FHQ 样例随机输出求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		{
			f=-1;    
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0',ch=getchar();
	}
	return x*f;
}
int n,q;
string s;
const int N=1000005;
struct node{
	int val;
	int pri;
	int lson;
	int rson;
	int siz;
	int sum;
	int lmax,lmin;
	int rmax,rmin;
	int rep;
	int swa;
	int inv;
}tr[N];
int root,cnt;
int build(int v) 
{
	tr[++cnt].val=v;
	tr[cnt].pri=rand();
	tr[cnt].siz=1;
	tr[cnt].sum=v;
	if(v==1)
	{
		tr[cnt].lmax=tr[cnt].rmax=1;
		tr[cnt].lmin=tr[cnt].rmin=0;
	}
	else
	{
		tr[cnt].lmax=tr[cnt].rmax=0;
		tr[cnt].lmin=tr[cnt].rmin=-1;
	}
	tr[cnt].rep=0;
	tr[cnt].swa=0;
	tr[cnt].inv=0;
	return cnt;
}
void pushdown(int u)
{
	if(!u) 
	{
		return;
	}
	if(tr[u].rep)
	{
		int c=tr[u].rep;
		if(tr[u].lson)
		{
			tr[tr[u].lson].rep=c;
			tr[tr[u].lson].val=c;
			tr[tr[u].lson].sum=c*tr[tr[u].lson].siz;
			if(c==1)
			{
				tr[tr[u].lson].lmax=tr[tr[u].lson].rmax=tr[tr[u].lson].siz;
				tr[tr[u].lson].lmin=tr[tr[u].lson].rmin=0;
			}
			else
			{
				tr[tr[u].lson].lmax=tr[tr[u].lson].rmax=0;
				tr[tr[u].lson].lmin=tr[tr[u].lson].rmin=-tr[tr[u].lson].siz;
			}
			tr[tr[u].lson].swa=tr[tr[u].lson].inv=0;
		}
		if(tr[u].rson)
		{
			tr[tr[u].rson].rep=c;
			tr[tr[u].rson].val=c;
			tr[tr[u].rson].sum=c*tr[tr[u].rson].siz;
			if(c==1)
			{
				tr[tr[u].rson].lmax=tr[tr[u].rson].rmax=tr[tr[u].rson].siz;
				tr[tr[u].rson].lmin=tr[tr[u].rson].rmin=0;
			}
			else
			{
				tr[tr[u].rson].lmax=tr[tr[u].rson].rmax=0;
				tr[tr[u].rson].lmin=tr[tr[u].rson].rmin=-tr[tr[u].rson].siz;
			}
			tr[tr[u].rson].swa=tr[tr[u].rson].inv=0;
		}
		tr[u].rep=0;
	}
	if(tr[u].swa)
	{
		swap(tr[u].lson,tr[u].rson);
		swap(tr[u].lmax,tr[u].rmax);
		swap(tr[u].lmin,tr[u].rmin);
		if(tr[u].lson) 
		{
			tr[tr[u].lson].swa^=1;		
		}
		if(tr[u].rson) 
		{
			tr[tr[u].rson].swa^=1;
		}
		tr[u].swa=0;
	}
	if(tr[u].inv)
	{
		tr[u].val*=-1;
		tr[u].sum*=-1;
		swap(tr[u].lmax,tr[u].lmin);
		tr[u].lmax*=-1;
		tr[u].lmin*=-1;
		swap(tr[u].rmax,tr[u].rmin);
		tr[u].rmax*=-1;
		tr[u].rmin*=-1;
		if(tr[u].lson) 
		{
			tr[tr[u].lson].inv^=1;
		}
		if(tr[u].rson) 
		{
			tr[tr[u].rson].inv^=1;
		}
		tr[u].inv=0;
	}
}
void update(int u) 
{
	if(!u) return;
	pushdown(u);
	int l=tr[u].lson,r=tr[u].rson;
	tr[u].siz=tr[l].siz+tr[r].siz+1;
	tr[u].sum=tr[l].sum+tr[u].val+tr[r].sum;
	tr[u].lmax=max(tr[l].lmax,tr[l].sum+tr[u].val+tr[r].lmax);
	tr[u].lmin=min(tr[l].lmin,tr[l].sum+tr[u].val+tr[r].lmin);
	tr[u].rmax=max(tr[r].rmax,tr[r].sum+tr[u].val+tr[l].rmax);
	tr[u].rmin=min(tr[r].rmin,tr[r].sum+tr[u].val+tr[l].rmin);
}
void split(int now,int k,int &x,int &y) 
{
	if(now==0) 
	{
		x=y=0;
		return;
	}
	pushdown(now);
	if(tr[tr[now].lson].siz+1<=k) 
	{
		x=now;
		split(tr[now].rson,k-tr[tr[now].lson].siz-1,tr[now].rson,y);
	} 
	else 
	{
		y=now;
		split(tr[now].lson,k,x,tr[now].lson);
	}
	update(now);
}
int merge(int x,int y) 
{
	if(!x||!y) 
	{
		return x+y;
	}
	pushdown(x);
	pushdown(y);
	if(tr[x].pri>tr[y].pri) 
	{
		tr[x].rson=merge(tr[x].rson,y);
		update(x);
		return x;
	} 
	else 
	{
		tr[y].lson=merge(x,tr[y].lson);
		update(y);
		return y;
	}
}
void Replace(int l,int r,int c)
{
	int x,y,z;
	split(root,r,x,z);
	split(x,l-1,x,y);
	tr[y].rep=c;
	tr[y].val=c;
	tr[y].sum=c*tr[y].siz;
	if(c==1)
	{
		tr[y].lmax=tr[y].rmax=tr[y].siz;
		tr[y].lmin=tr[y].rmin=0;
	}
	else
	{
		tr[y].lmax=tr[y].rmax=0;
		tr[y].lmin=tr[y].rmin=-tr[y].siz;
	}
	tr[y].swa=tr[y].inv=0;
	root=merge(merge(x,y),z);
}
void Swap(int l,int r)
{
	int x,y,z;
	split(root,r,x,z);
	split(x,l-1,x,y);
	tr[y].swa^=1;
	root=merge(merge(x,y),z);
}
void Invert(int l,int r)
{
	int x,y,z;
	split(root,r,x,z);
	split(x,l-1,x,y);
	tr[y].inv^=1;
	root=merge(merge(x,y),z);
}
int Query(int l,int r)
{
	int x,y,z,ret;
	split(root,r,x,z);
	split(x,l-1,x,y);
	ret=((-tr[y].lmin+1)/2)+((tr[y].rmax+1)/2);
	root=merge(merge(x,y),z);
	return ret;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	srand(0);
	cin>>n>>q;
	cin>>s;
	s=" "+s;
	for(int i=1;i<=n;i++)
	{
		int v;
		if(s[i]=='(') 
		{
			v=1;
		} 
		else 
		{
			v=-1;
		}
		root=merge(root,build(v));
	}
	while(q--)
	{
		string op;
		cin>>op;
		if(op[0]=='R')
		{
			int l,r;
			char c;
			cin>>l>>r>>c;
			if(c=='(') 
			{
				Replace(l,r,1);
			} 
			else 
			{
				Replace(l,r,-1);
			}
		}
		else if(op[0]=='S')
		{
			int l,r;
			cin>>l>>r;
			Swap(l,r);
		}
		else if(op[0]=='I')
		{
			int l,r;
			cin>>l>>r;
			Invert(l,r);
		}
		else if(op[0]=='Q')
		{
			int l,r;
			cin>>l>>r;
			cout<<Query(l,r)<<"\n";
		}
	}
	return 0;
}