梦熊 CSP-S模拟赛 T3 youyou 的序列 II

原题链接


 

题目大意

给定一个长度为 n 的非负整数序列 a ，初始时所有数字均被标记为蓝色，youyou 和 yy 轮流对序列 a 进行操作，由 youyou 开始。

• 如果当前是 youyou 的回合，那么他可以至多选择连续的 c 1 个数，如果他们的和小于等于 w 1 ，则标记为红色。

• 如果当前是 yy 的回合，那么他可以至多选择连续的 c 2 个数，如果他们的和大于 w 2 ，则标记为蓝色。

定义 youyou 胜利即是在游戏任意时刻，所有数字都被标记为红色，定义 yy 胜利则是在无穷多个回合内， youyou 无法胜利。现在给定 q 个操作，对于每个操作给定三个数 opt , x , y 。

• 如果 opt 为 1 ，表示将 a x 增加 y 。

• 如果 opt 为 2 ，表示在序列 [ x , y ] 上进行一轮游戏。

对于每一个操作 2 ，判断 youyou 能否获得胜利

解题思路

代码如下：

#include <bits/stdc++.h>
#define ll long longusing namespace std;const int maxn = 3e5 + 5;int n, q, c1, c2;
ll w1, w2;
ll a[maxn], tr[maxn];void upd(int id, ll k){for(int i = id; i <= n; i += i & -i) tr[i] += k; 
}
ll que(int id){ll s = 0;for(int i = id; i > 0; i -= i & -i) s += tr[i];return s;
}
namespace seg{
#define l(x) (x << 1)
#define r(x) (x << 1 | 1)
ll max1[maxn << 2], tag[maxn << 2];
void up(int x){max1[x] = max(max1[l(x)], max1[r(x)]);
}
void down(int x){max1[l(x)] += tag[x], tag[l(x)] += tag[x];max1[r(x)] += tag[x], tag[r(x)] += tag[x];tag[x] = 0;
}
void update(int x, int l, int r, int ql, int qr, ll k){if(ql <= l && r <= qr){max1[x] += k, tag[x] += k;return;}down(x);int mid = l + r >> 1;if(ql <= mid) update(l(x), l, mid, ql, qr, k);if(qr > mid) update(r(x), mid + 1, r, ql, qr, k);up(x);
}
int query1(int x, int l, int r, int ql, int qr, ll k){if(ql <= l && r <= qr){if(max1[x] <= k) return 0;if(l == r){if(max1[x] > k) return l;else return 0;}down(x);int mid = l + r >> 1;if(max1[l(x)] > k) return query1(l(x), l, mid, ql, qr, k);else return query1(r(x), mid + 1, r, ql, qr, k);}down(x);int mid = l + r >> 1, res = 0;if(ql <= mid) res = query1(l(x), l, mid, ql, qr, k);if(res) return res;if(qr > mid) res = query1(r(x), mid + 1, r, ql, qr, k);return res;
}
int query2(int x, int l, int r, int ql, int qr, ll k){if(ql <= l && r <= qr){if(max1[x] <= k) return 0;if(l == r){if(max1[x] > k) return l;else return 0;}down(x);int mid = l + r >> 1;if(max1[r(x)] > k) return query2(r(x), mid + 1, r, ql, qr, k);else return query2(l(x), l, mid, ql, qr, k);}down(x);int mid = l + r >> 1, res = 0;if(qr > mid) res = query2(r(x), mid + 1, r, ql, qr, k);if(res) return res;if(ql <= mid) res = query2(l(x), l, mid, ql, qr, k);return res;
}}
namespace seg2{
#define l(x) (x << 1)
#define r(x) (x << 1 | 1)
ll max1[maxn << 2];
void up(int x){max1[x] = max(max1[l(x)], max1[r(x)]);
}
void build(int x, int l, int r){if(l == r){max1[x] = a[l];return;}int mid = l + r >> 1;build(l(x), l, mid), build(r(x), mid + 1, r);up(x);
}
void update(int x, int l, int r, int id, ll k){if(l == r){max1[x] += k;return;}int mid = l + r >> 1;if(id <= mid) update(l(x), l, mid, id, k);else update(r(x), mid + 1, r, id, k);up(x);
}
ll query(int x, int l, int r, int ql, int qr){if(ql <= l && r <= qr) return max1[x];int mid = l + r >> 1;ll res = 0;if(ql <= mid) res = max(res, query(l(x), l, mid, ql, qr));if(qr > mid) res = max(res, query(r(x), mid + 1, r, ql, qr));return res;
}}int main(){scanf("%d %d %d %d %lld %lld", &n, &q, &c1, &c2, &w1, &w2);for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);for(int i = 1; i <= n; i ++){upd(i, a[i]);seg::update(1, 1, n, max(1, i - c2 + 1), i, a[i]);}seg2::build(1, 1, n);while(q --){int op;scanf("%d", &op);if(op == 1){int x;ll y;scanf("%d %lld", &x, &y);upd(x, y);seg::update(1, 1, n, max(1, x - c2 + 1), x, y);seg2::update(1, 1, n, x, y);a[x] += y;}else{int l, r;scanf("%d %d", &l, &r);if(seg2::query(1, 1, n, l, r) > w1){printf("tetris\n");continue;}int L = 0, R = 0;if(r - l + 1 <= c2){if(que(r) - que(l - 1) > w2) L = l, R = r;}else{L = seg::query1(1, 1, n, l, r - c2 + 1, w2);R = seg::query2(1, 1, n, l, r - c2 + 1, w2) + c2 - 1;}if(!L || !R){printf("cont\n");continue;}if(que(R) - que(L - 1) <= w1 && R - L + 1 <= c1) printf("cont\n");else printf("tetris\n");}}return 0;
}

线段树+树状数组做法（80pts）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=3e6+5;
int n,q,c1,c2,w1,w2,a[MAXN],t[MAXN];
inline int read()
{int number=0,Fd=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')Fd=-1;ch=getchar();}while(ch>='0'&&ch<='9')number=(number<<1)+(number<<3)+(ch^48),ch=getchar();return number*Fd;
}
inline void write(int number)
{if(number<0)putchar('-'),number=-number;if(number>9)write(number/10);putchar(number%10+'0');
}
struct Tree{int l,r,sum,laz;#define l(x) tree[x].l#define r(x) tree[x].r#define sum(x) tree[x].sum#define laz(x) tree[x].laz
}tree[MAXN<<1];
inline int Build(int p,int l,int r)
{l(p)=l,r(p)=r;if(l==r)return sum(p)=a[l];int mid=l+r>>1;return sum(p)=max(Build(p<<1,l,mid),Build(p<<1|1,mid+1,r));
}
inline int PushUp(int p)
{return sum(p)=max(sum(p<<1),sum(p<<1|1));
}
inline void PushDown(int p)
{if(laz(p)){sum(p<<1)+=laz(p);sum(p<<1|1)+=laz(p);laz(p<<1)+=laz(p);laz(p<<1|1)+=laz(p);laz(p)=0;}
}
inline void Change(int p,int l,int r,int d)
{if(l<=l(p)&&r(p)<=r){sum(p)+=d,laz(p)+=d;return;}//printf("%lld ",p);PushDown(p);int mid=l(p)+r(p)>>1;if(l<=mid)Change(p<<1,l,r,d);if(mid<r)Change(p<<1|1,l,r,d);PushUp(p);
}
inline int Query(int p,int l,int r)
{if(l<=l(p)&&r(p)<=r)return sum(p);PushDown(p);int mid=l(p)+r(p)>>1,res=0;if(l<=mid)res=max(Query(p<<1,l,r),res);if(mid<r)res=max(Query(p<<1|1,l,r),res);return res;
}
inline int low(int x)
{return x&-x;
}
inline void add(int x,int d)
{while(x<=n)t[x]+=d,x+=low(x);
}
inline int query(int x)
{int res=0;while(x)res+=t[x],x-=low(x);return res;
}
main()
{
//	freopen("seq5.in","r",stdin);
//	freopen("seq5.out","w",stdout);n=read(),q=read(),c1=read(),c2=read(),w1=read(),w2=read();for(int i=1;i<=n;i++)a[i]=read(),add(i,a[i]);Build(1,1,n);while(q--){int opt,x,y;opt=read(),x=read(),y=read();if(opt==1)add(x,y),Change(1,x,x,y),a[x]+=y;else{int tmp=Query(1,x,y);if(tmp>w1){puts("tetris");continue;}tmp=query(y)-query(x-1);if(tmp<=w1&&y-x+1<=c1){puts("cont");continue;}else if(tmp>=w2&&y-x+1<=c2){puts("tetris");continue;}else if(tmp<w2){puts("cont");continue;}tmp=query(x-1+c2)-query(x-1);int l=x,r=x-1+c2,TL=0,TR=0;while(r<=y){if(tmp>=w2){TL=l;break;}tmp-=a[l++];tmp+=a[++r];}if(!TL){puts("cont");continue;}tmp=query(y)-query(y-c2);l=y-c2+1,r=y,TR=0;while(l>=x){if(tmp>=w2){TR=r;break;}tmp-=a[r--];tmp+=a[--l];}if(!TR){puts("cont");continue;}tmp=query(TR)-query(TL-1);if(tmp<=w1&&TR-TL+1<=c1)puts("cont");else puts("tetris");}}return 0;
}