为什么70
查看原帖
为什么70
856004
Grammar_hbw楼主2024/10/24 20:59

本蒟蒻实在找不出什么问题了qwqwqwqwqwq,就是个树状数组+线段树二分,但调不出来

#include <bits/stdc++.h>
#define yes do{cout<<"cont\n";goto end;}while(0)
#define no do{cout<<"tetris\n";goto end;}while(0)
#define name "seq"
using namespace std;
typedef long long ll;
//#define int ll
const int N=300007;
ll n,q,c1,c2,w1,w2;
struct bittree{
	ll val[N],sz;
	void add(int x,ll v){for(int i=x;i<=sz;i+=(i&-i))val[i]+=v;}
	ll query(int l,int r){
		ll ans=0;
		for(int i=r;i;i-=(i&-i)) ans+=val[i];
		for(int i=l-1;i;i-=(i&-i)) ans-=val[i];
		return ans;
	}
} tr;
struct segtree{
	ll val[N<<2],lz[N<<2];//[x,x+c2-1]
	void pushdown(int o){
		ll& k=lz[o];
		if(k){val[o*2]+=k,val[o*2+1]+=k,lz[o*2]+=k,lz[o*2+1]+=k;k=0;}
	}
	void update(int o){val[o]=max(val[o*2],val[o*2+1]);}
	void add(int l,int r,int L,int R,int o,ll v){
		if(l<=L&&R<=r) return void((val[o]+=v,lz[o]+=v));
		pushdown(o);
		int mid=(L+R)>>1;
		if(l<=mid) add(l,r,L,mid,o*2,v);
		if(r>mid) add(l,r,mid+1,R,o*2+1,v);
		update(o);
	}
	ll query(int l,int r,int L,int R,int o){
		if(l<=L&&R<=r) return val[o];
		pushdown(o);
		int mid=(L+R)>>1;
		ll ans=0;
		if(l<=mid) ans=max(ans,query(l,r,L,mid,o*2));
		if(r>mid) ans=max(ans,query(l,r,mid+1,R,o*2+1));
		return ans;
	}
	int lower_bound(int x,int L,int R,int o,ll v){
		if(L==R) return L;
		pushdown(o);
		if(val[o]<=v) return R+1;
		int mid=(L+R)>>1,tmp=0;
		if(x<=mid&&val[o*2]>v) tmp=lower_bound(x,L,mid,o*2,v);
		if(tmp<x) tmp=lower_bound(x,mid+1,R,o*2+1,v);
		return tmp;
	}
	int upper_bound(int x,int L,int R,int o,ll v){
		if(L==R) return L;
		pushdown(o);
		if(val[o]<=v) return L-1;
		int mid=(L+R)>>1,tmp=R+1;
		if(x>mid&&val[o*2+1]>v) tmp=upper_bound(x,mid+1,R,o*2+1,v);
		if(tmp>x) tmp=upper_bound(x,L,mid,o*2,v);
		return tmp;
	}
} st,mn;
void add(int x,ll v){tr.add(x,v);st.add(max(x-c2+1,1ll),min(1ll*x,n-c2+1),1,n-c2+1,1,v),mn.add(x,x,1,n,1,v);}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q>>c1>>c2>>w1>>w2;
	tr.sz=n;
	for(int i=1,x;i<=n;i++) cin>>x,add(i,x);
	for(int i=1,op,x,y;i<=q;i++){
		cin>>op>>x>>y;
		if(op==1) add(x,y);
		else if(op==2){
			int l=0,r=0;
			if(mn.query(x,y,1,n,1)>w1) no;
			if(y-x+1<=c2){if(tr.query(x,y)>w2)l=x,r=y;else yes;}
			else l=st.lower_bound(x,1,n-c2+1,1,w2),r=st.upper_bound(y-c2+1,1,n-c2+1,1,w2)+c2-1;
			if(l>y||r<x) yes;
			if(r-l>=c1) no;
			if(tr.query(l,r)>w1) no;
			yes;
		}
		end:;
	}
}
2024/10/24 20:59
加载中...