线段树做法,40pts,求Hack
查看原帖
线段树做法,40pts,求Hack
642173
KarmaticEnding楼主2024/10/21 10:16

我的思路是这样的:

用线段树 TT 实时维护 aa 数组的区间和,单点修改,区间查询;

用线段树 sumsum 维护,对于所有 r[c2,n],l=rc2+1r\in [c_2,n],l=r-c_2+1 和所有 r[1,c2),l=1r\in [1,c_2),l=1 的所有区间 [l,r][l,r] 的和。其中,线段树上第 rr 个位置记录的是区间 [l,r][l,r] 的和。在pushup的时候,sumsum 取的是左子和右子的最大值,也即 sumrt=sumls+sumrssum_{rt}=sum_{ls}+sum_{rs}

查询的时候,查询yy可操作的最左区间的左端点 LL,和最右区间的右端点 RR,如果存在 RL+1>c1R-L+1>c_1 或者 al++ar>w1a_l+\dots+a_r>w_1,输出tetris;否则输出cont

结果:在大样例seq4seq5中输出了很多不该输出的tetris,交上去 40pts40\text{pts},过了前两个特殊性质,还请路过的大佬 Hack\texttt{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');
		}
	}
}
2024/10/21 10:16
加载中...