我的思路是这样的:
用线段树 T 实时维护 a 数组的区间和,单点修改,区间查询;
用线段树 sum 维护,对于所有 r∈[c2,n],l=r−c2+1 和所有 r∈[1,c2),l=1 的所有区间 [l,r] 的和。其中,线段树上第 r 个位置记录的是区间 [l,r] 的和。在pushup的时候,sum 取的是左子和右子的最大值,也即 sumrt=sumls+sumrs。
查询的时候,查询yy可操作的最左区间的左端点 L,和最右区间的右端点 R,如果存在 R−L+1>c1 或者 al+⋯+ar>w1,输出tetris;否则输出cont。
结果:在大样例seq4和seq5中输出了很多不该输出的tetris,交上去 40pts,过了前两个特殊性质,还请路过的大佬 Hack 一下。
#include<bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs (rt<<1)|1
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
const int MAXN=3e5+10;
long long a[MAXN];
struct SegmentTree{//实现一个数据结构线段树
long long sum[MAXN<<2],lazy[MAXN<<2];
inline void pushup(int rt){
sum[rt]=sum[rt<<1]+sum[(rt<<1)|1];
}
void pushdown(int rt,int Llength,int Rlength){
if(lazy[rt]){
lazy[rt<<1]+=lazy[rt];
lazy[(rt<<1)|1]+=lazy[rt];
sum[rt<<1]=sum[rt<<1]+lazy[rt]*(long long)(Llength);
sum[(rt<<1)|1]=sum[(rt<<1)|1]+lazy[rt]*(long long)(Rlength);
lazy[rt]=0;//清空lazy标记
}
}
void build(int l,int r,int rt){
if(l==r){
sum[rt]=a[l];
return;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int L,int R,long long val,int l,int r,int rt){
if(L<=l&&r<=R){
sum[rt]+=((long long)(r-l+1)*val);
lazy[rt]+=val;
return;
}
int mid=(l+r)>>1;
pushdown(rt,mid-l+1,r-mid);
if(L<=mid){
update(L,R,val,lson);
}
if(R>mid){
update(L,R,val,rson);
}
pushup(rt);
}
long long query(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
return sum[rt];
}
int mid=(l+r)>>1;
long long res=0;
pushdown(rt,mid-l+1,r-mid);
if(L<=mid){
res+=query(L,R,lson);
}
if(R>mid){
res+=query(L,R,rson);
}
return res;
}
}T;
int n,q,c1,c2;
long long w1,w2;
long long sum[MAXN<<2],lazy[MAXN<<2];
long long s[MAXN];
inline void pushup(int rt){
sum[rt]=max(sum[ls],sum[rs]);
}
inline void pushdown(int rt){
if(lazy[rt]){
lazy[ls]+=lazy[rt];
lazy[rs]+=lazy[rt];
sum[ls]+=lazy[rt];
sum[rs]+=lazy[rt];
lazy[rt]=0;
}
}
void build(int l,int r,int rt){
if(l==r){
sum[rt]=s[l];
return;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
void update(int L,int R,long long val,int l,int r,int rt){
if(L<=l&&r<=R){
lazy[rt]+=val;
sum[rt]+=val;
return;
}
int mid=(l+r)>>1;
pushdown(rt);
if(L<=mid){
update(L,R,val,lson);
}
if(R>mid){
update(L,R,val,rson);
}
pushup(rt);
}
int queryL(int L,int R,int l,int r,int rt){
if(r<L||l>R){
return -1;
}
if(l==r){
return l;
}
int mid=(l+r)>>1;
pushdown(rt);
int rL=(sum[ls]>w2?queryL(L,R,lson):-1);
if(~rL){
return rL;
}
int rR=(sum[rs]>w2?queryL(L,R,rson):-1);
if(~rR){
return rR;
}
else{
return -1;
}
}
int queryR(int L,int R,int l,int r,int rt){
if(r<L||l>R){
return -1;
}
if(l==r){
return r;
}
int mid=(l+r)>>1;
pushdown(rt);
int rR=(sum[rs]>w2?queryR(L,R,rson):-1);
if(~rR){
return rR;
}
int rL=(sum[ls]>w2?queryR(L,R,lson):-1);
if(~rL){
return rL;
}
else{
return -1;
}
}
int main(){
// freopen("seq4.in","r",stdin);
// freopen("seq4.out","w",stdout);
scanf("%d%d%d%d%lld%lld",&n,&q,&c1,&c2,&w1,&w2);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i];
}
T.build(1,n,1);
for(int i=c2;i<=n;++i){
s[i]-=s[i-c2];
}
int op,x,y;
bool canwin=true;
build(1,n,1);
while(q--){
scanf("%d%d%d",&op,&x,&y);
if(op==1){
update(x,min(n,x+c2-1),y,1,n,1);
T.update(x,x,y,1,n,1);
}
else{
if(c2>n&&w2==0){
if(c1<n||T.query(1,n,1,n,1)>w1){
putchar('t');putchar('e');putchar('t');putchar('r');putchar('i');putchar('s');
putchar('\n');
continue;
}
else{
putchar('c');putchar('o');putchar('n');putchar('t');
putchar('\n');
continue;
}
}
canwin=true;
if(y-x+1<=c2){
long long b=T.query(x,y,1,n,1);
if(b>w2&&(y-x+1>c1||b>w1)){
putchar('t');putchar('e');putchar('t');putchar('r');putchar('i');putchar('s');
putchar('\n');
continue;
}
else{
putchar('c');putchar('o');putchar('n');putchar('t');
putchar('\n');
continue;
}
}
int L=queryL(x+c2,y,1,n,1);
if(L==-1){
putchar('c');putchar('o');putchar('n');putchar('t');
putchar('\n');
continue;
}
L=max(L-c2+1,x);
int R=queryR(x,y,1,n,1);
if(R-L+1>c1||T.query(L,R,1,n,1)>w1){
canwin=false;
}
if(canwin){
putchar('c');putchar('o');putchar('n');putchar('t');
}
else{
putchar('t');putchar('e');putchar('t');putchar('r');putchar('i');putchar('s');
}
putchar('\n');
}
}
}