精华内容
下载资源
问答
  • 方伯伯的OJ ( onlinejudge ) 方伯伯的OJ 题目描述 方伯伯正在做他的OJ。现在他在处理OJ 上的用户排名问题。 OJ 上注册了n 个用户,编号为1 ∼ n,一开始他们按照编号排名。方伯伯会按照...

    方伯伯的OJ ( onlinejudge )

    方伯伯的OJ

    题目描述

    方伯伯正在做他的OJ。现在他在处理OJ 上的用户排名问题。

    OJ 上注册了个用户,编号为1  n,一开始他们按照编号排名。方伯伯会按照心情对这些用户做以下四种操作,修改用户的排名和编号:

    1. 操作格式为1 x y,意味着将编号为的用户编号改为y,而排名不变,执行完该操作后需要输出该用户在队列中的位置,数据保证必然出现在队列中, 同时是一个当前不在排名中的编号。

    2. 操作格式为2 x,意味着将编号为的用户的排名提升到第一位,执行完该操作后需要输出执行该操作前编号为用户的排名。

    3. 操作格式为3 x,意味着将编号为的用户的排名降到最后一位,执行完该操作后需要输出执行该操作前编号为用户的排名。

    4. 操作格式为4 k,意味着查询当前排名为的用户编号,执行完该操作后需要输出当前操作用户的编号。

    但同时为了防止别人监听自己的工作,方伯伯对他的操作进行了加密,即将四种操作的格式分别改为了:

    a y a

    a

    a

    a

    其中为上一次操作得到的输出,一开始= 0。

    例如:

    上一次操作得到的输出是5

    这一次操作的输入为:1 13 15

    因为这个输入是经过加密后的,所以你应该处理的操作是1 8 10

    现在你截获了方伯伯的所有操作,希望你能给出结果。

     

    输入格式

    输入的第1 行包含2 个用空格分隔的整数m,表示初始用户数和操作数。

    此后有行,每行是一个询问,询问格式如上所示。

     

    输出格式

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

     

    样例

    样例输入

    10 10
    1 2 11
    3 13
    2 5
    3 7
    2 8
    2 10
    2 11
    3 14
    2 18
    4 9

    样例输出

    2
    2
    2
    4
    3
    5
    5
    7
    8
    11

    数据范围与提示

     

    【数据范围】
    对于10% 的数据,1 ≤ n ≤ 10^3

     

    对于40% 的数据,1 ≤ n ≤ 10^5

     

    对于100% 的数据,1 ≤ n ≤ 10^8,1 ≤ m ≤ 105

     

    输入保证对于所有的操作1,2,3,x 必然已经出现在队列中,同时对于所有操作1,1 ≤ y ≤ 2 ×10^8,并且y 没有出现在队列中。对于所有操作4,保证1 ≤ k ≤ n。

    solution
    可以发现1e8的数据啥也开不起来。
    我们考虑用 splay 维护一段区间,这样的状态数是m了。
    还是以splay的大小关系表示排名,节点维护区间长度。
    对于1操作,我们用两个map将编号对应到 1~1e8
    对于2.3操作,我们找到包含这个点的区间。然后把它拆成三块。
    对于4操作,splay上找k大即可。
    现在还剩一个问题,怎么找到包含某个点的区间。
    邵神犇:用一个set把当前所有区间的左端点存起来,每次找第一个包含它的。(%%%
    那就解决啦。
     
    然而这题全是细节。。。
    1.找第k大时找到了也要减左儿子
    if(tr[ls].sz>=x)k=ls;
    else if(tr[ls].sz+tr[k].r-tr[k].l+1>=x){x-=tr[ls].sz;break;}
    else x-=tr[ls].sz+tr[k].r-tr[k].l+1,k=tr[k].ch[1];

    2.insert完要维护一整条链。

    3.区间的size为r-l+1

    4.根的前驱不是左儿子!!根的后驱不是右儿子!!(可能是我傻逼)

    5.注意分讨x=l x=r x=l=r的特殊情况

    6.节点开2m~3m

    #include<cstdio>
    #include<iostream>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<map>
    #include<set>
    using namespace std;
    int n,m,rt,ans,cnt;
    struct node{
        int sz,l,r,ch[2],f;
    }tr[200006];
    set<int>s;
    map<int,int>ls,dy,id;
    void print_a(int k){
        if(!k)return;
        print_a(tr[k].ch[0]);
        for(int i=tr[k].l;i<=tr[k].r;i++)printf("%d ",i);
        print_a(tr[k].ch[1]);
    }
    bool get(int x){return tr[tr[x].f].ch[1]==x;}
    void wh(int x){
        tr[x].sz=tr[tr[x].ch[0]].sz+tr[tr[x].ch[1]].sz+tr[x].r-tr[x].l+1;
    }
    void rotate(int x){
        int y=tr[x].f,z=tr[y].f;
        int wx=get(x),wy=get(y);
        tr[z].ch[wy]=x;tr[x].f=z;
        tr[y].ch[wx]=tr[x].ch[wx^1];tr[tr[x].ch[wx^1]].f=y;
        tr[x].ch[wx^1]=y;tr[y].f=x;
        wh(y);wh(x);
    }
    void splay(int x,int g){
        while(tr[x].f!=g){
            int y=tr[x].f,z=tr[y].f;
            if(z!=g)rotate(get(x)==get(y)?y:x);
            rotate(x);
        }
        if(!g)rt=x;
    }
    void ask(int t){
        set<int>::iterator pos;
        pos=s.upper_bound(t);pos--;
        int k=id[*pos];
        //cout<<"aaa "<<t<<' '<<*pos<<' '<<k<<' '<<tr[k].l<<' '<<tr[k].r <<endl;
        splay(k,0);
        ans=tr[tr[rt].ch[0]].sz;
        ans+=t-(*pos)+1;
        printf("%d\n",ans);
    }
    void insert_Front(int x){
        int k=rt;
        while(tr[k].ch[0])k=tr[k].ch[0];
        int p=++cnt;
        tr[p].l=tr[p].r=x;tr[p].sz=1;
        tr[k].ch[0]=p;tr[p].f=k;
        for(int i=p;i;i=tr[i].f)wh(i);
        s.insert(x);id[x]=cnt;
        splay(p,0);
    }
    void insert_Bottom(int x){
        int k=rt;
        while(tr[k].ch[1])k=tr[k].ch[1];
        int p=++cnt;
        tr[p].l=tr[p].r=x;tr[p].sz=1;
        tr[k].ch[1]=p;tr[p].f=k;
        for(int i=p;i;i=tr[i].f)wh(i);
        s.insert(x);id[x]=cnt;
        splay(p,0);
    //cout<<p<<' '<<tr[p].l<<' '<<tr[p].r<<' '<<tr[p].f<<endl; 
    }
    void add(int x,int opt){
        int l=tr[rt].l,r=tr[rt].r;
        if(l==r){
            int ls=tr[rt].ch[0],rs=tr[rt].ch[1];
            if(!ls)rt=rs,tr[rs].f=0;
            else if(!rs)rt=ls,tr[ls].f=0;
            else {
                while(tr[ls].ch[1])ls=tr[ls].ch[1];
                while(tr[rs].ch[0])rs=tr[rs].ch[0];
                splay(ls,0);splay(rs,ls);
                //print_a(rt);puts("");puts("------");
                tr[tr[rt].ch[1]].ch[0]=0;
                wh(tr[rt].ch[1]);wh(rt);
                //print_a(rt);puts("");puts("------");
            }
        }
        else if(x==l){
            
            tr[rt].l=x+1,wh(rt);
            s.insert(x+1);id[x+1]=rt;
        }
        else if(x==r){
            tr[rt].r=x-1,wh(rt);
        }
        else {
            int k=++cnt;
            tr[k].l=x+1;tr[k].r=tr[rt].r;
            tr[rt].r=x-1;
            int rs=tr[rt].ch[1];
            if(rs){tr[k].ch[1]=rs;tr[rs].f=k;}
            tr[rt].ch[1]=k;tr[k].f=rt;
            wh(k);wh(rt);
            //printf("id%d l=%d r=%d rs=%d k=%d\n",rt,tr[rt].l,tr[rt].r,tr[rt].ch[1],k);
            //printf("kid%d kl=%d lr=%d\n",k,tr[k].l,tr[k].r);
            s.insert(x+1);id[x+1]=k;
            
        }
        if(!opt)insert_Front(x);
        else insert_Bottom(x);
    }
    void Kth(int x){
        int k=rt;
        while(1){
            //printf("k:%d l=%d r=%d\n",k,tr[k].l,tr[k].r);
            int ls=tr[k].ch[0];
            //printf("sz:%d\n",tr[ls].sz);
            if(tr[ls].sz>=x)k=ls;
            else if(tr[ls].sz+tr[k].r-tr[k].l+1>=x){x-=tr[ls].sz;break;}
            else x-=tr[ls].sz+tr[k].r-tr[k].l+1,k=tr[k].ch[1];
        }
        //cout<<tr[k].l<<' '<<x<<endl;
        int f=tr[k].l+x-1;
        ans=dy[f];if(!ans)ans=f;
        printf("%d\n",ans);
    }
    
    int main()
    {
        freopen("test.in","r",stdin);
        freopen("test.out","w",stdout);
        cin>>n>>m;
        rt=1;cnt=1;
        tr[1].l=1,tr[1].r=n,tr[1].sz=n;
        s.insert(1);id[1]=1;
        ans=0;
        //print_a(rt);puts("");
        for(int i=1,op,x,y;i<=m;i++){
            scanf("%d%d",&op,&x);x-=ans;
            if(op==1){
                scanf("%d",&y);
                y-=ans;
                int t=ls[x];if(!t)t=x;
                ls[y]=t;dy[t]=y;
                ask(t);
            }
            if(op==2){
                int t=ls[x];if(!t)t=x;
                ask(t);add(t,0);
            }
            if(op==3){
                int t=ls[x];if(!t)t=x;
                ask(t);add(t,1);
            }
            if(op==4){
                Kth(x);
            }
            //cout<<"root "<<rt<<endl;
            //print_a(rt);puts("");puts("------");
        }
        return 0;
    }
    View Code

     

     
    posted @ 2019-02-19 15:17 liankewei123456 阅读(...) 评论(...) 编辑 收藏
    展开全文
  • [SCOI2014]方伯伯的OJ

    2019-09-23 23:23:28
    这里是洛谷题目链接:[SCOI2014]方伯伯的OJ 题目描述 方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。Oj上注册了n个用户,编号为1~n“,一开始他们按照编号排名。 方伯伯会按照心情对这些用户做以下四种...

    这里是洛谷题目链接:[SCOI2014]方伯伯的OJ

    题目描述

    方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。Oj上注册了n个用户,编号为1~n“,一开始他们按照编号排名。

    方伯伯会按照心情对这些用户做以下四种操作,修改用户的排名和编号:

    1.操作格式为1 x y,意味着将编号为x的用户编号改为y,而排名不变,执行完该操作后需要输出该用户在队列中的位置,数据保证x必然出现在队列中,同时1,是一个当前不在排名中的编号。

    2.操作格式为2 x,意味着将编号为x的用户的排名提升到第一位,执行完该操作后需要输出执行该操作前编号为z用户的排名。

    3.操作格式为3 x,意味着将编号为z的用户的排名降到最后一位,执行完该操作后需要输出执行该操作前编号为z用户的排名。

    4.操作格式为4 k,意味着查询当前排名为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现在你截获了方伯伯的所有操作,希望你能给出结果。

    输入输出格式

    输入格式:

     

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

     

    输出格式:

     

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

     

    输入输出样例

    输入样例#1: 
    10 10
    1 2 11
    3 13
    2 5
    3 7
    2 8
    2 10
    2 11
    3 14
    2 18
    4 9
    输出样例#1: 
    2
    2
    2
    4
    3
    5
    5
    7
    8
    11

    说明

    对于 100% 的数据,1 <= n <= 10^8,1 <= m <= 10^5

    输入保证对于所有的操作 1,2,3,x 必然已经出现在队列中,同时对于所有操作 1,1 <= y <= 2 * 10^8,并且

    y 没有出现在队列中。

    对于所有操作 4,保证 1 <= k <= n。

     

    先推荐一下巨佬同学oldfish的博客:[SCOI2014]方伯伯的OJ(偶尔会上不了)

    首先看到了这个神奇的N,很显然是不能开10^8个节点来保存下所有的节点,再看M只有10^5,意思就是最多我只会用到10^5个点,但是事先我并不知道这些点是什么,所以也不能直接开10^5个节点,那么我们想应该如何才能保存下这些点.因为我直接用数组存不下,所以我们考虑先用一个节点表示一个区间,然后我们在要用到这个区间内的数时,再把这个节点分裂开.什么意思呢?比如我们想要找到第x个数,然后现在只有一个节点root,包括了1~n的范围,那么我们就把这个节点拆开,变成t[root].ch[0]保存1~x-1,t[root].ch[1]保存x+1~n,和一个我们需要的节点x.这样我们就把空间省了下来.

    然后各个操作就是splay的基本操作了,将一个点提到第一位就是将它的中序遍历位置变到第一位,可以先将它旋到根,然后把后继旋到根下面,把它的左子树插到后继的左边。

    这里就先不放代码了代码我还没有打,实在是太难打了.....

     

    时隔一年,远在致远星上的我想起了这道题(其实是看见同学也在写这题),于是回来把这题的代码给补了,康康之前写的博客,发现讲的东西实在是少,这里再补充一下:

    1. 平衡树的中序遍历结果表示了排名,节点上的值记录节点的编号,这样我们就可以通过平衡树建立节点在树中的编号到节点的存储编号/排名的映射.
    2. 因为中序遍历只能维护一个东西,所以要通过存储编号找节点需要用map来实现,也就是map[i]记录右端点为i的树中的节点编号,这样就可以从区间找到节点了.

     

    再补充一下map使用lower_bound的方法:

    在map中lower_bound相当与是对第一关键字进行二分,找到第一个大于等于第一关键字的元素,返回这个元素的迭代器,而这个迭代器所包含的值的类型是一个pair,其中它的第一关键字也就是第一个大于等于lower_bound查询的元素的值,第二关键字相当于map[第一关键字].

     

    然后就是分离节点包含区间的过程中的各种细节了...看看代码吧.

     

      1 #include<bits/stdc++.h>
      2 using namespace std;
      3 const int N = 2e5+5;
      4 const int inf = 0x3f3f3f3f;
      5 
      6 int n, m, cnt = 0, root = 0, lans = 0;
      7 
      8 struct splay{ int ch[2], l, r, size, fa, val; }t[N];
      9 
     10 map <int, int> vis;
     11 
     12 bool get(int x){ return x == t[t[x].fa].ch[1]; }
     13 
     14 void up(int x){ t[x].size = t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].r-t[x].l+1; }
     15 
     16 int newnode(int val, int l, int r){
     17     t[++cnt].val = val, t[cnt].size = r-l+1, t[cnt].l = l, t[cnt].r = r;
     18     return cnt;
     19 }
     20 
     21 void rotate(int x){
     22     int f = t[x].fa, gf = t[f].fa, d1 = get(x), d2 = get(f);
     23     t[t[x].ch[d1^1]].fa = f, t[f].ch[d1] = t[x].ch[d1^1];
     24     t[x].ch[d1^1] = f, t[f].fa = x;
     25     t[gf].ch[d2] = x, t[x].fa = gf;
     26     up(f), up(x);
     27 }
     28 
     29 void splay(int x, int goal){
     30     while(t[x].fa != goal){
     31         int f = t[x].fa, gf = t[f].fa, d1 = get(x), d2 = get(f);
     32         if(gf != goal){
     33             if(d1 == d2) rotate(f);
     34             else rotate(x);
     35         }
     36         rotate(x);
     37     }
     38     if(goal == 0) root = x;
     39 }
     40 
     41 void insert(int now, int k){
     42     if(!k){
     43         splay(2, 0); int x = t[root].ch[1];
     44         while(t[x].ch[0]) x = t[x].ch[0];
     45         t[now].fa = x, t[x].ch[0] = now;
     46     } else {
     47         splay(3, 0); int x = t[root].ch[0];
     48         while(t[x].ch[1]) x = t[x].ch[1];
     49         t[now].fa = x, t[x].ch[1] = now;
     50     }
     51     splay(now, 0);
     52 }
     53 
     54 int kth(int k){
     55     int x = root, son;
     56     while(1){
     57         if(k <= t[son = t[x].ch[0]].size) x = son;
     58         else if(k > t[son].size+t[x].r-t[x].l+1)
     59             k -= t[son].size+t[x].r-t[x].l+1, x = t[x].ch[1];
     60         else return x;
     61     }
     62 }
     63 
     64 void delet(int k){
     65     int pre = kth(k-1), nex = kth(k+1), x;
     66     splay(pre, 0), splay(nex, pre); x = t[nex].ch[0];
     67     t[nex].ch[0] = 0, splay(nex, 0);
     68 }
     69 
     70 void split(int x, int num){
     71     int son, ls, rs;
     72     if(t[x].l == t[x].r) return;
     73     if(t[x].l == num || t[x].r == num){
     74         if(t[x].l != num){
     75             son = newnode(t[x].l, t[x].l, num-1);
     76             t[x].l = num, t[x].size = t[x].r-t[x].l+1, t[x].val = num;
     77             t[son].ch[0] = t[x].ch[0], t[t[x].ch[0]].fa = son;
     78             t[x].ch[0] = son, t[son].fa = x; up(son), up(x);
     79             vis[num-1] = son, vis[num] = x;
     80         } else {
     81             son = newnode(num+1, num+1, t[x].r);
     82             vis[t[x].r] = son, vis[num] = x;
     83             t[x].r = num, t[x].size = t[x].r-t[x].l+1, t[x].val = num;
     84             t[son].ch[1] = t[x].ch[1], t[t[x].ch[1]].fa = son;
     85             t[x].ch[1] = son, t[son].fa = x; up(son), up(x);
     86         }
     87     } else {
     88         ls = newnode(t[x].l, t[x].l, num-1);
     89         rs = newnode(num+1, num+1, t[x].r);
     90         vis[num-1] = ls, vis[t[x].r] = rs, vis[num] = x;
     91         t[x].l = t[x].r = num, t[x].size = 1, t[x].val = num;
     92         t[ls].ch[0] = t[x].ch[0], t[t[x].ch[0]].fa = ls;
     93         t[x].ch[0] = ls, t[ls].fa = x; up(ls), up(x);
     94         t[rs].ch[1] = t[x].ch[1], t[t[x].ch[1]].fa = rs;
     95         t[x].ch[1] = rs, t[rs].fa = x; up(rs), up(x);
     96     }
     97 }
     98 
     99 void init(){
    100     root = 1, cnt = 3, t[1].l = 1, t[1].r = n, t[1].val = n, vis[n] = 1;
    101     t[1].size = n+2, t[1].ch[0] = 2, t[1].ch[1] = 3;
    102     t[2].fa = t[3].fa = t[2].size = t[3].size = 1, t[2].val = -inf, t[3].val = inf;
    103 }
    104 
    105 int main(){
    106     ios::sync_with_stdio(false);
    107     int opt, x, y, pos, now, k; cin >> n >> m; init();
    108     for(int i = 1; i <= m; i++){
    109         cin >> opt >> x, x -= lans;
    110         if(opt == 1){
    111             cin >> y, y -= lans;
    112             pos = (*vis.lower_bound(x)).first, now = vis[pos];
    113             splay(now, 0), split(now, x);
    114             vis[x] = 0, vis[y] = now, t[now].val = y;
    115             cout << (lans = t[t[now].ch[0]].size) << endl;
    116         }
    117         if(opt == 2 || opt == 3){
    118             pos = (*vis.lower_bound(x)).first, now = vis[pos];
    119             splay(now, 0), split(now, x);
    120             k = t[t[now].ch[0]].size+1;
    121             cout << (lans = k-1) << endl;
    122             delet(k), insert(now, opt-2);
    123         }
    124         if(opt == 4){
    125             now = kth(x+1), splay(now, 0);
    126             if(t[now].l != t[now].r) split(now, x-t[t[now].ch[0]].size+t[now].l); //
    127             cout << (lans = t[now].val) << endl;
    128         }
    129     }
    130     return 0;
    131 }

     

    转载于:https://www.cnblogs.com/BCOI/p/8576989.html

    展开全文
  • BZOJ3595: [Scoi2014]方伯伯的Oj Description 方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。Oj上注册了n个用户,编号为1~”,一开始他们按照编号排名。方伯伯会按照心情对这些用户做以下四种操作,...

    BZOJ3595: [Scoi2014]方伯伯的Oj

    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个操作的输出。

    Sample Input

    10 10
    1 2 11
    3 13
    25
    37
    28
    2 10
    2 11
    3 14
    2 18
    4 9

    Sample Output

    2
    2
    2
    4
    3
    5
    5
    7
    8
    11

    HINT

    对于 100% 的数据,1 ≤ n ≤ 10^8,1 ≤ m ≤ 10^5
    输入保证对于所有的操作 1,2,3,x 必然已经出现在队列中,同时对于所有操作 1,1 ≤ y ≤ 2 × 10^8,并且y 没有出现在队列中。
    对于所有操作 4,保证 1 ≤ k ≤ n。

    题解Here!

    首先,应该能看出这是一个$Splay$的毒瘤题。
    $splay$维护每个用户,再用一个$map$记录每个出现的编号在$Splay$中对应节点。
    这个题就做完了
    吗?
    并不!
    因为$n<=10^8$。。。
    这玩意好烦啊。。。
    我们可以通过构$(kan)$造$(ti)$法$(jie)$得出一种方法:
    我们注意到有效询问只有$m<=10^5$个。
    也就是说,我们的$Splay$最多只会与$3\times 10^5$个节点有关。
    那么我们可以把那些暂时不用的节点全部合并,等到要用的时候再拆点。
    这样就可以保证不会$TLE/MLE$了。
    然后注意的细节还蛮多的,看代码吧。。。
    吐槽:做完这题就会感觉到,维护一个像样的$OJ$真麻烦,尤其是洛谷、LOJ、UOJ等高效的$OJ$,但是$BZOJ$就算了吧。。。
    附代码:
    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<map>
    #define MAXN 1000010
    using namespace std;
    map<int,int> pos;
    int n,m;
    int size=0,root=0;
    struct Splay{
    	int f,s,son[2];
    	int l,r;
    }a[MAXN];
    inline int read(){
    	int date=0,w=1;char c=0;
    	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    	return date*w;
    }
    inline void pushup(int rt){
    	if(!rt)return;
    	a[rt].s=a[a[rt].son[0]].s+a[a[rt].son[1]].s+a[rt].r-a[rt].l+1;
    }
    inline void turn(int rt,int k){
    	int x=a[rt].f,y=a[x].f;
    	a[x].son[k^1]=a[rt].son[k];
    	if(a[rt].son[k])a[a[rt].son[k]].f=x;
    	a[rt].f=y;
    	if(y)a[y].son[a[y].son[1]==x]=rt;
    	a[x].f=rt;
    	a[rt].son[k]=x;
    	pushup(x);pushup(rt);
    }
    void splay(int rt,int ancestry){
    	while(a[rt].f!=ancestry){
    		int x=a[rt].f,y=a[x].f;
    		if(y==ancestry)turn(rt,a[x].son[0]==rt);
    		else{
    			int k=a[y].son[0]==x?1:0;
    			if(a[x].son[k]==rt){turn(rt,k^1);turn(rt,k);}
    			else{turn(x,k);turn(rt,k);}
    		}
    	}
    	if(ancestry==0)root=rt;
    }
    int newnode(int l,int r){
    	int rt=++size;
    	a[rt].son[0]=a[rt].son[1]=a[rt].f=0;
    	a[rt].l=l;a[rt].r=r;
    	a[rt].s=r-l+1;
    	return rt;
    }
    inline void buildtree(){
    	root=newnode(1,n);
    	a[root].s=n;
    	pos[n]=root;
    }
    int kth(int rt,int k){
    	if(k>a[rt].s)return 0;
    	while(k){
    		int s=a[a[rt].son[0]].s+a[rt].r-a[rt].l+1;
    		if(a[a[rt].son[0]].s<k&&k<=s){
    			k-=a[a[rt].son[0]].s;
    			break;
    		}
    		if(s<k){
    			k-=s;
    			rt=a[rt].son[1];
    		}
    		else rt=a[rt].son[0];
    	}
    	return a[rt].l+k-1;
    }
    void remove(int rt){
    	int front=a[rt].son[0],next=a[rt].son[1];
    	while(a[front].son[1])front=a[front].son[1];
    	while(a[next].son[0])next=a[next].son[0];
    	if(!front&&!next)root=0;
    	else if(!front){
    		splay(next,root);
    		root=next;
    		a[root].f=0;
    		a[rt].son[0]=a[rt].son[1]=0;
    		a[rt].s=1;
    	}
    	else if(!next){
    		splay(front,root);
    		root=front;
    		a[root].f=0;
    		a[rt].son[0]=a[rt].son[1]=0;
    		a[rt].s=1;
    	}
    	else{
    		splay(front,0);splay(next,front);
    		a[next].son[0]=a[rt].f=0;
    		a[rt].s=1;
    		pushup(next);pushup(front);
    	}
    }
    void split(int x,int id){
    	if(a[x].l==a[x].r)return;
    	int l=a[x].l,r=a[x].r,lson,rson;
    	if(l==id){
    		rson=newnode(l+1,r);
    		pos[r]=rson;pos[id]=x;
    		a[rson].son[1]=a[x].son[1];
    		a[a[rson].son[1]].f=rson;
    		a[x].son[1]=rson;a[rson].f=x;
    		a[x].r=l;
    		pushup(rson);pushup(x);
    	}
    	else if(r==id){
    		lson=newnode(l,r-1);
    		pos[r-1]=lson;pos[id]=x;
    		a[lson].son[0]=a[x].son[0];
    		a[a[lson].son[0]].f=lson;
    		a[x].son[0]=lson;a[lson].f=x;
    		a[x].l=r;
    		pushup(lson);pushup(x);
    	}
    	else{
    		lson=newnode(l,id-1);rson=newnode(id+1,r);
    		pos[id]=x;pos[id-1]=lson;pos[r]=rson;
    		a[lson].son[0]=a[x].son[0];a[rson].son[1]=a[x].son[1];
    		a[a[lson].son[0]].f=lson;a[a[rson].son[1]].f=rson;
    		a[x].son[0]=lson;a[x].son[1]=rson;a[lson].f=a[rson].f=x;
    		a[x].l=a[x].r=id;
    		pushup(lson);pushup(rson);pushup(x);
    	}
    	splay(x,0);
    }
    inline int change(int x,int y){
    	int k=pos.lower_bound(x)->second,s;
    	split(k,x);
    	splay(k,0);
    	s=a[k].s-a[a[k].son[1]].s;
    	a[k].l=a[k].r=y;
    	pos[y]=k;
    	return s;
    }
    inline void push_head(int rt){
    	if(!root){root=rt;return;}
    	int fa=root;
    	while(a[fa].son[0]){
    		a[fa].s++;
    		fa=a[fa].son[0];
    	}
    	a[fa].s++;
    	a[fa].son[0]=rt;
    	a[rt].f=fa;
    	splay(rt,0);
    }
    inline void push_last(int rt){
    	if(!root){root=rt;return;}
    	int fa=root;
    	while(a[fa].son[1]){
    		a[fa].s++;
    		fa=a[fa].son[1];
    	}
    	a[fa].s++;
    	a[fa].son[1]=rt;
    	a[rt].f=fa;
    	splay(rt,0);
    }
    inline int make_head(int x){
    	int k=pos.lower_bound(x)->second,s;
    	split(k,x);
    	splay(k,0);
    	s=a[k].s-a[a[k].son[1]].s;
    	remove(k);
    	push_head(k);
    	return s;
    }
    inline int make_last(int x){
    	int k=pos.lower_bound(x)->second,s;
    	split(k,x);
    	splay(k,0);
    	s=a[k].s-a[a[k].son[1]].s;
    	remove(k);
    	push_last(k);
    	return s;
    }
    void work(){
    	int f,x,y,last=0;
    	while(m--){
    		f=read();x=read()-last;
    		switch(f){
    			case 1:{
    				y=read()-last;
    				last=change(x,y);
    				printf("%d\n",last);
    				break;
    			}
    			case 2:{
    				last=make_head(x);
    				printf("%d\n",last);
    				break;
    			}
    			case 3:{
    				last=make_last(x);
    				printf("%d\n",last);
    				break;
    			}
    			case 4:{
    				last=kth(root,x);
    				printf("%d\n",last);
    				break;
    			}
    		}
    	}
    }
    void init(){
    	n=read();m=read();
    	buildtree();
    }
    int main(){
    	init();
    	work();
        return 0;
    }
    

     

    转载于:https://www.cnblogs.com/Yangrui-Blog/p/9678400.html

    展开全文
  • 「SCOI2014」方伯伯的 OJ 和列队有点像,平衡树点分裂维护即可 但是需要额外用个set之类的对编号查找点的位置 插入完了后记得splay,删除时注意特判好多东西 Code: #include <cstdio> #include <cctype>...

    「SCOI2014」方伯伯的 OJ

    和列队有点像,平衡树点分裂维护即可

    但是需要额外用个set之类的对编号查找点的位置

    插入完了后记得splay,删除时注意特判好多东西


    Code:

    #include <cstdio>
    #include <cctype>
    #include <set>
    const int N=2e5+10;
    template <class T>
    void inline read(T &x)
    {
        x=0;char c=getchar();
        while(!isdigit(c)) c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
    }
    #define ls ch[now][0]
    #define rs ch[now][1]
    #define fa par[now]
    int siz[N],ch[N][2],L[N],R[N],par[N],tot,root;
    void connect(int f,int now,int typ){ch[fa=f][typ]=now;}
    int identity(int now){return ch[fa][1]==now;}
    void updata(int now){siz[now]=siz[ls]+siz[rs]+R[now]+1-L[now];}
    void Rotate(int now)
    {
        int p=fa,typ=identity(now);
        connect(p,ch[now][typ^1],typ);
        connect(par[p],now,identity(p));
        connect(now,p,typ^1);
        updata(p),updata(now);
    }
    void splay(int now,int to)
    {
        to=par[to];
        if(!to) root=now;
        for(;fa!=to;Rotate(now))
            if(par[fa]!=to)
                Rotate(identity(now)^identity(fa)?now:fa);
    }
    struct yuucute
    {
        int x,id;
        yuucute(){}
        yuucute(int X,int Id){x=X,id=Id;}
        bool friend operator <(yuucute a,yuucute b){return a.x<b.x;}
        bool friend operator ==(yuucute a,yuucute b){return a.x==b.x;}
    };
    std::set <yuucute> s;
    std::set <yuucute>::iterator it;
    #define yuulovely 1
    int New(int l,int r)
    {
        siz[++tot]=r+1-l,L[tot]=l,R[tot]=r;
        return tot;
    }
    int getnum(int x)
    {
        it=--s.upper_bound(yuucute(x,yuulovely));
        return it->id;
    }
    void split(int now,int x)
    {
        if(L[now]==R[now]) return;
        s.erase(yuucute(L[now],yuulovely));
        s.insert(yuucute(x,now));
        int lson=ls,rson=rs;
        if(L[now]<x)
        {
            int lp=New(L[now],x-1);
            s.insert(yuucute(L[now],lp));
            connect(now,lp,0);
            connect(lp,lson,0);
            updata(lp);
        }
        if(x<R[now])
        {
            int rp=New(x+1,R[now]);
            s.insert(yuucute(x+1,rp));
            connect(now,rp,1);
            connect(rp,rson,1);
            updata(rp);
        }
        L[now]=R[now]=x;
    }
    void insl(int now,int ins)
    {
        ++siz[now];
        if(ls) insl(ls,ins);
        else connect(now,ins,0);
    }
    void insr(int now,int ins)
    {
        ++siz[now];
        if(rs) insr(rs,ins);
        else connect(now,ins,1);
    }
    int getlef(int now)
    {
        if(ls) return getlef(ls);
        return now;
    }
    void erase(int now)
    {
        if(!rs) {par[root=ls]=0,ls=0,updata(now);return;}
        splay(root=getlef(rs),rs);
        connect(root,ls,0);
        updata(root),par[root]=0;
        ls=rs=0,updata(now);
    }
    int getrank(int now,int &x)
    {
        if(siz[ls]>=x) return getrank(ls,x);
        x-=siz[ls];
        if(x<=R[now]-L[now]+1) return now;
        x-=R[now]-L[now]+1;
        return getrank(rs,x);
    }
    int main()
    {
        freopen("data.in","r",stdin);
        freopen("data.out","w",stdout);
        int n,m;
        read(n),read(m);
        root=New(1,n);
        s.insert(yuucute(1,root));
        int op,x,y,las=0;
        for(int i=1;i<=m;i++)
        {
            read(op),read(x);
            x-=las;
            if(op==1)
            {
                read(y),y-=las;
                int now=getnum(x);
                splay(now,root);
                printf("%d\n",las=siz[ls]+x+1-L[now]);
                split(now,x);
                L[now]=R[now]=y;
                s.erase(yuucute(x,yuulovely));
                s.insert(yuucute(y,now));
            }
            else if(op==2)
            {
                int now=getnum(x);
                splay(now,root);
                printf("%d\n",las=siz[ls]+x+1-L[now]);
                split(now,x);
                erase(now);
                insl(root,now);
                splay(now,root);
            }
            else if(op==3)
            {
                int now=getnum(x);
                splay(now,root);
                printf("%d\n",las=siz[ls]+x+1-L[now]);
                split(now,x);
                erase(now);
                insr(root,now);
                splay(now,root);
            }
            else
            {
                int now=getrank(root,x);
                printf("%d\n",las=x+L[now]-1);
                splay(now,root);
            }
        }
        return 0;
    }

    2019.2.23

    转载于:https://www.cnblogs.com/butterflydew/p/10421797.html

    展开全文
  • 3595: [Scoi2014]方伯伯的Oj Time Limit: 6 SecMemory Limit: 256 MBSubmit: 102Solved: 54[Submit][Status] Description 方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。 Oj上注册了n个用户,编号为1...
  • bzoj3595: [Scoi2014]方伯伯的Oj Description 方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。 Oj上注册了n个用户,编号为1~”,一开始他们按照编号排名。方伯伯会按照心情对这些用户做以下四种操作,...
  • bzoj3595 方伯伯的oj

    2019-09-29 12:24:48
    1.把编号为$x$人编号改为$y$,保证$y$没出现过 2.把编号为$x$人提到第一名 3.把编号为$x$人怼到最后一名 4.查询排名为$x$编号 初始每个人排名 = 他编号 sol: 考虑线段树,在叶子维护一个值...
  • loj2212 方伯伯的OJ

    2019-10-08 06:23:24
    2.注意删点函数split中ins之后splay也要判断是否在区间限制内,反之有可能tot恰好是被删掉那一个而产生死循环。 3.mn从-1往下开始标号,以0来区分是否标记。   题解:splay+离散排名+区间分裂 一道...
  • P4340【SCOI2014】方伯伯的Oj问题描述输入格式 输入的第1行包含2个用空格分隔的整数n和m,表示初始用户数和操作数。 此后有m行,每行是一个询问,询问格式如上所示。 输出格式 输出包含m行。每行包含一个整数,...
  • 方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。Oj上注册了n个用户,编号为1~n“,一开始他们按照编号排名。 方伯伯会按照心情对这些用户做以下四种操作,修改用户的排名和编号: 1.操作格式为1 x y,...
  • 方伯伯的oj bzoj3594

    2016-03-30 16:58:59
    http://www.lydsy.com/JudgeOnline/problem.php?id=3594 (貌似比维护数列更恶心QAQ,虽然我只是看了一眼不想写) 这道题真够恶心,它坑了我一上午~~还是下午来时候调出来
  • 方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。Oj上注册了n个用户,编号为1~n“,一开始他们按照编号排名。 方伯伯会按照心情对这些用户做以下四种操作,修改用户的排名和编号: 1.操作格式为1 x y,...
  • 我佛了,我这么大常数写法竟然跑得还不算特别慢。。。 首先想到用一个splay按排名维护队列,那么操作都挺sb,随便写写就行了吧。 然后就发现有问题,n≤108n\leq10^8n≤108,这意味着好像不能把整棵树建出来...
  • 直接动态开点线段树,维护所有可能出现位置\([-m,n+m]\),并按排名排列元素,记个区间元素个数以及底层节点代表编号,再搞个map记每个编号对应在线段树中出现位置即可,跑飞快,远超平衡树。 #include<...
  •  考虑到n范围巨大而m范围是正常1e5, 显然要动态开点,一个点代表一个区间。但这道题只用一棵平衡树可能不太好做,于是有dalao就写了两棵平衡树, 显然我这种一棵平衡树都要写挂人是不可能去完成两棵平衡树...
  • BZOJ-3595 方伯伯的OJ 双Treap

    千次阅读 2017-05-30 10:49:04
    大家都很强, 可与之共勉。2017年Rank6/************************************************************** Problem: 3595 User: Lazer2001 Language: C++ Result: Accepted Time:2252 ms Memory:16952 kb
  • 方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。 Oj上注册了n个用户,编号为1~”,一开始他们按照编号排名。方伯伯会按照心情对这些用户做以下四种操作,修改用户的排名和编号: 1.操作格式为1 x y,意味...
  • 方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。 Oj上注册了n个用户,编号为1~”,一开始他们按照编号排名。方伯伯会按照心情对这些用户做以下四种操作,修改用户的排名和编号: 1.操作格式为1 x y,意味...
  • 蒟蒻终于做到一道方伯伯的题了…… 调了一个上午一直TLE(发现自己打了好久的splay板子竟然是错的这种丢人事情我就不说了) 很明显,要建两棵树,$T1$维护排名,$T2$维护编号,$T2$表示编号为$x$的点在$T1$中的...

空空如也

空空如也

1 2 3
收藏数 58
精华内容 23
关键字:

方伯伯的oj