场上乱写了个最坏 O(nq) 的做法,结果拿了 80pts,只有性质 D 没过。
主要代码:
SegmentTree T(a);
while(q--){
int op,x,y;cin>>op>>x>>y;
if(op==1) T.update(x,y),a[x]+=y;
else {
if(T.queryMax(x,y)>w1)cout<<"tetris"<<endl;
else{
int l=x,r=y,suml=T.querySum(x,min(y,x+c2-1)),sumr=T.querySum(max(x,y-c2+1),y);
while(suml<=w2&&l+c2-1<=y){
suml-=a[l],suml+=a[l+c2];
l++;
}
while(sumr<=w2&&r-c2+1>=x){
sumr-=a[r],sumr+=a[r-c2];
r--;
}
if(suml<=w2||sumr<=w2){
cout<<"cont"<<endl;
}
else{
if(r-l+1>c1||T.querySum(l,r)>w1) cout<<"tetris"<<endl;
else cout<<"cont"<<endl;
}
}
}
}