线段树求助!!!
查看原帖
线段树求助!!!
987871
hopelessness楼主2023/9/28 20:47

关于线段树WA掉,我很是无奈
这是什么意思???
Code:

/*
	by hopelessness
*/
#include<bits/stdc++.h>

#define il inline
#define MAXN 202020
#define LL long long
#define INF 2147483647
#define ri register int

using namespace std;

struct Segment_Tree {
	int lch,rch,l,r,sum;
#define l(x) t[x].l
#define r(x) t[x].r
#define lch(x) t[x].lch
#define rch(x) t[x].rch
#define sum(x) t[x].sum
} t[MAXN<<2];

int n,m,tot,p,len,num,ans;

template<typename T>il void read(T &x) {
	char c=getchar();
	x=0;
	int f=0;
	for(; !isdigit(c); c=getchar()) f|=(c=='-');
	for(; isdigit(c); c=getchar()) x=((x<<3)+(x<<1)+(c^48));
	x=f?-x:x;
}
template<typename T>il void write(T x) {
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10^48);
}
il void Build(int l,int r) {
	ri x=++tot;
	l(x)=l;
	r(x)=r;
	if(l==r) {
		sum(x)=0;
		return ;
	}
	ri mid=(l+r)>>1;
	lch(x)=tot+1;
	Build(l,mid);
	rch(x)=tot+1;
	Build(mid+1,r);
	sum(x)=max(sum(lch(x)),sum(rch(x)));
	return ;
}
il int Query(int x,int l,int r) {
	if(l<=l(x)&&r(x)<=r) {
		return sum(x);
	}
	ri mid=(l(x)+r(x))>>1;
	ri ans=-INF;
	if(l<=mid) ans=max(Query(lch(x),l,r),ans);
	if(r>mid) ans=max(Query(rch(x),l,r),ans);
	return ans;
}
il void Change(int x,int pos,int num) {
	if(l(x)==r(x)&&l(x)==pos) {
		sum(x)=num;
		return ;
	}
	ri mid=(l(x)+r(x))>>1;
	if(pos<=mid) Change(lch(x),pos,num);
	else Change(rch(x),pos,num);
	sum(x)=max(sum(lch(x)),sum(rch(x)));
	return ;
}

int main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(m),read(p);
	Build(1,MAXN);
	while(m--) {
		char opt=getchar();
		if(!isalpha(opt)) opt=getchar();
		read(num);
		switch(opt) {
			case 'A': {
				Change(1,++len,(num+ans)%p);
				break;
			}
			case 'Q': {
				ans=Query(1,len-num+1,len);
				write(ans),putchar('\n');
				break;
			}
		}
	}
	return 0;
}
/*
10 100
A 97
Q 1
Q 1
A 17
Q 2
A 63
Q 1
Q 1
Q 3
A 99
-----
97
97
97
60
60
97
*/
2023/9/28 20:47
加载中...