题解 P3285 【[SCOI2014]方伯伯的OJ】

Froggy · 2019-04-05 21:11:24 · 题解

动态开点Splay

splay按排名排序,map记录右端点编号,即map[k]=t[k].r

这样,map.lower_bound就可以直接找到目标节点

我见许多题解的splay的2,3操作都是先erase再push_front或是push_back,不过我直接再原点上修改,这样一个change完事,可以大大减小代码量~~(也卡了常)

类似的题:P3960 列队

change函数原理:

2操作:将目标节点拆开,旋到根,将左子树向右子树合并,目标节点就变成了第一名
3操作:将目标节点拆开,旋到根,将右子树向左子树合并,目标节点就变成了最后一名

具体实现见代码里的change()函数

另:

1操作直接拆,修改编号,别忘了改map

4操作正常,按rank询问编号 ~~(我一开始忘把rank-=t[son].siz了,调了一个星期QWQ)~~

AC代码:

~~马蜂中规中矩~~

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
#define N 100010
inline int read(){
  int x=0,f=1;
  char c=getchar();
  while(c<'0'||c>'9'){
      if(c=='-')f=-1;
      c=getchar();
  }
  while(c>='0'&&c<='9'){
      x=(x<<3)+(x<<1)+c-'0';
      c=getchar();
  }
  return x*f;
}
int root,cnt=0,n,m,lans;
map<int,int> mp; 
struct node{
  int ch[2],siz,l,r,fa;
}t[N<<2];
int newNode(int l,int r){
  int k=++cnt;
  t[k].ch[0]=t[k].ch[1]=0;
  t[k].l=l,t[k].r=r;
  t[k].siz=t[k].r-t[k].l+1;
  return k;
}
void up(int k){
  t[k].siz=t[t[k].ch[0]].siz+t[t[k].ch[1]].siz+t[k].r-t[k].l+1;
}
int get(int k){
  return t[t[k].fa].ch[1]==k;
}
void rorate(int k){//略
  int fa=t[k].fa,gfa=t[fa].fa;
  int d1=get(k),d2=get(fa);
  t[fa].ch[d1]=t[k].ch[d1^1];
  t[t[k].ch[d1^1]].fa=fa;
  t[gfa].ch[d2]=k;
  t[k].fa=gfa;
  t[fa].fa=k;
  t[k].ch[d1^1]=fa;
  up(fa);
  up(k);
}
void splay(int k,int goal){//同上
  while(t[k].fa!=goal){
      int fa=t[k].fa,gfa=t[fa].fa;
      int d1=get(k),d2=get(fa);
      if(gfa!=goal){
          if(d1==d2)rorate(fa);
          else rorate(k);
      }
      rorate(k);
  }
  if(goal==0)root=k;
}
int kth(int rank){
  int k=root;
  while(1){
      int son=t[k].ch[0];
      if(rank<=t[son].siz)k=son;
      else if(rank>t[son].siz+t[k].r-t[k].l+1){
          rank-=t[son].siz+t[k].r-t[k].l+1;
          k=t[k].ch[1];
      }
      else{
          rank-=t[son].siz;
          return t[k].l+rank-1;
      }
  }
}
int rank(int k){//按编号找排名
  splay(k,0);
  return t[t[k].ch[0]].siz+1;
}
inline void split(int k,int id){//分裂操作
  int l=0,r=0;
  if(t[k].l==t[k].r)return;
  mp[id]=k;
  if(t[k].l!=id){
      mp[id-1]=l=newNode(t[k].l,id-1);
      t[l].ch[0]=t[k].ch[0];
      t[t[l].ch[0]].fa=l;
      t[k].ch[0]=l;
      t[l].fa=k;
  }
  if(t[k].r!=id){
      mp[t[k].r]=r=newNode(id+1,t[k].r);
      t[r].ch[1]=t[k].ch[1];
      t[t[r].ch[1]].fa=r;
      t[k].ch[1]=r;
      t[r].fa=k;
  }
  t[k].l=t[k].r=id;
  if(l)up(l);
  if(r)up(r);
  up(k);
}
void change(int k,int p){//这里,IMPORTANT!
  splay(k,0);
  k=root;
  if(!t[k].ch[p])return;//如果本身就是头或尾,直接再见
  if(!t[k].ch[p^1]){//如果在遥远的另一端,左变右或右变左
      t[k].ch[p^1]=t[k].ch[p];
      t[k].ch[p]=0;
  }
  else{//在中间的话,合并子树
      k=t[k].ch[p^1];
      while(t[k].ch[p])k=t[k].ch[p];
      t[t[root].ch[p]].fa=k;
      t[k].ch[p]=t[root].ch[p];
      t[root].ch[p]=0;
      splay(t[k].ch[p],0);
  }
}
int main(){
  n=read();m=read();
  mp[n]=root=newNode(1,n);
  for(int i=1;i<=m;i++){
      int opt,x,y;
      opt=read();x=read();
      x-=lans;
      if(opt == 1){
          y=read(),y -= lans;
          int pos=(*mp.lower_bound(x)).second;
          split(pos,x);
          lans=rank(pos);
          t[pos].l=t[pos].r=y;
          mp[y]=pos;
          cout<<lans<<endl;
      }
      if(opt == 2 || opt == 3){
          int pos=(*mp.lower_bound(x)).second;
          split(pos,x);
          lans=rank(pos);
          change(pos,opt-2);
          cout<<lans<<endl;
      }
      if(opt==4){
          lans=kth(x);//按排名找编号
          cout<<lans<<endl;
      }
  }
  return 0;//bye~
}

顺便放上P3960的代码,方便大家学习~

~~不开long long见祖宗~~

#include<iostream>
#include<cstdio>
using namespace std;
#define N 300010
#define ll long long
inline int read(){
  int x=0,f=1;
  char c=getchar();
  while(c<'0'||c>'9'){
      if(c=='-')f=-1;
      c=getchar();
  }
  while(c>='0'&&c<='9'){
      x=(x<<3)+(x<<1)+c-'0';
      c=getchar();
  }
  return x*f;
}
int n,m,q,root[N],cnt;
struct node{
  int ch[2],fa;
  ll siz,l,r;
}t[N*30];
inline int newNode(ll l,ll r){
  int k=++cnt;
  t[k].ch[0]=t[k].ch[1]=0;
  t[k].l=l,t[k].r=r;
  t[k].siz=t[k].r-t[k].l+1;
  return k;
}
inline void up(int k){
  t[k].siz=t[t[k].ch[0]].siz+t[t[k].ch[1]].siz+t[k].r-t[k].l+1;
}
inline int get(int k){
  return t[t[k].fa].ch[1]==k;
}
inline void rorate(int k){
  int fa=t[k].fa,gfa=t[fa].fa;
  int d1=get(k),d2=get(fa);
  t[fa].ch[d1]=t[k].ch[d1^1];
  t[t[k].ch[d1^1]].fa=fa;
  t[gfa].ch[d2]=k;
  t[k].fa=gfa;
  t[fa].fa=k;
  t[k].ch[d1^1]=fa;
  up(k);
  up(fa);
}
inline void splay(int &root,int k,int goal){
  while(t[k].fa!=goal){
      int fa=t[k].fa,gfa=t[fa].fa;
      int d1=get(k),d2=get(d2);
      if(gfa!=goal){
          if(d1==d2)rorate(fa);
          else rorate(k);
      }
      rorate(k);
  }
  if(goal==0)root=k;
}
inline void Insert(int &root,ll l){
  int k=root,fa=0;
  while(k){
      fa=k;
      k=t[k].ch[1];
  }
  k=newNode(l,l);
  if(fa)t[fa].ch[1]=k;
  t[k].fa=fa;
  splay(root,k,0);
}
ll splitNode(int &root,int k,ll rank){
  splay(root,k,0);
  rank+=t[k].l-1;
  int tmp=newNode(rank+1,t[k].r);
  t[k].r=rank-1;
  if(t[k].ch[1]==0){
      t[k].ch[1]=tmp;
      t[tmp].fa=k;
  }
  else{
      t[tmp].ch[1]=t[k].ch[1];
      t[t[tmp].ch[1]].fa=tmp;
      t[k].ch[1]=tmp;
      t[tmp].fa=k;
  }
  up(tmp);
  up(k);
  return rank;
}
inline ll getKth(int &root,ll rank){
  int k=root;
  while(1){
      int son=t[k].ch[0];
      if(rank<=t[son].siz){
          k=t[k].ch[0];
      }
      else if(rank>t[son].siz+t[k].r-t[k].l+1){
          rank-=(t[son].siz+t[k].r-t[k].l+1);
          k=t[k].ch[1];
      }
      else{
          rank-=t[son].siz;
          return splitNode(root,k,rank);
      }
  }
}
int main(){
  n=read();m=read();q=read();
  for(int i=1;i<=n;i++){
      root[i]=newNode(1ll*(i-1)*m+1,1ll*i*m-1);
  }
  root[n+1]=newNode(1ll*m,1ll*m);
  for(int i=2;i<=n;i++){
      Insert(root[n+1],1ll*i*m);
  }

  while(q--){
      int x=read(),y=read();
      if(y==m){
          ll ans=getKth(root[n+1],x);
          printf("%lld\n",ans);
          Insert(root[n+1],ans);
      }
      else{
          ll ans=getKth(root[x],y);
          printf("%lld\n",ans);
          Insert(root[n+1],ans);
          Insert(root[x],getKth(root[n+1],x));
      }
  }
  return 0;
}

题解 P3285 【[SCOI2014]方伯伯的OJ】

动态开点Splay

splay按排名排序,map记录右端点编号,即map[k]=t[k].r

我见许多题解的splay的2,3操作都是先erase再push_front或是push_back,不过我直接再原点上修改,这样一个change完事,可以大大减小代码量~~(也卡了常)

change函数原理:

2操作:将目标节点拆开,旋到根,将左子树向右子树合并,目标节点就变成了第一名

3操作:将目标节点拆开,旋到根,将右子树向左子树合并,目标节点就变成了最后一名

另:

AC代码:

顺便放上P3960的代码,方便大家学习~