萌新求助线段树
查看原帖
萌新求助线段树
140360
MeowScore楼主2022/1/30 23:55

rt,调废了,写线段树好久没这么崩溃了/kk

请大佬指教/kel


#include<bits/stdc++.h>
using namespace std;
const int N=50010;
struct ST{
	int lmax;
	int rmax;
}st[N*4];
int q[N];
int tail;
void build(int root,int l,int r){
	st[root].lmax=st[root].rmax=r-l+1;
	if(l==r)
		return;
	int mid=(l+r)/2;
	build(root*2,l,mid);
	build(root*2+1,mid+1,r);
}
void change(int root,int l,int r,int x,int k){
	if(l==r){
		st[root].lmax=st[root].rmax=k;
		return;
	}
	int mid=(l+r)/2;
	if(mid>=x) 
		change(root*2,l,mid,x,k);
	else
		change(root*2+1,mid+1,r,x,k);
	if(st[root*2].lmax==mid-l+1)
		st[root].lmax=st[root*2+1].lmax+mid-l+1;
	else
		st[root].lmax=st[root*2].lmax;
	if(st[root*2+1].rmax==r-mid)
		st[root].rmax=st[root*2].rmax+r-mid;
	else
		st[root].rmax=st[root*2+1].rmax; 
}
ST ask(int root,int l,int r,int x,int y){
	if(l>=x&&r<=y)
		return st[root];
	int mid=(l+r)/2;
	if(mid>=y)
		return ask(root*2,l,mid,x,y);
	else{
		if(mid+1<=x)
			return ask(root*2+1,mid+1,r,x,y);
		else{
			ST L=ask(root*2,l,mid,x,y);
			ST R=ask(root*2+1,mid+1,r,x,y);
			ST res;
			if(L.lmax==mid-l+1)
				res.lmax=R.lmax+mid-l+1;
			else
				res.lmax=L.lmax;
			if(R.rmax==r-mid)
				res.rmax=L.rmax+r-mid;
			else
				res.rmax=R.rmax;
			return res;
		}
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	build(1,1,n);
	for(int i=1;i<=m;i++){
		char opt;
		cin>>opt;
		if(opt=='D'){
			int x;
			cin>>x;
			tail++;
			q[tail]=x;
			change(1,1,n,x,0);
		}
		if(opt=='R'){
			int x=q[tail];
			tail--;
			change(1,1,n,x,1);
		}
		if(opt=='Q'){
			int x;
			cin>>x;
			int ans=0;
			ST res=ask(1,1,n,1,x);
			ans+=res.rmax;
			if(x!=n){
				res=ask(1,1,n,x+1,n);
				ans+=res.lmax;
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

2022/1/30 23:55
加载中...