rt,开了三棵线段树,只对了 #1~5,7,8。
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 300006
#define WIN puts("cont")
#define LOSE puts("tetris")
using namespace std;
int n,m,c1,c2,w1,w2;
int a[N],s[N];
int tree1[N<<2],tree2[N<<2],sum[N<<2],tag[N<<2],findans;
/*
s for the sum of [1, i]
tree1 for maxinum of the sum of [i, i+c2-1]
tag is the lazy-tag of tree1
tree2 for maxinum of a_i
sum for the sum of a_i
build() is for building the segment trees
update_range() is for updating tree1
update_single() is for updating tree2 & sum
query_max() is for querying tree2
query_whole_(min/max)() is for querying a whole node on segment trees
query_range_(min/max)() is for binary searching on segment trees
query_sum() is for querying sum
Very good, but the code is like sh*t.
*/
void build(int p,int l,int r)
{
if(l==r)
{
tree1[p]=s[min(l+c2-1,n)]-s[l-1];
sum[p]=tree2[p]=a[l];
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
tree1[p]=max(tree1[p<<1],tree1[p<<1|1]);
tree2[p]=max(tree2[p<<1],tree2[p<<1|1]);
sum[p]=sum[p<<1]+sum[p<<1|1];
}
void addtag(int p,int x){tag[p]+=x,tree1[p]+=x;}
void push_down(int p)
{
if(tag[p])
{
addtag(p<<1,tag[p]);
addtag(p<<1|1,tag[p]);
tag[p]=0;
}
}
void update_range(int p,int l,int r,int L,int R,int x)
{
if(L<=l&&r<=R){addtag(p,x);return;}
push_down(p);
int mid=l+r>>1;
if(L<=mid)update_range(p<<1,l,mid,L,R,x);
if(R>mid)update_range(p<<1|1,mid+1,r,L,R,x);
tree1[p]=max(tree1[p<<1],tree1[p<<1|1]);
}
void update_single(int p,int l,int r,int k,int x)
{
if(l==r){tree2[p]+=x,sum[p]+=x;return;}
push_down(p);
int mid=l+r>>1;
if(k<=mid)update_single(p<<1,l,mid,k,x);
else update_single(p<<1|1,mid+1,r,k,x);
tree2[p]=max(tree2[p<<1],tree2[p<<1|1]);
sum[p]=sum[p<<1]+sum[p<<1|1];
}
int query_max(int p,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return tree2[p];
push_down(p);
int mid=l+r>>1,ret=-1;
if(L<=mid)ret=max(ret,query_max(p<<1,l,mid,L,R));
if(R>mid)ret=max(ret,query_max(p<<1|1,mid+1,r,L,R));
return ret;
}
int query_sum(int p,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return sum[p];
push_down(p);
int mid=l+r>>1,ret=0;
if(L<=mid)ret+=query_sum(p<<1,l,mid,L,R);
if(R>mid)ret+=query_sum(p<<1|1,mid+1,r,L,R);
return ret;
}
int query_whole_min(int p,int l,int r)
{
if(l==r)return l;
push_down(p);
int mid=l+r>>1;
if(tree1[p<<1]>w2)return query_whole_min(p<<1,l,mid);
return query_whole_min(p<<1|1,mid+1,r);
}
int query_whole_max(int p,int l,int r)
{
if(l==r)return l;
push_down(p);
int mid=l+r>>1;
if(tree1[p<<1|1]>w2)return query_whole_max(p<<1|1,mid+1,r);
return query_whole_max(p<<1,l,mid);
}
int query_range_min(int p,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
if(tree1[p]>w2&&findans)
{
findans=0;
return query_whole_min(p,l,r);
}
return 1e15;
}
push_down(p);
int mid=l+r>>1,ret=1e15;
if(L<=mid)ret=min(ret,query_range_min(p<<1,l,mid,L,R));
if(R>mid)ret=min(ret,query_range_min(p<<1|1,mid+1,r,L,R));
return ret;
}
int query_range_max(int p,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
if(tree1[p]>w2&&findans)
{
findans=0;
return query_whole_max(p,l,r);
}
return -1e15;
}
push_down(p);
int mid=l+r>>1,ret=-1e15;
if(L<=mid)ret=max(ret,query_range_max(p<<1,l,mid,L,R));
if(R>mid)ret=max(ret,query_range_max(p<<1|1,mid+1,r,L,R));
return ret;
}
main()
{
scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&c1,&c2,&w1,&w2);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]),s[i]=s[i-1]+a[i];
build(1,1,n);
while(m--)
{
int opt,l,r,x,y;
scanf("%lld",&opt);
if(opt==1)
{
scanf("%lld%lld",&x,&y);
update_single(1,1,n,x,y);
update_range(1,1,n,max(1ll,x-c2+1),x,y);
}
else
{
scanf("%lld%lld",&l,&r);
int len=r-l+1;
if(len<c2)
{
if(query_sum(1,1,n,l,r)<=w1&&len<=c1)WIN;
else if(query_sum(1,1,n,l,r)>w2)LOSE;
else if(query_max(1,1,n,l,r)<=w1)WIN;
else LOSE;
}
else
{
int i=query_range_min(findans=1,1,n,l,r);
int j=query_range_max(findans=1,1,n,l,r)+c2-1;
if(i>n)
{
if(query_max(1,1,n,l,r)<=w1)WIN;
else LOSE;
}
else if(len<=c1&&query_max(1,1,n,l,r)<=w1)WIN;
else LOSE;
}
}
}
return 0;
}