继续水题，终于完全掌握了伸展树了，好心痛QAQ。
1.codevs1343 蚱蜢
区间最大值查询+单点移动
最大值查询维护一个mx数组就行，单点移动么，先删除在插入
CODE：
/*
PS: 比较max值时，要写成 mx[x]=max(a[x],max(mx[l],mx[r]));形式
且最好把mx[0]赋值为负无穷大 取max时，注意初值问题 */ #include<bits/stdc++.h>
#define N 100005
using namespace std;
int c[N][],fa[N],a[N],size[N],mx[N],n,m,rt;
int read(){
char c;int f=,x=;c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();}
while(c<=''&&c>='')x=x*+c-'',c=getchar();
return f*x;
} void pushup(int x){
int l=c[x][],r=c[x][];
size[x]=size[l]+size[r]+;
mx[x]=max(a[x],max(mx[l],mx[r]));
} void rotate(int x,int &k){//旋转
int y=fa[x],z=fa[y],l,r;
l=(c[y][]==x);r=l^;
if(y==k)k=x;
else c[z][c[z][]==y]=x;
fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
c[y][l]=c[x][r];c[x][r]=y;
pushup(y);pushup(x);
} void splay(int x,int &k){//转化为根
while(x!=k){
int 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;
if(l==r){c[f][l>=f]=l;fa[l]=f;mx[l]=a[l];size[l]=;return;}
int mid=(l+r)>>;build(l,mid-,mid);build(mid+,r,mid);
pushup(mid);fa[mid]=f;c[f][mid>=f]=mid;
} int find(int x,int k){
int l=c[x][],r=c[x][];
if(size[l]+==k)return x;
if(size[l]>=k)return find(l,k);
return find(r,k-size[l]-);
} void query(int l,int r){
int x=find(rt,l),y=find(rt,r+);
splay(x,rt);splay(y,c[x][]);
printf("%d\n",mx[c[y][]]);
} void move(int l,int r){
int x=find(rt,l),y=find(rt,l+);
splay(x,rt);splay(y,c[x][]);
int now=c[y][];fa[now]=;
c[y][]=;pushup(y);pushup(x);
x=find(rt,r+);y=find(rt,r+);
splay(x,rt);splay(y,c[x][]);
c[y][]=now;fa[now]=y;
pushup(y);pushup(x);
} int main(){
n=read();m=read();
a[]=a[n+]=-;
for(int i=;i<=n;i++)a[i+]=read();
build(,n+,);rt=(n+)>>;
while(m--){
printf("\n");
int l,r;char s[];l=read();
scanf("%s",s);
if(s[]=='D'){r=read()+l;query(l+,r);move(l,r-);}
else{r=l-read();query(r,l-);move(l,r-);}
/* for(int i=2;i<=n+1;i++){
int dada=find(rt,i);
printf("%d ",a[dada]);
}*/
}
return ;
}
2.codevs1514 书架
单点移动+单点查询
移动还是一样，先删除再插入
查询编号为S的书的上面目前有多少本书时，把S调整至根节点，输出左边儿子的元素个数即可
查询从上面数起的第S本书的编号，find（S）即可。
CODE：
#include<cstdio>
#include<cstring>
using namespace std; const int INF = 1e9 + ;
const int maxn = + ; int n, m, root;
int ch[maxn][], p[maxn], a[maxn], s[maxn], v[maxn], id[maxn]; void update(int k) {
s[k] = s[ch[k][]] + s[ch[k][]] + ;
} void rotate(int& px, int& x, int d) {
int t = ch[x][d]; ch[x][d] = px; ch[px][d^] = t;
p[x] = p[px]; p[px] = x; p[t] = px; update(px); update(x); px = x;
} void splay(int x, int& k) {
while(x != k) {
int y = p[x], z = p[y];
int d = ch[y][] == x ? : ;
int d2 = ch[z][] == y ? : ;
if(y != k) rotate(ch[z][d2], x, d^); else rotate(k, x, d^);
}
} void build(int L, int R, int P, int d) {
if(L == R) { s[L] = ; p[L] = P; ch[P][d] = L; return; }
int M = (L+R) >> ;
p[M] = P; ch[P][d] = M;
if(M- >= L) build(L, M-, M, );
if(R >= M+) build(M+, R, M, );
update(M);
} int find(int k, int rank) {
int l = ch[k][], r = ch[k][];
if(s[l]+ == rank) return k;
else if(s[l] >= rank) return find(l, rank);
else return find(r, rank-s[l]-);
} void remove(int k) {
int x, y, z;
x = find(root, k-); y = find(root, k+);
splay(x, root); splay(y, ch[x][]);
z = ch[y][]; ch[y][] = ; p[z] = s[z] = ;
update(y); update(x);
} void move(int k, int val) {
int o = id[k], x, y, rank;
splay(o, root);
rank = s[ch[o][]] + ;
remove(rank);
if(val == INF) x = find(root, n), y = find(root, n+);
else if(val == -INF) x = find(root, ), y = find(root, );
else x = find(root, rank+val-), y = find(root, rank+val);
splay(x, root); splay(y, ch[x][]);
s[o] = ; p[o] = y; ch[y][] = o;
update(y); update(x);
} int main() {
scanf("%d%d", &n, &m);
for(int i = ; i <= n+; i++) scanf("%d", &v[i]), id[v[i]] = i;
build(, n+, , );
root = (n+) >> ; char cmd[]; int S, T;
for(int i = ; i <= m; i++) {
scanf("%s%d", cmd, &S);
switch(cmd[]) {
case 'T': move(S, -INF); break;
case 'B': move(S, INF); break;
case 'I': scanf("%d", &T); move(S, T); break;
case 'A': splay(id[S], root); printf("%d\n", s[ch[id[S]][]]-); break;
case 'Q': printf("%d\n", v[find(root, S+)]); break;
}
}
return ;
}
3.codevs1743 反转卡片
简单到爆，一直区间倒置直到第一个数==1为止
CODE:
#include<bits/stdc++.h>
#define N 300005
using namespace std;
int c[N][],fa[N],a[N],v[N],size[N],rev[N],rt,n,m;
int read(){
char c;int f=,x=;c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();}
while(c<=''&&c>='')x=x*+c-'',c=getchar();
return f*x;
} void update(int x){
int l=c[x][],r=c[x][];
size[x]=size[l]+size[r]+;
} void pushdown(int x){
if(rev[x]){
swap(c[x][],c[x][]);rev[x]=;
if(c[x][])rev[c[x][]]^=;
if(c[x][])rev[c[x][]]^=;
}
} void rotate(int x,int &k){
int y=fa[x],z=fa[y],l,r;
if(c[y][]==x)l=;else l=;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){
while(x!=k){
int 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;
if(l==r){
size[l]=;fa[l]=f;
if(l>f)c[f][]=l;
else c[f][]=l;
v[l]=a[l];
return;
}
int mid=(l+r)>>;v[mid]=a[mid];
build(l,mid-,mid);build(mid+,r,mid);
update(mid);fa[mid]=f;c[f][mid>f]=mid;
} int find(int x,int k){
pushdown(x);
int l=c[x][],r=c[x][];
if(size[l]+==k)return x;
if(size[l]+>k)return find(l,k);
return find(r,k--size[l]);
} void rever(int l,int r){
int x=find(rt,l),y=find(rt,r+);
splay(x,rt);splay(y,c[x][]);
rev[c[y][]]^=;
} int main(){
n=read();
a[]=a[n+]=;
for(int i=;i<=n;i++)a[i+]=read();
build(,n+,);rt=(+n)>>;
int x,y,ans=;
while(){
y=find(rt,);
x=v[y];
if(x==||ans>)break;
else rever(,x);
ans++;
}
printf("%d",ans>?-:ans);
return ;
}
4.codevs1985 GameZ游戏排名系统
cnm劳资这个题调了一个晚上。。。。泪流满面，本来还可以多写2个题的。
使用hash或者map建立映射，记录某人是否已出现，如果出现的话删除再插入，否则直接插入
查询玩家排名时，直接查询他的编号，把编号调整至根节点，输出右边儿子的元素个数
最坑比的就是输出从第x位起排名前10位的人。。我先用的是查找函数，直接查找排名第x+1，x+2……点的编号并输出名字，然而效率及其低下，codevsTLE3组。后来美腻的张姐告诉我：把x~x+10区间调整至一个子树上，然后中序遍历，输出。我TM真的是个智障。。
PS:注意建立两个虚节点分别作为第一和倒数第一，来保证splay操作的正确性或者加上特殊的判断处理，但特判有些麻烦
CODE：
//愚蠢的TLE :输出一段连续的区间值时，不要一个一个找每个数的位置（超级费时间）
// 把那整个区间转移到一棵子树上，中序输出
#include<bits/stdc++.h>
#define N 250005
#define inf 2147483647
using namespace std;
int n,c[N][],fa[N],val[N],size[N],tot,rt,t1,t2;
char s[];
struct player{
int sc;
char na[];
}p[N];
map<string,int>mp;
int read(){
char c;int f=,x=;c=getchar();
while(c>''||c<''){if(c=='-')f=-;c=getchar();}
while(c<=''&&c>='')x=x*+c-'',c=getchar();
return f*x;
} void pushup(int x){
int l=c[x][],r=c[x][];
size[x]=size[l]+size[r]+;
} void rotate(int x,int &k){
int y=fa[x],z=fa[y],l,r;
if(c[y][]==x)l=;else l=;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){
while(x!=k){
int 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 insert(int v,int num){
if(!rt){rt=num;val[num]=v;size[rt]=;return;}
int p=rt,z;
while(p){
size[p]++;z=p;
if(val[p]<v)p=c[p][];
else p=c[p][];
}
val[num]=v;c[z][v>val[z]]=num;
fa[num]=z;size[num]=;
splay(num,rt);
} int find(int x,int k){
int l=c[x][],r=c[x][];
if(size[r]+==k)return x;
if(size[r]>=k)return find(r,k);
return find(l,k-size[r]-);
} int trans(){
int i=,x=;
while(s[i]){x=x*+s[i]-'';i++;}
return x;
} void del(int x){
splay(x,rt);
int l=c[x][],r=c[x][];
while(c[l][])l=c[l][];
while(c[r][])r=c[r][];
splay(l,rt);splay(r,c[l][]);
fa[c[r][]]=;c[r][]=;
pushup(r);pushup(l);
} void print(int x){
if(!x)return;
print(c[x][]);
printf("%s ",p[x].na);
print(c[x][]);
} void find_name(int a){
int b=min(a+,tot);
int x=find(rt,b),y=find(rt,a);
splay(x,rt);splay(y,c[x][]);
pushup(y);pushup(x);
print(c[y][]);
printf("\n");
} int main(){
n=read();
insert(inf,);
insert(-,);
tot=;
for(int i=;i<=n;i++){
char ch;scanf(" %c",&ch);
if(ch=='+'){
scanf("%s",p[++tot].na);p[tot].sc=read();
if(mp[p[tot].na]){
int ps=mp[p[tot].na];
del(ps);
p[ps].sc=p[tot].sc;
insert(p[tot].sc,ps);
tot--;
}
else {
mp[p[tot].na]=tot;
insert(p[tot].sc,tot);
}
}
else {
scanf("%s",s);
if(s[]>=''&&s[]<=''){
int pos=trans();
find_name(pos);
}
else{
int ps=mp[s];
splay(ps,rt);
printf("%d\n",size[c[rt][]]);
}
} }
return ;
}
记录一件事情，今晚lgh和ypj吵架了，原因是我们想离开高二机房，他不准，lgh又不肯退步，于是造成了惨剧（开玩笑）。。后来ypj就一直教育他（期间再次提到了某位打游戏翻车的同学），搞得他心情很不好啊，于是他就开始挤兑ypj，我估计后来ypj也非常不高兴。
其实这件事呢，我们是不占理的。首先是没给ypj说一声就想走，十分的不尊重，其二就是lgh可能被愤怒冲昏了头脑，说话非常的冲，让人听了很不爽，交流方式确实有些问题。当然ypj说话也有些问题，他非常的不善言辞（就是瞎几把说话）。在我看来，和ypj吵并不值得，因为他本来就很不可理喻，思想跟我们完全脱节。以后遇到这种情况，我们最好就是不跟他说屁话，打代码。他bb够了自己就离开了，免得吵起来双方都不爽。
今天ypj讲了主席树，我听懂了思想，但具体代码实现还有些懵逼，明天再看看。。
chair-man tree