●个人感觉：
- 代码长；
- 函数多；
- （很套路）；
- （很强的Splay，无愧于“区间王”）
●NOI2005维修数列
- 一个可以当模板学习的题，包含了众多操作（函数）：
- 区间插入，删除，更新，翻转，询问信息以及”回收空间”(名字很刚)等。
- update()pushdown() rotate() splay() build() find() split() insert() rec() erase() query() rever() modify()还有main()
- 建议初学Splay者打一打；
- 代码：
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define N 1000005
using namespace std;
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,m,rt,cnt,k,len,val; char ch[];
int a[N],id[N],fa[N],c[N][];
int sum[N],siz[N],v[N],mx[N],lx[N],rx[N];
bool tag[N],rev[N];
queue<int> q;
void update(int x)
{
int l=c[x][],r=c[x][];
sum[x]=sum[l]+sum[r]+v[x];
siz[x]=siz[l]+siz[r]+;
mx[x]=max(mx[l],mx[r]);
mx[x]=max(mx[x],rx[l]+v[x]+lx[r]);
lx[x]=max(lx[l],sum[l]+v[x]+lx[r]);
rx[x]=max(rx[r],sum[r]+v[x]+rx[l]);
}
void pushdown(int x)
{
int l=c[x][],r=c[x][];
if(tag[x])
{
rev[x]=tag[x]=;
if(l) tag[l]=,v[l]=v[x],sum[l]=v[l]*siz[l];
if(r) tag[r]=,v[r]=v[x],sum[r]=v[r]*siz[r];
if(v[x]>=)
{
if(l) lx[l]=rx[l]=mx[l]=sum[l];
if(r) lx[r]=rx[r]=mx[r]=sum[r];
}
else
{
if(l)lx[l]=rx[l]=,mx[l]=v[x];
if(r)lx[r]=rx[r]=,mx[r]=v[x];
}
}
if(rev[x])
{
rev[x]^=;rev[l]^=;rev[r]^=;
swap(lx[l],rx[l]);swap(lx[r],rx[r]);
swap(c[l][],c[l][]);swap(c[r][],c[r][]);
}
}
void rotate(int x,int &k)//Ðýת£¨µ¥£©
{
int y=fa[x],z=fa[y];
int l=(x!=c[y][]),r=l^;
if(y==k) k=x;
else c[z][y!=c[z][]]=x;
fa[x]=z; fa[y]=x; fa[c[x][r]]=y;
c[y][l]=c[x][r]; c[x][r]=y;
update(y); update(x);
}
void splay(int x,int &k)
{
int y,z;
while(x!=k)
{
y=fa[x],z=fa[y];
if(y!=k)
{
if(c[y][]==x^c[z][]==y) rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
void build(int l,int r,int f)
{
if(l>r) return;
int mid=l+r>>,now=id[mid],last=id[f];
if(l==r)
{
sum[now]=a[l];
siz[now]=;
tag[now]=rev[now]=;
if(a[l]>=)lx[now]=rx[now]=mx[now]=a[l];
else lx[now]=rx[now]=,mx[now]=a[l];
}
build(l,mid-,mid);build(mid+,r,mid);
v[now]=a[mid];
fa[now]=last;
c[last][mid>=f]=now;
update(now);
}
int find(int k,int x)
{
pushdown(k);
if(siz[c[k][]]+==x) return k;
if(siz[c[k][]]>=x) return find(c[k][],x);
else return find(c[k][],x-siz[c[k][]]-);
}
int split(int k,int len)
{
int x=find(rt,k),y=find(rt,k+len+);
splay(x,rt);splay(y,c[x][]);
return c[y][];
}
void insert(int k,int len)
{
for(int i=;i<=len;i++)
if(!q.empty()) id[i]=q.front(),q.pop();
else id[i]=++cnt;
for(int i=;i<=len;i++) a[i]=read();
build(,len,);
int x=id[+len>>];
int z=find(rt,k+),y=find(rt,k+);//µÚһλΪ-inf
splay(z,rt); splay(y,c[z][]);
fa[x]=y; c[y][]=x;
update(y);update(fa[y]);
}
void rec(int x)
{
if(!x) return;
int l=c[x][],r=c[x][];
rec(l); rec(r);
q.push(x);
fa[x]=c[x][]=c[x][]=;
tag[x]=rev[x]=;
}
void erase(int k,int len)
{
int x=split(k,len),y=fa[x];
rec(x); c[y][]=;
update(y);update(fa[y]);
}
void query(int k,int len)
{
int x=split(k,len);
printf("%d\n",sum[x]);
}
void rever(int k,int len)//Çø¼ä·×ª
{
int x=split(k,len),y=fa[x];
if(!tag[x])
{
rev[x]^=;
swap(lx[x],rx[x]);
swap(c[x][],c[x][]);
update(y);update(fa[y]);
}
}
void modify(int k,int len,int val)
{
int x=split(k,len),y=fa[x];
tag[x]=; v[x]=val;
sum[x]=v[x]*siz[x];
if(v[x]>=) lx[x]=rx[x]=mx[x]=sum[x];
else lx[x]=rx[x]=,mx[x]=v[x];
update(y);update(fa[y]);
}
int main()
{
n=read();m=read();
mx[]=a[]=a[n+]=-inf; id[]=; id[n+]=n+;
for(int i=;i<=n+;i++) a[i]=read(),id[i]=i;
build(,n+,);
rt=n+>>; cnt=n+;
while(m-->)
{
scanf("%s",ch);
if(ch[]!='M'||ch[]!='X') k=read(),len=read();
if(ch[]=='I') insert(k,len);
if(ch[]=='D') erase(k,len);
if(ch[]=='R') rever(k,len);
if(ch[]=='G') query(k,len);
if(ch[]=='M')
{
if(ch[]=='X')printf("%d\n",mx[rt]);
else val=read(),modify(k,len,val);
}
}
return ;
}I'm here!
●宠物收养所（codves 1285）
- 用Splay维护一个权值树，每次进行查找，删除或插入操作,较简单。
- 注意要mod
- 代码：
-
#include<cstdio>
#include<iostream>
using namespace std;
int rt,size,n,t1,t2,kind;
long long ans;
int fa[],tr[][],num[];
void rotate(int x,int &k)
{
int y=fa[x],z=fa[y];
int l=(x!=tr[y][]),r=l^;
if(y!=k) tr[z][(y!=tr[z][])]=x;
else k=x;
fa[x]=z;fa[y]=x;fa[tr[x][r]]=y;
tr[y][l]=tr[x][r];tr[x][r]=y;
}
void splay(int x,int &k)
{
int y,z;
while(x!=k)
{
y=fa[x],z=fa[y];
if(y!=k)
{
if((x==tr[y][])^(y==tr[z][]))rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
void ins(int &k,int x,int last)
{
if(k==){size++;k=size;num[k]=x;fa[k]=last;splay(k,rt);return;}
if(x<num[k])ins(tr[k][],x,k);else ins(tr[k][],x,k);
}
void find_pre(int k,int x)
{
if(k==) return;
if(num[k]<=x){t1=k;find_pre(tr[k][],x);}
else find_pre(tr[k][],x);
}
void find_bac(int k,int x)
{
if(k==) return;
if(num[k]>=x){t2=k;find_bac(tr[k][],x);}
else find_bac(tr[k][],x);
}
void del(int x)
{
splay(x,rt);
if(tr[x][]*tr[x][]==) rt=tr[x][]+tr[x][];
else
{
int k=tr[x][];
while(tr[k][])k=tr[k][];
tr[k][]=tr[x][];fa[tr[x][]]=k;
rt=tr[x][];
}
fa[rt]=;
}
int main()
{
scanf("%d",&n);int f,x;
for(int i=;i<=n;i++)
{
scanf("%d%d",&f,&x);
if(!rt){kind=f;ins(rt,x,);}
else if(kind==f) ins(rt,x,);
else
{
t1=t2=-;
find_pre(rt,x);find_bac(rt,x);
if(t1==-){ans+=num[t2]-x;ans%=;del(t2);}
else if(t2==-){ans+=x-num[t1];ans%=;del(t1);}
else
{
if(num[t2]-x>=x-num[t1]) ans+=x-num[t1],del(t1);// µ± a-b==a+bʱ£¬Ñ¡a-b
else ans+=num[t2]-x,del(t2); ans%=;
} } }
printf("%d",ans);
return ;
}I'm still here!
#include<iostream>
#include<cstdio>
#define MAXN 80005
#define INF 0x3f3f3f3f
using namespace std;
int fa[MAXN],ch[MAXN][],num[MAXN];
int rk,root,tot,t1,t2;
void rotate(int x,int &k)
{
int y=fa[x],z=fa[y];
int l=ch[y][]==x,r=^l;
if(y==k) k=x;
else ch[z][ch[z][]==y]=x;
fa[ch[x][r]]=y; fa[y]=x; fa[x]=z;
ch[y][l]=ch[x][r]; ch[x][r]=y;
}
void splay(int x,int &k)
{
int y,z;
while(x!=k)
{
y=fa[x]; z=fa[y];
if(y!=k) ((ch[z][]==y)^(ch[y][]==x)) ? rotate(x,k):rotate(y,k);
rotate(x,k);
}
}
void insert(int &k,int x,int last)
{
if(!k){k=++tot;fa[k]=last;num[k]=x;splay(k,root);return;}
insert(ch[k][x>=num[k]],x,k);
}
void del(int x)
{
splay(x,root);
if(!(ch[root][]*ch[root][])) root=ch[root][]+ch[root][];
else
{
int p=ch[root][];
while(ch[p][]) p=ch[p][];
fa[ch[root][]]=p; ch[p][]=ch[root][];
root=ch[root][];
}
fa[root]=;
}
void find_fro(int k,int x)
{
if(!k) return;
if(num[k]<=x) t1=k,find_fro(ch[k][],x);
else find_fro(ch[k][],x);
}
void find_bac(int k,int x)
{
if(!k) return;
if(num[k]>=x) t2=k,find_bac(ch[k][],x);
else find_bac(ch[k][],x);
}
int main()
{
int n,ans=,k,a,tmp,p; scanf("%d",&n);
while(n--)
{
scanf("%d%d",&k,&a);
if(!root||rk==k) rk=k,insert(root,a,);
else
{
t1=INF; t2=INF; tmp=INF; p=;
find_fro(root,a);
find_bac(root,a);
if(t1!=INF&&tmp>a-num[t1]) p=t1,tmp=a-num[t1];
if(t2!=INF&&tmp>num[t2]-a) p=t2,tmp=num[t2]-a;
if(p) del(p);
ans=(ans+tmp)%;
}
}
printf("%d",ans);
return ;
}7.27 注意！的优先级大于*（乘号）啊！！！QAQ
●营业额统计（codevs 1296）
- 用Splay维护营业额（权值树），每次先查找小于今日营业额的最大值和大于今日营业额的最小值，（也可以有相等的请况），然后取最优解加入ans中，在插入今日营业额；
- 和上题有点像
- 但不知我的代码为何在codevs上要TLE一组，在COGS上要WA一组和TLE一组（求助！）
- 代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define N 40000
using namespace std;
int fa[N],ch[N][],num[N];
int n,a,t1,t2,root,sz;
void rotate(int x,int &k)
{
int y,z,l,r;
z=fa[y=fa[x]];
r=^(l=(ch[y][]==x));
if(y==k)k=x;
else ch[z][ch[z][]==y]=x;
fa[x]=z; fa[y]=x; fa[ch[x][r]]=y;
ch[y][l]=ch[x][r];ch[x][r]=y;
}
void splay(int x,int &k)
{
int y,z;
while(x!=k)
{
z=fa[y=fa[x]];
if(y!=k) ch[z][]==y^ch[y][]==x?rotate(x,k):rotate(y,k);
rotate(x,k);
}
}
void insert(int x,int last,int &k)
{
if(!k)
{
k=++sz;
num[sz]=x;
fa[k]=last;
splay(k,root);
return;
}
if(num[k]==x)return;
insert(x,k,ch[k][x>num[k]]);
}
void find_fro(int x,int k)
{
if(!k)return;//¡ñ¡ð¡ð
if(num[k]<=x){t1=k;find_fro(x,ch[k][]);}
else find_fro(x,ch[k][]);
}
void find_bac(int x,int k)
{
if(!k)return;
if(num[k]>=x){t2=k;find_bac(x,ch[k][]);}
else find_bac(x,ch[k][]);
}
int main()
{
int ans=;
scanf("%d%d",&n,&ans);
insert(ans,,root);n--;
while(n--)
{
scanf("%d",&a);
t1=t2=-; int tmp=0x3f3f3f3f;
find_fro(a,root);
find_bac(a,root);
if(t1!=-) tmp=min(tmp,a-num[t1]);
if(t2!=-) tmp=min(tmp,num[t2]-a);
insert(a,,root);
ans+=tmp;
}
printf("%d",ans);
return ;
}I'm here,too!
●反转卡片（codevs 1743）
- 一个区间翻转的题，要用到lazy标记,较简单。
- 代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define N 300005
using namespace std;
int n,cnt,rt;
int a[N],c[N][],fa[N],siz[N],rev[N],num[N];
int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void update(int k)
{
siz[k]=siz[c[k][]]+siz[c[k][]]+;
}
void pushdown(int k)
{
if(!rev[k]) return;
int l=c[k][],r=c[k][];
rev[l]^=; rev[r]^=; rev[k]^=;
swap(c[l][],c[l][]);
swap(c[r][],c[r][]);
}
int find(int x,int k)
{
pushdown(k);
if(siz[c[k][]]+==x) return k;
else if(siz[c[k][]]+>x) return find(x,c[k][]);
else return find(x-siz[c[k][]]-,c[k][]);
}
void rotate(int x,int &k)
{
int y=fa[x],z=fa[y];
int l=c[y][]!=x,r=l^;
if(y==k) k=x;
else c[z][c[z][]!=y]=x;
fa[x]=z; fa[y]=x; fa[c[x][r]]=y;
c[y][l]=c[x][r]; c[x][r]=y;
update(y); update(x);
}
void splay(int x,int &k)
{
int y,z;
while(x!=k)
{
y=fa[x],z=fa[y];
if(y!=k)
{
if(c[z][]==y^c[y][]==x) rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
int split(int k,int len)
{
int x=find(k,rt),y=find(k+len+,rt);
splay(x,rt); splay(y,c[x][]);
return c[y][];
}
void rever(int k,int len)
{
int x=split(k,len);
rev[x]^=;
swap(c[x][],c[x][]);
}
void build(int l,int r,int f)
{
if(l>r) return;
int mid=l+r>>;
c[f][mid>=f]=mid;
fa[mid]=f;
num[mid]=a[mid];
build(l,mid-,mid);
build(mid+,r,mid);
update(mid);
}
int main()
{
n=read();
a[]=a[n+]=;
for(int i=;i<=n+;i++) a[i]=read();
build(,n+,);
rt=n+>>;
int len=num[find(,rt)];
while(len!=)
{
cnt++;
rever(,len);
len=num[find(,rt)];
}
printf("%d",cnt);
return ;
}I'm here as well!
●蚱蜢（codevs 1343）
- Splay维护蚱蜢的位置和区间最大值；
- 用到单点删除和插入；
- （开始题看错了，以为是区间交换，调了半天也没发现代码错误，然后再一看题，……….）
- 代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define N 100050
using namespace std;
int fa[N],c[N][],a[N],mx[N],siz[N];
int n,m,root;
void pushup(int x)
{
int l=c[x][],r=c[x][];
siz[x]=siz[l]+siz[r]+; mx[x]=max( max(mx[l],mx[r]),a[x]);
}
void rotate(int x,int &k)
{
int y=fa[x],z=fa[y],l=(c[y][]!=x),r=^l;
if(y==k) k=x; else c[z][c[z][]!=y]=x;
fa[x]=z; fa[y]=x; fa[c[x][r]]=y;
c[y][l]=c[x][r]; c[x][r]=y;
pushup(y);pushup(x);
}
void splay(int x,int &k)
{
int y,z;
while(x!=k)
{
y=fa[x]; z=fa[y];
if(y!=k) { if(c[z][]==y^c[y][]==x) rotate(x,k); else rotate(y,k); }
rotate(x,k);
}
}
int find(int x,int rt)
{
if(siz[c[rt][]]+==x) return rt;
else if(siz[c[rt][]]+>x) return find(x,c[rt][]);
else return find(x-siz[c[rt][]]-,c[rt][]);
}
int split(int a,int b)
{
int x=find(a,root),y=find(b,root);
splay(x,root); splay(y,c[x][]);
pushup(y); pushup(x);
if(c[y][]) return c[y][];
else return y;
}
void build(int l,int r,int last,int &k)
{
if(l>r) return;
k=l+r>>; fa[k]=last;
if(l==r){mx[k]=a[k]; siz[k]=;}
build(l,k-,k,c[k][]); build(k+,r,k,c[k][]); pushup(k);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n+;i++) scanf("%d",&a[i]);
build(,n+,,root); int zm,st,x,y,z,w; char di;
while(m--)
{
scanf("%d %c %d",&zm,&di,&st);
if(di=='L') x=split(zm-st,zm+);
else x=split(zm+,zm+st+);
printf("%d\n",mx[x]); x=split(zm,zm+); y=fa[x];
c[y][]=; fa[x]=; pushup(y); pushup(fa[y]); if(di=='L') y=split(zm-st,zm-st+);
else y=split(zm+st+-,zm+st+-);
fa[x]=y; c[y][]=x;
siz[x]=; mx[x]=a[x]; pushup(y); pushup(fa[y]);
}
return ;
}Click me here！
●GameZ游戏排名系统（codevs 1985）
- 我用的是Splay（权值树）+map（stl），题还不错。
- 单点插入，删除，查询单点信息，查询区间元素；
- 注意（分数会有重复的）
- codevs上是过了，但bzoj上显示Presentation_Error（求助！）
- 代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<map>
#define N 250050
#define inf 4294967305
#define ll long long
using namespace std;
map<string,ll> mp;
ll n,root,id,sz=,un,c[N][],fa[N],cnt;
char s[];
struct info{
ll sz,co;
char na[];
void nw(ll val)
{
sz=; co=val; ll i=;
while(s[i]) na[i-]=s[i],i++; na[i-]=;
}
}fo[N];
void pushup(ll x)
{
ll l=c[x][],r=c[x][];
fo[x].sz=fo[l].sz+fo[r].sz+;
}
void rotate(ll x,ll &k)
{
ll y=fa[x],z=fa[y],l=(c[y][]!=x),r=^l;
if(y==k) k=x; else c[z][c[z][]!=y]=x;
fa[x]=z; fa[y]=x; fa[c[x][r]]=y;
c[y][l]=c[x][r]; c[x][r]=y;
pushup(y);pushup(x);
}
void splay(ll x,ll &k)
{
ll y,z;
while(x!=k)
{
y=fa[x]; z=fa[y];
if(y!=k) { if(c[z][]==y^c[y][]==x) rotate(x,k); else rotate(y,k); }
rotate(x,k);
}
}
void insert(ll val,ll x,ll last,ll &rt)
{
if(!rt){rt=x; fo[x].nw(val); fa[x]=last; splay(x,root); return;}
insert(val,x,rt,c[rt][fo[rt].co<val]);
}
void erase()
{
splay(id,root);
ll t1,tt1=c[id][],t2,tt2=c[id][];
while(tt1) t1=tt1,tt1=c[t1][];
while(tt2) t2=tt2,tt2=c[t2][];
splay(t1,root);
splay(t2,c[t1][]);
un=c[t2][];
fa[un]=;
c[t2][]=;
pushup(t2);
pushup(t1);
}
void ask_rank()
{
if(cnt) printf("\n");
splay(id,root);
printf("%lld",fo[c[id][]].sz+-);
cnt++;
}
ll make_number()
{
ll tot=,i=;
while(s[i]) tot=tot*+s[i]-'',i++;
return tot;
}
void print_name(ll rt)
{
if(!rt) return;
print_name(c[rt][]);
printf("%s ",fo[rt].na);
print_name(c[rt][]);
}
ll find(ll x,ll rt)
{
if(fo[c[rt][]].sz+==x) return rt;
else if(fo[c[rt][]].sz+>x) return find(x,c[rt][]);
else return find(x-fo[c[rt][]].sz-,c[rt][]);
}
void ask_name(ll a)
{
if(cnt) printf("\n");
cnt++;
ll b=min(a++,sz);
ll x=find(b,root),y=find(a,root);
splay(x,root);
splay(y,c[x][]);
pushup(y); pushup(x);
print_name(c[y][]); }
int main()
{
scanf("%lld",&n); ll a;
insert(inf,,,root);
insert(-,,,root);
while(n--)
{
scanf("%s",s);
id=mp[s+];
if(s[]=='+')
{
scanf("%lld",&a);
if(!id) insert(a,id=mp[s+]=++sz,,root);
else
{
erase();
insert(a,un,,root);
}
}else
if('A'<=s[]&&s[]<='Z') ask_rank();
else
{
a=make_number();
ask_name(a);
}
}
return ;
}......