40pts 求调玄关
查看原帖
40pts 求调玄关
718060
蒋辰逸楼主2024/10/23 18:58
#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace FastIO{
	char buf[1<<20],*p1,*p2;
	#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin), p1 == p2) ? 0 : *p1++)
	template<typename T>inline void read(T &x){
	    bool f=1;x=0;char ch=getchar();
	    while(ch<'0'||ch>'9'){if(ch=='-') f=!f;ch=getchar();}
	    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	    x=(f?x:-x);return;
	}
	template<typename T>inline void write(T x){
	    if(x<0) putchar('-'),x=-x;
	    if(x>9) write(x/10);
	    putchar(x%10+'0');return;
	}
}
using namespace FastIO;
int n,q,c1,c2,w1,w2;
int a[300010];
namespace seg{
	class seg1{
		private:
			#define lson (u<<1)
			#define rson ((u<<1)|1)
			#define mid ((l+r)>>1)
			int t[4*300010],tt[4*300010];
			inline void pushup(int u){
				t[u]=t[lson]+t[rson];
				tt[u]=max(tt[lson],tt[rson]);
				return;
			}
			inline void maketag(int u,int l,int r,int x){
				t[u]+=x*(r-l+1);
				tt[u]+=x;
				return;
			}
			inline bool inrng(int L,int R,int l,int r){
				return L<=l&&r<=R;
			}
			inline bool hvrng(int L,int R,int l,int r){
				return l<=R&&L<=r;
			}
		public:
			void build(int u=1,int l=1,int r=n){
				if(l==r){
					t[u]=a[l];
					tt[u]=a[l];
					return;
				}
				build(lson,l,mid);
				build(rson,mid+1,r);
				pushup(u);
				return;
			}
			void chg(int L,int R,int x,int u=1,int l=1,int r=n){
				if(inrng(L,R,l,r)){
					maketag(u,l,r,x);
					return;
				}
				if(hvrng(L,R,l,mid))chg(L,R,x,lson,l,mid);
				if(hvrng(L,R,mid+1,r))chg(L,R,x,rson,mid+1,r);
				pushup(u);
				return;
			}
			int querysum(int L,int R,int u=1,int l=1,int r=n){
				if(inrng(L,R,l,r)){
					return t[u];
				}
				int ret=0;
				if(hvrng(L,R,l,mid))ret+=querysum(L,R,lson,l,mid);
				if(hvrng(L,R,mid+1,r))ret+=querysum(L,R,rson,mid+1,r);
				return ret;
			}
			int querymax(int L,int R,int u=1,int l=1,int r=n){
				if(inrng(L,R,l,r)){
					return tt[u];
				}
				int ret=0;
				if(hvrng(L,R,l,mid))ret=max(ret,querymax(L,R,lson,l,mid));
				if(hvrng(L,R,mid+1,r))ret=max(ret,querymax(L,R,rson,mid+1,r));
				return ret;
			}
	};
	class seg2{
		private:
			#define lson (u<<1)
			#define rson ((u<<1)|1)
			#define mid ((l+r)>>1)
			int t[4*300010],tag[4*300010],sum[300010];
			inline void pushup(int u){
				t[u]=max(t[lson],t[rson]);
				return;
			}
			inline void pushdown(int u){
				t[lson]+=tag[u];
				t[rson]+=tag[u];
				tag[lson]+=tag[u];
				tag[rson]+=tag[u];
				tag[u]=0;
				return;
			}
			inline void maketag(int u,int x){
				t[u]+=x;
				tag[u]+=x;
				return;
			}
			inline bool inrng(int L,int R,int l,int r){
				return L<=l&&r<=R;
			}
			inline bool hvrng(int L,int R,int l,int r){
				return l<=R&&L<=r;
			}
		public:
			void cntsum(){
				for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
				return;
			}
			void build(int u=1,int l=1,int r=n-c2+1){
				if(l==r){
					t[u]=sum[l+c2-1]-sum[l-1];
					return;
				}
				build(lson,l,mid);
				build(rson,mid+1,r);
				pushup(u);
				return;
			}
			void chg(int L,int R,int x,int u=1,int l=1,int r=n-c2+1){
				if(inrng(L,R,l,r)){
					maketag(u,x);
					return;
				}
				pushdown(u);
				if(hvrng(L,R,l,mid))chg(L,R,x,lson,l,mid);
				if(hvrng(L,R,mid+1,r))chg(L,R,x,rson,mid+1,r);
				pushup(u);
				return;
			}
			int queryl(int L,int R,int u=1,int l=1,int r=n-c2+1){
				if(t[u]<w2)return r+1;
				if(l==r)return r;
				pushdown(u);
				if(inrng(L,R,l,r)){
					if(t[lson]>=w2)return queryl(L,R,lson,l,mid);
					else return queryl(L,R,rson,mid+1,r);
				}
				if(hvrng(L,R,l,mid))return queryl(L,R,lson,l,mid);
				if(hvrng(L,R,mid+1,r))return queryl(L,R,rson,mid+1,r);
				int ret=queryl(L,mid,lson,l,mid);
				if(ret==mid+1)ret=queryl(mid+1,R,rson,mid+1,r);
				return ret;
			}
			int queryr(int L,int R,int u=1,int l=1,int r=n-c2+1){
				if(t[u]<w2)return l-1;
				if(l==r)return l;
				pushdown(u);
				if(inrng(L,R,l,r)){
					if(t[rson]>=w2)return queryr(L,R,rson,mid+1,r);
					else return queryr(L,R,lson,l,mid+1);
				}
				if(hvrng(L,R,l,mid))return queryr(L,R,lson,l,mid);
				if(hvrng(L,R,mid+1,r))return queryr(L,R,rson,mid+1,r);
				int ret=queryr(mid+1,R,rson,mid+1,r);
				if(ret==mid)ret=queryr(L,mid,lson,l,mid);
				return ret;
			}
	};
}
using namespace seg;
seg1 tr1;
seg2 tr2;
signed main(){
	cin>>n>>q>>c1>>c2>>w1>>w2;
	c1=min(c1,n);c2=min(c2,n);
	for(int i=1;i<=n;i++)cin>>a[i];
	tr1.build();
	tr2.cntsum();
	tr2.build();
	while(q--){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1){
			a[x]+=y;
			tr1.chg(x,x,y);
			tr2.chg(max(x-c2+1,1ll),min(x,n-c2+1),y);
		}
		if(op==2){
			if(tr1.querymax(x,y)>w1){
				puts("tetris");
				continue;
			}
			if(y-x+1<c2){
				if(tr1.querysum(x,y)<w2){
					puts("cont");
					continue;
				}
				if(y-x+1<=c1&&tr1.querysum(x,y)<=w1){
					puts("cont");
					continue;
				}
				puts("tetris");
				continue;
			}
			int pos1=tr2.queryl(x,y-c2+1);
			int pos2=tr2.queryr(x,y-c2+1);
			if(pos1>pos2){
				puts("cont");
				continue;
			}
			pos2+=c2-1;
			if(pos2-pos1+1<=c1&&tr1.querysum(pos1,pos2)<=w1){
				puts("cont");
				continue;
			}
			puts("tetris");
			continue;
		}
	}
	return 0;
}
2024/10/23 18:58
加载中...