刷题
今天上了一天的树，然后就下不来了，（根本就没上去吧）
打了道256行的SpalySplay，然后在COGS上过了道4星半的[NOI2005]维护数列，然后——我发现！@#在内网上竟然E了（喵喵喵？），然后，喵的COGS上是3s 256MB，其他OJ上全是1s 64MB= =
莫名尴尬= =
生活
颓了一天= =
刷SpalySplay板子刷到死= =，然后只能颓某黄学长的2048以示敬意= =
然后就颓成了这个鬼样子= =
不过SpalySplay真的难打= =，随手一打就是这个鬼样子= =
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
int sum(),f();
char ch(getchar());
for(;ch<''||ch>'';ch=getchar())
if(ch=='-')
f=-;
for(;ch>=''&&ch<='';sum=sum*+(ch^),ch=getchar());
return sum*f;
}
int ch[][],f[],key[],size[];
int sum[],maxl[],maxr[],maxn[];
int root,sz;
bool lazy[],rev[];
inline void clear(int x){
f[x]=ch[x][]=ch[x][]=size[x]=key[x]=sum[x]=;
lazy[x]=rev[x]=maxl[x]=maxr[x]=;
maxn[x]=-;
}
inline int get(int x){
return ch[f[x]][]==x;
}
inline int my_max(int a,int b){
return a>b?a:b;
}
inline void swp(int &a,int &b){
a^=b;
b^=a;
a^=b;
}
inline void update(int x){
int l(ch[x][]),r(ch[x][]);
sum[x]=sum[l]+sum[r]+key[x];
size[x]=size[l]+size[r]+;
maxn[x]=maxl[r]+key[x]+maxr[l];
if(l)
maxn[x]=my_max(maxn[x],maxn[l]);
if(r)
maxn[x]=my_max(maxn[x],maxn[r]);
maxl[x]=my_max(maxl[l],sum[l]+key[x]+maxl[r]);
maxr[x]=my_max(maxr[r],sum[r]+key[x]+maxr[l]);
}
inline void pushdown(int x){
int l(ch[x][]),r(ch[x][]);
if(lazy[x]){
rev[x]=lazy[x]=;
if(l){
lazy[l]=;
key[l]=key[x];
sum[l]=key[l]*size[l];
}
if(r){
lazy[r]=;
key[r]=key[x];
sum[r]=key[r]*size[r];
}
if(key[x]>=){
if(l)
maxl[l]=maxr[l]=maxn[l]=sum[l];
if(r)
maxl[r]=maxr[r]=maxn[r]=sum[r];
}
else{
if(l){
maxl[l]=maxr[l]=;
maxn[l]=key[l];
}
if(r){
maxl[r]=maxr[r]=;
maxn[r]=key[r];
}
}
}
if(rev[x]){
rev[x]=;
rev[l]^=;
rev[r]^=;
swp(maxl[l],maxr[l]);
swp(maxl[r],maxr[r]);
swp(ch[l][],ch[l][]);
swp(ch[r][],ch[r][]);
}
}
inline void rotate(int x){
int p(f[x]),g(f[p]),which(get(x));
pushdown(p);
pushdown(x);
ch[p][which]=ch[x][which^];
f[ch[p][which]]=p;
ch[x][which^]=p;
f[p]=x;
f[x]=g;
if(g)
ch[g][ch[g][]==p]=x;
update(p);
update(x);
}
inline void splay(int x,int y){
pushdown(x);
for(int fa=f[x];fa!=y;rotate(x),fa=f[x])
if(f[fa]!=y)
rotate(get(fa)==get(x)?fa:x);
if(!y)
root=x;
}
inline int find(int x){
int now(root);
while(){
pushdown(now);
if(x<=size[ch[now][]])
now=ch[now][];
else{
int tmp(size[ch[now][]]+);
if(x<=tmp)
return now;
x-=tmp;
now=ch[now][];
}
}
}
inline void build(int l,int r,int fa){
if(l>r)
return ;
if(l==r){
f[l]=fa;
size[l]=;
sum[l]=key[l];
if(key[l]>=)
maxl[l]=maxr[l]=maxn[l]=key[l];
else{
maxl[l]=maxr[l]=;
maxn[l]=key[l];
}
if(fa){
if(l<fa)
ch[fa][]=l;
else
ch[fa][]=l;
}
return;
}
int mid((l+r)>>);
build(l,mid-,mid);
build(mid+,r,mid);
f[mid]=fa;
update(mid);
if(fa){
if(mid<fa)
ch[fa][]=mid;
else
ch[fa][]=mid;
}
}
inline void erase(int x){
if(!x)
return;
erase(ch[x][]);
erase(ch[x][]);
clear(x);
}
char op[];
inline int gg(){
freopen("seq2005.in","r",stdin);
freopen("seq2005.out","w",stdout);
int n(read()),m(read());
key[++sz]=-;
for(int i=;i<=n;i++)
key[++sz]=read();
key[++sz]=-;
build(,n+,);
root=(n+)>>;
int all(n+);
while(m--){//cout<<'*'<<m<<endl;
scanf("%s",op);
if(op[]=='I'){
int pos(read()+),tot(read()),old(sz+);
int x(find(pos)),y(find(pos+));
splay(x,);
splay(y,x);
for(int i=;i<=tot;i++)
key[++sz]=read();
build(old,sz,);
int rt((old+sz)>>);
f[rt]=y;
ch[y][]=rt;
update(y);
update(x);
all+=tot;
continue;
}
if(op[]=='D'){
int pos(read()),tot(read());
int x(find(pos)),y(find(pos+tot+));
splay(x,);
splay(y,x);
erase(ch[y][]);
update(y);
update(x);
all-=tot;
continue;
}
if(op[]=='R'){
int pos(read()),tot(read());
int x(find(pos)),y(find(pos+tot+));
splay(x,);
splay(y,x);
int z(ch[y][]);
if(!lazy[z]){
rev[z]^=;
swp(ch[z][],ch[z][]);
swp(maxl[z],maxr[z]);
update(y);
update(x);
}
continue;
}
if(op[]=='G'){
int pos(read()),tot(read());
int x(find(pos)),y(find(pos+tot+));
splay(x,);
splay(y,x);
printf("%d\n",sum[ch[y][]]);
continue;
}
if(op[]=='K'){
int pos(read()),tot(read()),c(read());
int x(find(pos)),y(find(pos+tot+));
splay(x,);
splay(y,x);
int z(ch[y][]);
lazy[z]=;
key[z]=c;
sum[z]=size[z]*c;
if(c>=)
maxl[z]=maxr[z]=maxn[z]=sum[z];
else{
maxl[z]=maxr[z]=;
maxn[z]=c;
}
update(y);
update(x);
}
if(op[]=='X'){
int x(find()),y(find(all));
splay(x,);
splay(y,x);
printf("%d\n",maxn[ch[y][]]);
}
}
return ;
}
int K(gg());
int main(){;}
手累啊
Song
《Not Afraid》——Eminem