BZOJ 3595: [Scoi2014]方伯伯的Oj Splay + 动态裂点 + 卡常

BZOJ 3595: [Scoi2014]方伯伯的Oj Splay + 动态裂点 + 卡常

Description

方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。
Oj上注册了n个用户，编号为1～”，一开始他们按照编号排名。方伯伯会按照心情对这些用户做以下四种操作，修改用户的排名和编号：
1．操作格式为1 x y，意味着将编号为z的用户编号改为V，而排名不变，执行完该操作后需要输出该用户在队列中的位置，数据保证x必然出现在队列中，同时1，是一个当前不在排名中的编号。
2．操作格式为2 x，意味着将编号为x的用户的排名提升到第一位，执行完该操作后需要输出执行该操作前编号为z用户的排名。
3．操作格式为3 x，意味着将编号为z的用户的排名降到最后一位，执行完该操作后需要输出执行该操作前编号为z用户的排名。
4．操作格式为4 k，意味着查询当前排名为足的用户编号，执行完该操作后需要输出当前操作用户的编号。
但同时为了防止别人监听自己的工作，方伯伯对他的操作进行了加密，即将四种操作的格式分别改为了：
1 x+a y+a
2 x+a
3 x+a
4 k+a
其中a为上一次操作得到的输出，一开始a=0。
例如：
上一次操作得到的输出是5
这一次操作的输入为：1  13 15
因为这个输入是经过加密后的，所以你应该处理的操作是1 8 10
现在你截获丁方伯伯的所有操作，希望你能给出结果。

Input

输入的第1行包含2个用空格分隔的整数n和m，表示初始用户数和操作数。
此后有m行，每行是一个询问，询问格式如上所示。

Output

输出包含m行。每行包含一个整数，其中第i行的整数表示第i个操作的输出。

和 NOIP2017 day2t3 挺像的.
 凭借自己力量独立码出这道题还是超级开心的
 假如说数据范围较小，我们可以对每一个用户开一个点，并用平衡树来维护.
 不过，此题中人数会达到 $10^8$ 级别，这样无论是空间还是时间都承受不了.
 好在操作数 $m$ 最大只有 $10^5$ 级别.
 这意味着其实有许多人之间的相对位置关系是始终不变的（操作数太少）
 我们考虑用动态裂点的方式来维护.
 相比于原来是一个点维护一个人，现在是用一个点维护连续的一排人.
 如果操作的人在一个大的点中，直接分情况讨论将该点裂成 3(或2)个新点即可.
 以上操作可以用 $splay$ 来维护.
 还有一个小小的问题，我们如何知道用户 $x$ 在 $splay$ 中所在点的编号为多少 ？
 由于点和点表示的连续区间是不可能有交集的，我们直接用一个 $set$ 来维护每一个节点的左，右端点与节点编号.
 这样，当我们想知道节点编号时直接在 $set$ 中调用 $lowerbound$ 函数来查即可.
 说起来简单，写起来细节还是挺多的.

普通版：     

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define maxn 200004  
#define lson(x) ch[x][0]
#define rson(x) ch[x][1] 
#define get(x) (ch[f[x]][1]==x) 
using namespace std;
inline void setIO(string s)
{string in=s+".in",out=s+".out"; freopen(in.c_str(),"r",stdin); freopen(out.c_str(),"w",stdout); 
}
int n,Q,lastans,root;  
int ch[maxn][2], f[maxn], L[maxn], R[maxn], siz[maxn], sta[maxn]; 
inline int de()
{int x; scanf("%d",&x); return x - lastans; 
}
// 右端点从小 -> 大    
struct Node
{int l,r,id;  Node(int l=0,int r=0,int id=0):l(l),r(r),id(id){} bool operator<(Node b)const { return b.r > r; } 
}; 
set<Node>S; 
set<Node>::iterator it;  
struct Splay
{ int cnt; inline void init() { cnt=0; for(int i=1;i<maxn-100;++i) sta[++cnt]=i;  }inline int newnode() { return sta[cnt--];  }// 内存回收   inline void erase(int x) {ch[x][0]=ch[x][1]=f[x]=L[x]=R[x]=siz[x]=0; sta[++cnt]=x;       }inline void pushup(int x){siz[x]=siz[lson(x)] + siz[rson(x)] + R[x]-L[x]+1; }     inline void rotate(int x){int old=f[x],fold=f[old],which=get(x); ch[old][which]=ch[x][which^1], f[ch[old][which]]=old; ch[x][which^1]=old, f[old]=x, f[x]=fold; if(fold) ch[fold][ch[fold][1]==old]=x; pushup(old), pushup(x);     }// u -> x      inline void splay(int x,int &u){int a=f[u]; for(int fa;(fa=f[x])!=a;rotate(x)) {     if(f[fa]!=a) rotate(get(fa)==get(x)?fa:x);             }u = x;   }// 查找第 k 大编号inline int find(int kth){int p = root;    while(1){if(siz[lson(p)] >= kth) p=ch[p][0]; else {kth-=(siz[lson(p)]); if(kth > R[p] - L[p] + 1) kth -= (R[p] - L[p] + 1), p = rson(p); else {return L[p] + kth - 1; }}} }  inline void del(int x){int p=x; // root = x splay(x,root); if(!ch[x][0] && !ch[x][1]) root = 0;  else if(!ch[x][0])  root = ch[x][1], f[ch[x][1]]=0; else if(!ch[x][1]) root = ch[x][0], f[ch[x][0]]=0;      else { p = ch[x][0]; while(rson(p)) p = rson(p); splay(p, ch[x][0]);    rson(p) = ch[x][1], f[ch[x][1]] = p, f[p] = 0; pushup(p);     root=p;   }S.erase(Node(L[x], R[x],x)); erase(x); }    // 第 kth 大位置之后进行插入.    inline int insert(int kth,int l,int r){if(!root){root=newnode(), L[root]=l,R[root]=r;      pushup(root);  S.insert(Node(L[root], R[root], root)); return root; }int p=root, fa=0, cur=0, tmp=0; while(p) {fa=p; if(kth >= (tmp=siz[lson(p)] + R[p]-L[p]+1)) kth -= tmp, p=rson(p), cur=1; else p=lson(p), cur=0;  }p = newnode(); L[p]=l,R[p]=r; ch[fa][cur]=p,f[p]=fa; pushup(p); splay(p, root);S.insert(Node(L[p], R[p], p));                return p;        }// 对于点 x, 割裂出 l inline int split(int x,int l){splay(x, root);     int tmp = siz[lson(x)],l1=L[x], r1=R[x], oo=0;  // 该点已经单独存在,无需删除     if(l==l1&&l==r1) return x;      if(l==l1) {  del(x);    oo = insert(tmp,l,l); insert(tmp+1,l+1,r1); }else if(l==r1){del(x);          insert(tmp,l1,r1-1); oo = insert(tmp+r1-l1,r1,r1); }else { del(x);   // printf("---------n");insert(tmp,l1,l-1);  // printf("%d %dn",l1,l-1); oo = insert(tmp+l-l1,l,l);  // printf("%d %dn",l,l); insert(tmp+l-l1+1,l+1,r1);  //printf("%d %dn",l+1,r1); // for(it=S.begin();it!&#d();it++) printf("%d %dn",(*it).l,(*it).r); }   return oo; }
}tr; 
int main()
{// setIO("input"); scanf("%d%d",&n,&Q);tr.init(); tr.insert(0,1,n);     S.insert(Node(1,n,root));     while(Q--){int opt; scanf("%d",&opt); if(opt==1){// x -> y int x=de(),y=de(),z;  it=S.lower_bound(Node(0, x, 0));         z = tr.split((*it).id, x);          S.erase(Node(L[z], R[z], z)); S.insert(Node(y,y,z));                       tr.splay(z, root), L[z]=R[z]=y, tr.pushup(z), printf("%dn",lastans=siz[lson(z)]+1);  }if(opt==2){ int x=de(), z, l, r; it=S.lower_bound(Node(0, x, 0));   z = tr.split((*it).id, x);      tr.splay(z, root), printf("%dn",lastans=siz[lson(z)]+1); l = L[z], r=R[z];     tr.del(z), tr.insert(0, l, r);      }if(opt==3){int x=de(), z, l, r, kk;   // for(it=S.begin();it!&#d();it++) printf("%d %d::n",(*it).l,(*it).r); it = S.lower_bound(Node(0, x, 0));        z = tr.split((*it).id, x); tr.splay(z, root), printf("%dn",lastans=siz[lson(z)]+1); l = L[z], r = R[z]; tr.del(z); tr.insert(siz[root], l, r);      }if(opt==4){int k=de(); printf("%dn",lastans=tr.find(k)); }}return 0; 
}

卡常版

#include<bits/stdc++.h>
#define maxn 200004  
#define lson(x) ch[x][0]
#define rson(x) ch[x][1] 
#define get(x) (ch[f[x]][1]==x) 
#define rg register
#define O2 __attribute__((optimize("-O2")))
using namespace std;
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {int x=0; char c=nc(); while(c<48) c=nc(); while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x;}
O2 inline void setIO(rg string s)
{string in=s+".in",out=s+".out"; freopen(in.c_str(),"r",stdin); freopen(out.c_str(),"w",stdout); 
}
int n,Q,lastans,root;  
int ch[maxn][2], f[maxn], L[maxn], R[maxn], siz[maxn], sta[maxn]; 
O2 inline int de()
{rg int x=rd(); return x - lastans; 
}
// 右端点从小 -> 大    
struct Node
{int l,r,id;  Node(rg int l=0,rg int r=0,rg int id=0):l(l),r(r),id(id){} bool operator<(Node b)const { return b.r > r; } 
}; 
set<Node>S; 
set<Node>::iterator it;  
struct Splay
{ int cnt; O2 inline void init() { cnt=0; for(rg int i=1;i<maxn-100;++i) sta[++cnt]=i;  }O2 inline int newnode() { return sta[cnt--];  }// 内存回收   O2 inline void erase(int x) {ch[x][0]=ch[x][1]=f[x]=L[x]=R[x]=siz[x]=0; sta[++cnt]=x;       }O2 inline void pushup(int x){siz[x]=siz[lson(x)] + siz[rson(x)] + R[x]-L[x]+1; }     O2 inline void rotate(int x){rg int old=f[x],fold=f[old],which=get(x); ch[old][which]=ch[x][which^1], f[ch[old][which]]=old; ch[x][which^1]=old, f[old]=x, f[x]=fold; if(fold) ch[fold][ch[fold][1]==old]=x; pushup(old), pushup(x);     }// u -> x      O2 inline void splay(int x,int &u){rg int a=f[u]; for(rg int fa;(fa=f[x])!=a;rotate(x)) {     if(f[fa]!=a) rotate(get(fa)==get(x)?fa:x);             }u = x;   }// 查找第 k 大编号O2 inline int find(int kth){rg int p = root;    while(1){if(siz[lson(p)] >= kth) p=ch[p][0]; else {kth-=(siz[lson(p)]); if(kth > R[p] - L[p] + 1) kth -= (R[p] - L[p] + 1), p = rson(p); else {return L[p] + kth - 1; }}} }  O2 inline void del(int x){rg int p=x; // root = x splay(x,root); if(!ch[x][0] && !ch[x][1]) root = 0;  else if(!ch[x][0])  root = ch[x][1], f[ch[x][1]]=0; else if(!ch[x][1]) root = ch[x][0], f[ch[x][0]]=0;      else { p = ch[x][0]; while(rson(p)) p = rson(p); splay(p, ch[x][0]);    rson(p) = ch[x][1], f[ch[x][1]] = p, f[p] = 0; pushup(p);     root=p;   }S.erase(Node(L[x], R[x],x)); erase(x); }    // 第 kth 大位置之后进行插入.    O2 inline int insert(rg int kth,rg int l,rg int r){if(!root){root=newnode(), L[root]=l,R[root]=r;      pushup(root);  S.insert(Node(L[root], R[root], root)); return root; }rg int p=root, fa=0, cur=0, tmp=0; while(p) {fa=p; if(kth >= (tmp=siz[lson(p)] + R[p]-L[p]+1)) kth -= tmp, p=rson(p), cur=1; else p=lson(p), cur=0;  }p = newnode(); L[p]=l,R[p]=r; ch[fa][cur]=p,f[p]=fa; pushup(p); splay(p, root);S.insert(Node(L[p], R[p], p));                return p;        }// 对于点 x, 割裂出 l O2 inline int split(rg int x,rg int l){splay(x, root);     rg int tmp = siz[lson(x)],l1=L[x], r1=R[x], oo=0;  // 该点已经单独存在,无需删除     if(l==l1&&l==r1) return x;      if(l==l1) {  del(x);    oo = insert(tmp,l,l); insert(tmp+1,l+1,r1); }else if(l==r1){del(x);          insert(tmp,l1,r1-1); oo = insert(tmp+r1-l1,r1,r1); }else { del(x);   // printf("---------n");insert(tmp,l1,l-1);  // printf("%d %dn",l1,l-1); oo = insert(tmp+l-l1,l,l);  // printf("%d %dn",l,l); insert(tmp+l-l1+1,l+1,r1);  //printf("%d %dn",l+1,r1); // for(it=S.begin();it!&#d();it++) printf("%d %dn",(*it).l,(*it).r); }   return oo; }
}tr; 
O2 int main()
{  n=rd(),Q=rd();tr.init(); tr.insert(0,1,n);     S.insert(Node(1,n,root));     while(Q--){rg int opt=rd(); if(opt==1){// x -> y rg int x=de(),y=de(),z;  it=S.lower_bound(Node(0, x, 0));         z = tr.split((*it).id, x);          S.erase(Node(L[z], R[z], z)); S.insert(Node(y,y,z));                       tr.splay(z, root), L[z]=R[z]=y, tr.pushup(z), printf("%dn",lastans=siz[lson(z)]+1);  }if(opt==2){ rg int x=de(), z, l, r; it=S.lower_bound(Node(0, x, 0));   z = tr.split((*it).id, x);      tr.splay(z, root), printf("%dn",lastans=siz[lson(z)]+1); l = L[z], r=R[z];     tr.del(z), tr.insert(0, l, r);      }if(opt==3){rg int x=de(), z, l, r, kk;      it = S.lower_bound(Node(0, x, 0));        z = tr.split((*it).id, x); tr.splay(z, root), printf("%dn",lastans=siz[lson(z)]+1); l = L[z], r = R[z]; tr.del(z); tr.insert(siz[root], l, r);      }if(opt==4){rg int k=de(); printf("%dn",lastans=tr.find(k)); }}return 0; 
}

转载于:.html