刷题

今天上了一天的树，然后就下不来了，（根本就没上去吧）

打了道256行的SpalySplay，然后在COGS上过了道4星半的[NOI2005]维护数列，然后——我发现！@#在内网上竟然E了（喵喵喵？），然后，喵的COGS上是3s 256MB，其他OJ上全是1s 64MB= =

莫名尴尬= =

生活

颓了一天= =

刷SpalySplay板子刷到死= =，然后只能颓某黄学长的2048以示敬意= =

然后就颓成了这个鬼样子= =

不过SpalySplay真的难打= =，随手一打就是这个鬼样子= =

1 #include
      
         2 #include
       
          3 #include
        
           4 using namespace std;  5 inline int read(){  6     int sum(0),f(1);  7     char ch(getchar());  8     for(;ch<'0'||ch>'9';ch=getchar())  9         if(ch=='-') 10             f=-1; 11     for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar()); 12     return sum*f; 13 } 14 int ch[4000001][2],f[4000001],key[4000001],size[4000001]; 15 int sum[4000001],maxl[4000001],maxr[4000001],maxn[4000001]; 16 int root,sz; 17 bool lazy[4000001],rev[4000001]; 18 inline void clear(int x){ 19     f[x]=ch[x][0]=ch[x][1]=size[x]=key[x]=sum[x]=0; 20     lazy[x]=rev[x]=maxl[x]=maxr[x]=0; 21     maxn[x]=-1000000000; 22 } 23 inline int get(int x){ 24     return ch[f[x]][1]==x; 25 } 26 inline int my_max(int a,int b){ 27     return a>b?a:b; 28 } 29 inline void swp(int &a,int &b){ 30     a^=b; 31     b^=a; 32     a^=b; 33 } 34 inline void update(int x){ 35     int l(ch[x][0]),r(ch[x][1]); 36     sum[x]=sum[l]+sum[r]+key[x]; 37     size[x]=size[l]+size[r]+1; 38     maxn[x]=maxl[r]+key[x]+maxr[l]; 39     if(l) 40         maxn[x]=my_max(maxn[x],maxn[l]); 41     if(r) 42         maxn[x]=my_max(maxn[x],maxn[r]); 43     maxl[x]=my_max(maxl[l],sum[l]+key[x]+maxl[r]); 44     maxr[x]=my_max(maxr[r],sum[r]+key[x]+maxr[l]); 45 } 46 inline void pushdown(int x){ 47     int l(ch[x][0]),r(ch[x][1]); 48     if(lazy[x]){ 49         rev[x]=lazy[x]=0; 50         if(l){ 51             lazy[l]=1; 52             key[l]=key[x]; 53             sum[l]=key[l]*size[l]; 54         } 55         if(r){ 56             lazy[r]=1; 57             key[r]=key[x]; 58             sum[r]=key[r]*size[r]; 59         } 60         if(key[x]>=0){ 61             if(l) 62                 maxl[l]=maxr[l]=maxn[l]=sum[l]; 63             if(r) 64                 maxl[r]=maxr[r]=maxn[r]=sum[r]; 65         } 66         else{ 67             if(l){ 68                 maxl[l]=maxr[l]=0; 69                 maxn[l]=key[l]; 70             } 71             if(r){ 72                 maxl[r]=maxr[r]=0; 73                 maxn[r]=key[r]; 74             } 75         } 76     } 77     if(rev[x]){ 78         rev[x]=0; 79         rev[l]^=1; 80         rev[r]^=1; 81         swp(maxl[l],maxr[l]); 82         swp(maxl[r],maxr[r]); 83         swp(ch[l][0],ch[l][1]); 84         swp(ch[r][0],ch[r][1]); 85     } 86 } 87 inline void rotate(int x){ 88     int p(f[x]),g(f[p]),which(get(x)); 89     pushdown(p); 90     pushdown(x); 91     ch[p][which]=ch[x][which^1]; 92     f[ch[p][which]]=p; 93     ch[x][which^1]=p; 94     f[p]=x; 95     f[x]=g; 96     if(g) 97         ch[g][ch[g][1]==p]=x; 98     update(p); 99     update(x);100 }101 inline void splay(int x,int y){102     pushdown(x);103     for(int fa=f[x];fa!=y;rotate(x),fa=f[x])104         if(f[fa]!=y)105             rotate(get(fa)==get(x)?fa:x);106     if(!y)107         root=x;108 }109 inline int find(int x){110     int now(root);111     while(1){112         pushdown(now);113         if(x<=size[ch[now][0]])114             now=ch[now][0];115         else{116             int tmp(size[ch[now][0]]+1);117             if(x<=tmp)118                 return now;119             x-=tmp;120             now=ch[now][1];121         }122     }123 }124 inline void build(int l,int r,int fa){125     if(l>r)126         return ;127     if(l==r){128         f[l]=fa;129         size[l]=1;130         sum[l]=key[l];131         if(key[l]>=0)132             maxl[l]=maxr[l]=maxn[l]=key[l];133         else{134             maxl[l]=maxr[l]=0;135             maxn[l]=key[l];136         }137         if(fa){138             if(l
         
          >1);146     build(l,mid-1,mid);147     build(mid+1,r,mid);148     f[mid]=fa;149     update(mid);150     if(fa){151         if(mid
          
           >1;175     int all(n+2);176     while(m--){
    //cout<<'*'<
           
            <
            
             >1);187 f[rt]=y;188 ch[y][0]=rt;189 update(y);190 update(x);191 all+=tot;192 continue;193 }194 if(op[0]=='D'){195 int pos(read()),tot(read());196 int x(find(pos)),y(find(pos+tot+1));197 splay(x,0);198 splay(y,x);199 erase(ch[y][0]);200 update(y);201 update(x);202 all-=tot;203 continue;204 }205 if(op[0]=='R'){206 int pos(read()),tot(read());207 int x(find(pos)),y(find(pos+tot+1));208 splay(x,0);209 splay(y,x);210 int z(ch[y][0]);211 if(!lazy[z]){212 rev[z]^=1;213 swp(ch[z][0],ch[z][1]);214 swp(maxl[z],maxr[z]);215 update(y);216 update(x);217 }218 continue;219 }220 if(op[0]=='G'){221 int pos(read()),tot(read());222 int x(find(pos)),y(find(pos+tot+1));223 splay(x,0);224 splay(y,x);225 printf("%d\n",sum[ch[y][0]]);226 continue;227 }228 if(op[2]=='K'){229 int pos(read()),tot(read()),c(read());230 int x(find(pos)),y(find(pos+tot+1));231 splay(x,0);232 splay(y,x);233 int z(ch[y][0]);234 lazy[z]=1;235 key[z]=c;236 sum[z]=size[z]*c;237 if(c>=0)238 maxl[z]=maxr[z]=maxn[z]=sum[z];239 else{240 maxl[z]=maxr[z]=0;241 maxn[z]=c;242 }243 update(y);244 update(x);245 }246 if(op[2]=='X'){247 int x(find(1)),y(find(all));248 splay(x,0);249 splay(y,x);250 printf("%d\n",maxn[ch[y][0]]);251 }252 }253 return 0;254 }255 int K(gg());256 int main(){;}
            
           
          
         
        
       
      

手累啊

Song

《Not Afraid》——Eminem

I'm not afraid

To take a stand

Everybody come take my hand 

We'll walk to the route together

Through the storm

Whatever weather,cold or warm

Just lettin' you know that

You're not alone 

Holla if you fell like you've been down on the same road

 

And I just cannot keep livin' in this way

So starting today

We'll break out of this cage

I'm standing up

I'ma face my demons 

I'm manning up

I'ma hold my ground

I've had enough

Now I'm fed up

It's time to get my life back right now

I just cannot keep livin' in this way