首页
登录 | 注册

[SCOI2014]方伯伯的OJ

看到这道题的第一想法就是要用FHQ treap 过了这道题...于是至今尚未成功(华丽的 T 掉了 (╯‵□′)╯︵┻━┻ )。于是附个地址。

然后水一波博客。

 

题意简介

emmmm...方伯伯脑抽做了个 oj ,然后想要在对 oj 上的 1~n 编号的用户乱来(并且还对他的乱来操作进行了加密)。你需要维护一棵平衡树完成方伯伯的一波操作

你的平衡树需要支持这些操作: 1. 修改编号; 2. 把一个人放到树的最左边; 3. 把一个人放到树的最右边;4.输出一个排名对应的编号。

 

题目分析

然后这道题非常坑,要用 map 记录每个节点对应区间右端点的对应节点编号 (听起来很绕,其实就是: 设某节点对应区间右端点为 R , 该节点编号为 p , 那么我们用的map 的 first key 就是 R ,second key 是 p),然后用找某个编号所在的节点用 lower_bound 就好了(才知道map是可以 lower bound 的,并且是以第一关键字作比较的)。我记得有看到用另一种利用 map 的方法,那好像是 普通 treap (splay应该也能用啊)的,而且节点维护的区间也有点混乱...就是这个

 

Splay 做法

  1 //by Judge
  2 #include<iostream>
  3 #include<cstdio>
  4 #include<map>
  5 using namespace std;
  6 const int M=5e5+111;
  7 //#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
  8 char buf[1<<21],*p1=buf,*p2=buf;
  9 inline int read(){
 10     int x=0,f=1; char c=getchar();
 11     for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
 12     for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
 13 }
 14 char sr[1<<21],z[20];int C=-1,Z;
 15 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
 16 inline void print(int x){
 17     if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
 18     while(z[++Z]=x%10+48,x/=10);
 19     while(sr[++C]=z[Z],--Z);sr[++C]='\n';
 20 }
 21 int n,m,cnt,ans,root;
 22 map<int,int> mp;
 23 struct Node{
 24     int l,r,siz,fa,ch[2];
 25 }t[M];
 26 inline int newnode(int x,int y){ int u=++cnt; t[u].siz=y-x+1,t[u].l=x,t[u].r=y; return u; }
 27 inline void pushup(int x){ t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+t[x].r-t[x].l+1; }
 28 inline void rotate(int x){
 29     int y=t[x].fa,z=t[y].fa,sn=t[y].ch[1]==x;
 30     t[x].fa=z; if(z) t[z].ch[t[z].ch[1]==y]=x;
 31     t[y].ch[sn]=t[x].ch[!sn],t[t[y].ch[sn]].fa=y;
 32     t[y].fa=x,t[x].ch[!sn]=y,pushup(y);
 33 }
 34 inline void splay(int x,int to){
 35     while(t[x].fa^to){
 36         int y=t[x].fa,z=t[y].fa;
 37         if(z!=to) rotate((t[z].ch[0]==y)^(t[y].ch[0]==x)?x:y);
 38         rotate(x);
 39     } pushup(x); if(!to) root=x;
 40 }
 41 inline int query(int x){ splay(x,0); return t[x].siz-t[t[x].ch[1]].siz; }
 42 inline int get_id(int k){  //查询排名为 k 的人的编号
 43     int now=root;
 44     while(k){ 
 45         int sum=t[t[now].ch[0]].siz+t[now].r-t[now].l+1;
 46         if(t[t[now].ch[0]].siz<k && k<=sum){
 47             k-=t[t[now].ch[0]].siz; break;
 48         } else if(sum<k) k-=sum,now=t[now].ch[1];
 49         else now=t[now].ch[0];
 50     } return t[now].l+k-1;
 51 }
 52 inline void erase(int x){  //删除节点信息
 53     int pre=t[x].ch[0],nxt=t[x].ch[1];
 54     while(t[pre].ch[1]) pre=t[pre].ch[1];
 55     while(t[nxt].ch[0]) nxt=t[nxt].ch[0];
 56     if(!pre && !nxt) return (void)(root=0);
 57     if(!pre) splay(nxt,root),t[root=nxt].fa=0;
 58     else if(!nxt) splay(pre,root),t[root=pre].fa=0;
 59     else splay(pre,0),splay(nxt,pre),t[nxt].ch[0]=0,pushup(nxt),pushup(pre);
 60     t[x].ch[0]=t[x].ch[1]=0,t[x].siz=1;  //不知道为什么这里不写会 T (懒得想咯应该是编号改完可能会改回来的问题吧)
 61 }
 62 inline void push_front(int x){ //插头
 63     if(!root) return (void)(root=x); int fa=root;
 64     while(t[fa].ch[0]) ++t[fa].siz,fa=t[fa].ch[0];
 65     ++t[fa].siz,t[fa].ch[0]=x,t[x].fa=fa,splay(x,0);
 66 }
 67 inline void push_back(int x){  //插尾
 68     if(!root) return (void)(root=x); int fa=root;
 69     while(t[fa].ch[1]) ++t[fa].siz,fa=t[fa].ch[1];
 70     ++t[fa].siz,t[fa].ch[1]=x,t[x].fa=fa,splay(x,0);
 71 }
 72 inline void split(int x,int id){ //拆出节点
 73     int L=t[x].l,R=t[x].r,ls,rs;
 74     if(L==R) return ; //不用拆
 75     if(L==id){  //最左端
 76         mp[R]=rs=++cnt,mp[id]=x;
 77         t[rs].ch[1]=t[x].ch[1];
 78         t[t[rs].ch[1]].fa=rs;
 79         t[x].ch[1]=rs,t[rs].fa=x;
 80         t[rs].l=L+1,t[rs].r=R,t[x].r=L;
 81         pushup(rs),pushup(x);
 82     } else if(R==id){ //最右端
 83         mp[R-1]=ls=++cnt,mp[id]=x;
 84         t[ls].ch[0]=t[x].ch[0];
 85         t[t[ls].ch[0]].fa=ls;
 86         t[x].ch[0]=ls,t[ls].fa=x;
 87         t[ls].l=L,t[ls].r=R-1,t[x].l=R;
 88         pushup(ls),pushup(x);
 89     } else{  //在中间
 90         mp[id]=x,mp[id-1]=ls=++cnt,mp[R]=rs=++cnt;
 91         t[ls].ch[0]=t[x].ch[0],t[rs].ch[1]=t[x].ch[1];
 92         t[t[ls].ch[0]].fa=ls,t[t[rs].ch[1]].fa=rs;
 93         t[x].ch[0]=ls,t[x].ch[1]=rs,t[ls].fa=t[rs].fa=x;
 94         t[x].l=t[x].r=id,t[ls].l=L,t[ls].r=id-1,t[rs].l=id+1,t[rs].r=R;
 95         pushup(ls),pushup(rs),pushup(x);
 96     }
 97 }
 98 signed main() {
 99     n=read(),m=read(),
100     mp[n]=root=newnode(1,n);
101     for(int x,y,pos,opt;m;--m){
102         opt=read();
103         switch(opt){
104             case 1:
105                 x=read()-ans,y=read()-ans;
106                 pos=mp.lower_bound(x)->second; //map 里面找节点编号
107                 split(pos,x),ans=query(pos); //拆出节点查排名
108                 t[pos].l=t[pos].r=y,mp[y]=pos; //修改信息输答案
109                 print(ans); break;
110             case 2:
111                 x=read()-ans, pos=mp.lower_bound(x)->second;
112                 split(pos,x),ans=query(pos),erase(pos); //拆除节点再删除
113                 push_front(pos),print(ans); break; //节点重新加入树
114             case 3:
115                 x=read()-ans, pos=mp.lower_bound(x)->second;
116                 split(pos,x),ans=query(pos),erase(pos);
117                 push_back(pos),print(ans); break;
118             case 4:
119                 x=read()-ans,ans=get_id(x),print(ans); break; //询问编号直输出
120         }
121     } Ot(); return 0;
122 }

 

FHQ treap

 


相关文章

  • 补习系列(20)-大话 WebSocket 与 &quot;尬聊&quot;的实现
    目录 一.聊聊 WebSocket 二.Stomp 是个什么鬼 三.SpringBoot 整合 WebSocket A. 引入依赖 B. WebSocket 配置 C. 控制器 D. 前端实现 四.参考文档 一.聊聊 WebSocket 从 ...
  • 页面性能优化-原生JS实现图片懒加载
         在项目开发中,我们往往会遇到一个页面需要加载很多图片的情况.我们可以一次性加载全部的图片,但是考虑到用户有可能只浏览部分图片.所以我们需要对图片加载进行优化,只加载浏览器窗口内的图片,当用户滚动时,再加载更多的图片.这种加载图片的 ...
  • 《k8s 源码分析》- Custom Controller 之 Informer
    Custom Controller 之 Informer 概述 架构概览 reflector - List & Watch API Server Reflector 对象 ListAndWatch watchHandler - ad ...
  • 目录 引入 简单工厂 抽象工厂 Spring的bean工厂 模拟Spring工厂实现 模拟IOC 引入 假设有一个司机, 需要到某个城市, 于是我们给他一辆汽车 public class Demo { public static void ...
  • 关于分布式锁原理的一些学习与思考-redis分布式锁,zookeeper分布式锁
      首先分布式锁和我们平常讲到的锁原理基本一样,目的就是确保,在多个线程并发时,只有一个线程在同一刻操作这个业务或者说方法.变量. 在一个进程中,也就是一个jvm 或者说应用中,我们很容易去处理控制,在jdk java.util 并发包中已 ...
  • ERP不规范,同事两行泪
    最近的很多次对外交流,都聊到了ERP建设的话题,并且无一例外的不那么让人省心,回想我这么多年走过的ERP坑坑路,在这里也写下经验和总结,希望能给正在或者即将走上ERP建设路的企业一些思考和帮助. 导读 1.几个瞎眼而普遍的案例 2.ERP的 ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.066 s.
京ICP备10005923号