题目链接

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node {
	int x,y;
};
int vis[50000005];
struct tree {
	#define ls (x<<1)
	#define rs ((x<<1)|1)
	#define mid ((l+r)>>1)
	int lsum[5000005],rsum[5000005];
	void pushup(int x,int l,int r) {
		int len1=(mid-l+1),len2=(r-(mid+1)+1);
		
		if(lsum[ls]==len1) lsum[x]=lsum[ls]+lsum[rs];
		else lsum[x]=lsum[ls];
		
		if(rsum[rs]==len2) rsum[x]=rsum[ls]+rsum[rs];
		else rsum[x]=rsum[rs];
	}
	void build(int x,int l,int r) {
		if(l==r) {
			lsum[x]=1;
			rsum[x]=1;
			return ;
		}
		build(ls,l,mid);
		build(rs,mid+1,r);
		lsum[x]=(lsum[ls]+lsum[rs]);
		rsum[x]=(rsum[ls]+rsum[rs]);
	}
	void modify(int x,int l,int r,int L,int R,int k) {
		if(L<=l && r<=R) {
			lsum[x]=k;
			rsum[x]=k;
			return ;
		}
		if(L<=mid) modify(ls,l,mid,L,R,k);
		if(mid<R) modify(rs,mid+1,r,L,R,k);
		pushup(x,l,r);
	}
	node query(int x,int l,int r,int L,int R) {
		if(L<=l && r<=R) {return (node){lsum[x],rsum[x]};}
		node res;
		if(L<=mid && mid<R) {
			node res1,res2;
			res1=query(ls,l,mid,L,R);
			res2=query(rs,mid+1,r,L,R);
			
			if(res1.x==(mid-l+1)) {
				res.x=res1.x+res2.x;
			} else res.x=res1.x;
			
			if(res2.y==(r-(mid+1)+1)) {
				res.y=res2.y+res1.y;
			} else res.y=res2.y;
			
		} else {
			if(L<=mid) {res=query(ls,l,mid,L,R);} 
			if(mid<R) {res=query(rs,mid+1,r,L,R);}
		}
		pushup(x,l,r);
		return res;
	}
}T;
int stk[5000005],tail=0;
signed main() {
	int n,m;
	scanf("%lld %lld",&n,&m);
	T.build(1,1,n);
	while(m--) {
		char c;
		int x;
		cin>>c;
		if(c=='D') {
			scanf("%lld",&x);
			T.modify(1,1,n,x,x,0);
			stk[++tail]=x;
			vis[x]=1;
		} else if(c=='R') {
			T.modify(1,1,n,stk[tail],stk[tail],1);
			vis[stk[tail]]=0;
			tail--;
		} else {
			scanf("%lld",&x);
			int l=0,r=0;
			if(x-1>0) l=T.query(1,1,n,1,x-1).y;
			if(x+1<=n) r=T.query(1,1,n,x+1,n).x;
			if(!vis[x]) printf("%lld\n",l+1+r);
			else printf("0\n");
		}
	}
	return 0;
}

rt,样例过了de了半小时无果

就是记录最长左右端点