首页 > 代码库 > try
try
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=100010; int t[maxn][2],f[maxn],s[maxn],lmax[maxn],lmin[maxn],rmax[maxn],rmin[maxn],sum[maxn],A[maxn],g[maxn],re[maxn],n,sz=0,a[maxn],root,q; char str[maxn]; int Node(int fa,int num) { sz++; t[sz][0]=t[sz][1]=0; f[sz]=fa; s[sz]=1; lmax[sz]=lmin[sz]=rmax[sz]=rmin[sz]=sum[sz]=A[sz]=num; } void count(int x) { sum[x]=sum[t[x][0]]+A[x]+sum[t[x][1]]; s[x]=s[t[x][0]]+1+s[t[x][1]]; lmax[x]=max(lmax[t[x][0]],sum[t[x][0]]+max(A[x],A[x]+lmax[t[x][1]])); lmin[x]=min(lmin[t[x][0]],sum[t[x][0]]+min(A[x],A[x]+lmin[t[x][1]])); rmax[x]=max(rmax[t[x][1]],sum[t[x][1]]+max(A[x],A[x]+rmax[t[x][0]])); rmin[x]=min(rmin[t[x][1]],sum[t[x][1]]+min(A[x],A[x]+rmin[t[x][0]])); } void re_repair(int x) { re[x]^=1;swap(lmin[x],lmax[x]);lmin[x]=-lmin[x];lmax[x]=-lmax[x]; swap(rmin[x],rmax[x]);rmin[x]=-rmin[x];rmax[x]=-rmax[x]; A[x]=-A[x]; } void g_repair(int x) { g[x]^=1;swap(lmin[x],rmin[x]);swap(lmax[x],rmax[x]); } void pushdown(int x) { if(g[x]) { g_repair(t[x][0]);g_repair(t[x][1]); swap(t[x][0],t[x][1]); g[x]=0; } if(re[x]) { re_repair(t[x][0]);re_repair(t[x][1]); re[x]=0; } } void build(int fa,int &x,int l,int r) { if(l>r)return; int mid=(l+r)>>1; x=Node(fa,a[mid]); build(x,t[x][0],l,mid-1); build(x,t[x][1],mid+1,r); count(x); } void rotate(int x) { int k=x==t[f[x]][1]; int y=f[x]; t[y][k]=t[x][!k];f[t[x][!k]]=y; if(f[y])t[f[y]][y==t[f[y]][1]]=x;f[x]=f[y];f[y]=x; t[x][!k]=y; lmin[x]=lmin[y];lmax[x]=lmax[y];rmin[x]=rmin[y];rmax[x]=rmax[y];sum[x]=sum[y];s[x]=s[y]; count(y); } void splay(int r,int x) { for(int fa=f[r];f[x]!=fa;) { if(f[f[x]]==fa){rotate(x);break;} int X=x==t[f[x]][1],Y=f[x]==t[f[f[x]]][1]; if(X^Y)rotate(x),rotate(x); else rotate(f[x]),rotate(x); } } void find(int &r,int k) { for(int x=r;x;) { if(k<=t[x][0])x=t[x][0]; if(k==t[x][0]+1){splay(r,x),r=x;break;} k-=t[x][0]+1;x=t[x][1]; } } void reserve() { int l,r; scanf("%d%d",&l,&r); find(root,l);find(t[root][1],r-l+2); int y=t[t[root][1]][0]; re_repair(y); count(t[root][1]);count(root); } void g_reserve() { int l,r; scanf("%d%d",&l,&r); find(root,l);find(t[root][1],r-l+2); int y=t[t[root][1]][0]; g_repair(y); count(t[root][1]);count(root); } void ask() { int l,r; scanf("%d%d",&l,&r); find(root,l);find(t[root][1],r-l+2); int y=t[t[root][1]][0]; printf("%d\n",(-lmin[y]+1)/2+(rmax[y]+1)/2); } int main() { scanf("%d%d%s",&n,&q,str+1); for(int i=1;i<=n;i++)if(str[i]==‘(‘)a[i]=1;else a[i]=-1; build(0,root,0,n+1); for(int i=1;i<=q;i++) { int x; scanf("%d",&x); if(x==0)ask(); if(x==1)reserve(); if(x==2)g_reserve(); } return 0; }
try
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。