美洲杯波胆_美洲杯波胆赔率
做最好的网站
来自 计算机教程 2019-09-24 00:10 的文章
当前位置: 美洲杯波胆 > 计算机教程 > 正文

bzoj2209 [ JSOI2011 ],bzoj2209jsoi2011

将左括号记为1,右括号记为-1,则一个合法的括号序列满足所有的前缀和非负。

bzoj2209 [ JSOI2011 ],bzoj2209jsoi2011

将左括号记为1,右括号记为-1,则一个合法的括号序列满足所有的前缀和非负。

用splay维护。

代码:

男篮世界杯波胆 1

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 #define N 100010
  7 inline char nc(){
  8     static char buf[100000],*p1=buf,*p2=buf;
  9     if(p1==p2){
 10         p2=(p1=buf) fread(buf,1,100000,stdin);
 11         if(p1==p2)return EOF;
 12     }
 13     return *p1  ;
 14 }
 15 inline void Read(int& x){
 16     char c=nc();
 17     for(;c<'0'||c>'9';c=nc());
 18     for(x=0;c>='0'&&c<='9';x=(x<<3) (x<<1) c-48,c=nc());
 19 }
 20 char ss[30];
 21 int Len;
 22 inline void Print(int x){
 23     if(x==0)putchar(48);
 24     for(Len=0;x;x/=10)ss[  Len]=x;
 25     for(;Len;)putchar(ss[Len--] 48);putchar('n');
 26 }
 27 int i,j,k,n,m,s[N],ch[N][2],f[N],Rt,c1[N][2],c2[N][2],Sum[N],a[N],x,y,z;
 28 bool r[N],b[N];
 29 char S[N];
 30 inline int Min(int x,int y){
 31     return x<y?x:y;
 32 }
 33 inline int Max(int x,int y){
 34     return x<y?y:x;
 35 }
 36 inline int Abs(int x){
 37     return x<0?-x:x;
 38 }
 39 inline void Pushup(int x){
 40     s[x]=s[ch[x][0]] s[ch[x][1]] 1;
 41     Sum[x]=Sum[ch[x][0]] Sum[ch[x][1]] a[x];
 42     c1[x][0]=Min(Sum[ch[x][0]] a[x],Min(c1[ch[x][0]][0],Sum[ch[x][0]] a[x] c1[ch[x][1]][0]));
 43     c1[x][1]=Max(Sum[ch[x][0]] a[x],Max(c1[ch[x][0]][1],Sum[ch[x][0]] a[x] c1[ch[x][1]][1]));
 44     c2[x][0]=Min(Sum[ch[x][1]] a[x],Min(c2[ch[x][1]][0],Sum[ch[x][1]] a[x] c2[ch[x][0]][0]));
 45     c2[x][1]=Max(Sum[ch[x][1]] a[x],Max(c2[ch[x][1]][1],Sum[ch[x][1]] a[x] c2[ch[x][0]][1]));
 46 }
 47 inline void Update_rev(int x){
 48     if(x==0)return;
 49     swap(c1[x][0],c2[x][0]);
 50     swap(c1[x][1],c2[x][1]);
 51     swap(ch[x][0],ch[x][1]);
 52     r[x]^=1;
 53 }
 54 inline void Update_ops(int x){
 55     if(x==0)return;
 56     a[x]*=-1;Sum[x]*=-1;
 57     swap(c1[x][0],c1[x][1]);
 58     swap(c2[x][0],c2[x][1]);
 59     c1[x][0]*=-1;c1[x][1]*=-1;
 60     c2[x][0]*=-1;c2[x][1]*=-1;
 61     b[x]^=1;
 62 }
 63 inline void Pushdown(int x){
 64     if(r[x]){
 65         Update_rev(ch[x][0]);Update_rev(ch[x][1]);
 66         r[x]=0;
 67     }
 68     if(b[x]){
 69         Update_ops(ch[x][0]);Update_ops(ch[x][1]);
 70         b[x]=0;
 71     }
 72 }
 73 inline void Build(){
 74     ch[Rt=1][1]=2;
 75     for(i=2;i<=n 1;i  ){f[i]=i-1;ch[i][1]=i 1;}
 76     f[n 2]=n 1;s[n 2]=1;s[n 1]=2;c1[n 1][0]=c1[n 1][1]=c2[n 1][0]=c2[n 1][1]=a[n];
 77     for(i=n;i>=1;i--)Pushup(i);
 78 }
 79 inline int Get(int x){return ch[f[x]][1]==x;}
 80 inline void Rotate(int x){
 81     bool d=Get(x);int y=f[x];
 82     if(f[y])ch[f[y]][Get(y)]=x;
 83     ch[y][d]=ch[x][d^1];f[ch[y][d]]=y;
 84     f[x]=f[y];f[y]=x;ch[x][d^1]=y;
 85     Pushup(y);
 86 }
 87 inline void P(int x,int y){
 88     if(f[x]!=y)P(f[x],y);
 89     Pushdown(x);
 90 }
 91 inline void Splay(int x,int y){
 92     P(x,y);
 93     for(;f[x]!=y;Rotate(x))
 94     if(f[f[x]]!=y)Rotate(Get(x)==Get(f[x])?f[x]:x);
 95     if(y==0)Rt=x;Pushup(x);
 96 }
 97 inline int Find(int x,int y){
 98     Pushdown(x);
 99     if(s[ch[x][0]] 1==y)return x;
100     if(s[ch[x][0]]>=y)return Find(ch[x][0],y);
101     return Find(ch[x][1],y-s[ch[x][0]]-1); 
102 }
103 inline int Get_result(int x){
104     int t=-c1[x][0];
105     int Res=(t>>1) t%2;
106     t=(Res<<1) Sum[x];
107     Res =Abs(t)>>1;
108     return Res;
109 }
110 inline int Query(int x,int y){
111     int a1=Find(Rt,x-1),a2=Find(Rt,y 1);
112     Splay(a2,0);Splay(a1,Rt);
113     return Get_result(ch[a1][1]);
114 }
115 inline void Update1(int x,int y){
116     int a1=Find(Rt,x-1),a2=Find(Rt,y 1);
117     Splay(a2,0);Splay(a1,Rt);
118     Update_ops(ch[a1][1]);Pushup(a1);Pushup(a2);
119 }
120 inline void Update2(int x,int y){
121     int a1=Find(Rt,x-1),a2=Find(Rt,y 1);
122     Splay(a2,0);Splay(a1,Rt);
123     Update_rev(ch[a1][1]);Pushup(a1);Pushup(a2);
124 }
125 int main(){
126     scanf("%d%d",&n,&m);
127     scanf("%s",S 1);
128     for(i=1;i<=n;i  )
129     if(S[i]=='(')a[i 1]=1;else a[i 1]=-1;
130     Build();
131     while(m--){
132         Read(x);Read(y);Read(z);y  ;z  ;
133         if(x==0)Print(Query(y,z));else
134         if(x==1)Update1(y,z);else if(x==2)Update2(y,z);
135     }
136     return 0;
137 }

bzoj2209

 

http://www.bkjia.com/cjjc/1202930.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1202930.htmlTechArticlebzoj2209 [男篮世界杯波胆, JSOI2011 ],bzoj2209jsoi2011 将左括号记为1,右括号记为-1,则一个合法的括号序列满足所有的前缀和非负。 用splay维护。 代码: 1 #in...

用splay维护。

代码:

男篮世界杯波胆 2男篮世界杯波胆 3

本文由美洲杯波胆发布于计算机教程,转载请注明出处:bzoj2209 [ JSOI2011 ],bzoj2209jsoi2011

关键词: