平衡树试炼场 R.I.P.
第一道 NOI 难度纪念（没做过 NOI 的蒟蒻表示很惊恐，无法区分省选与 NOI 难度）（也许就是省选难度呢)

Problem

原题讲得很不清楚我就来多 bb 两句
给定 n，最开始有个 1~n 编号的序列
然后作以下操作
1 x y 把原 x 编号改为 y 编号，并输出 x 编号的排名；保证 x 在序列中，y 不在序列中
2 x 把 x 编号提到第 1，并输出原排名
3 x 把 x 编号提到最后，并输出原排名
4 x 输出排名为 x 的编号

范围： $n<=10^8,\ m<=10^5$
数据强制在线

Solution

我觉得我的做法可能没有普遍适用性，毕竟很鬼畜

一眼看过去是道维护序列的题目，然后就是 splay，书架那道题。
但是范围很蛋疼。1e8？我总不可能建 1e8 个点。
题解也看不太懂。我一开始也想过合并区间为一个点，到要用的时候再分裂，但不知道怎么实现。
然后看到题解有一个人说：可以合并点，要用的时候再分裂，心中就稳了，准备朝这个方向去写。（虽然我看不懂他是怎么用 map 写的 逃 ）

这么说吧，我的实现可能有点难懂.... 我尝试讲清楚
一开始定义 split(x)操作为把编号为 x 的点（或包含 x 的合并点）旋到根
如果这是个合并点就拆，不是就返回。
怎么拆？
给点三个值,l,r,v。v 代表这个点的编号，合并点的编号为 0.l,r 代表合并点的区间，如果 l == r 就是非合并点。
那么如果要用的值是 x，则把这个合并点拆成两个合并点和一个非合并点。
维护非合并点的大小和 l，r。我们把根的左子树的最大值旋到最上，右子树的最小值旋到最上。那么把这两个非合并点分别插到左子树的右子树，和右子树的左子树。如果某个子树为空则另判。

一开始我是这么愉快地想的，然后想到一个难题。我怎么记录编号为 x 的点的节点的指针？
map？不行，如果它是在一个合并点里（还没调用），我不知道它所属合并节点的位置。
那么我就只能另建一棵树了。一棵树里作主要的序列操作，另一棵树里用于查对应节点排名的点，另一颗树的每个点都与这棵树里的每个点有一一对应关系。

另一棵树的作用我们再详细讲讲。假设你知道了某个编号为 x 的节点的 原始排名（编号），那么你就可以在右边的树找到这个节点的所属节点 / 合并点（因为它的序列顺序并没有更改），而这个你找到的节点 / 合并点里面含有一个叫 con 的指针，指向第一棵树的指针。这样我们就可以调查到编号为 x 的点的节点在第一棵树里的指针，则可以使用 splay 操作了。

怎么知道某个编号为 x 的节点的原始排名？太简单了不讲。自己看代码。

与此同时，我们需要在各种地方调查某个点是属于合并点还是节点。对每个调查的编号都进行 split 操作，以保证自己调查的编号是一个节点而非合并点。
以及 split 操作需要对两棵树都进行拆点。

这样操作的话，最后 splay 树的节点数就会是 m。与 n 就无关了。

实现鬼畜对不对？

我觉得我写得出来也是很鬼畜了。

Code

// Code by ajcxsu
// Problem: Uncle Fang's OJ LP3285

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<map>
#define _rg register
#define INF (0x3f3f3f3f)
#define DEBUG printf("Passing %s in line %d\n",__FUNCTION__,__LINE__)
using namespace std;

const int N=1e6+10,M=1e5+10;
int n,m;


struct Node *nil;
struct Node {
    int l,r,v,c,s;
    Node *ch[2], *f, *con;
    Node(int l,int r,int v=0):l(l),r(r),v(v),c(r-l+1),s(r-l+1) { ch[0]=ch[1]=f=nil; }
    int cmp(int &k) {
        if(this==nil) return -1;
        if(k<=ch[0]->s) return 0;
        else if(k<=ch[0]->s+c) return -1;
        else { k-=ch[0]->s+c; return 1; }
    }
    int cmpb(int val) {
        if(val==v) return -1;
        return val>v;
    }
    void upd() { s=c+ch[0]->s+ch[1]->s; }
    int dir() {
        if(f==nil) return -1;
        return f->ch[1]==this;
    }
} *root, *root2;

map<int,int> pos;
void init() {
    nil=new Node(0,0,-INF);
    nil->ch[0]=nil->ch[1]=nil->f=root=nil;
    nil->s=nil->c=0;
}

void dfs(Node *x) {
    if(x==nil) return;
    dfs(x->ch[0]);
    if(x->v) printf("%d ",x->v);
    else printf("%d~%d ",x->l,x->r);
    dfs(x->ch[1]);
}

void rot(Node *x) {
    Node *y=x->f;
    int d=x->dir();
    if(d==-1) return;
    y->ch[d]=x->ch[!d];
    if(x->ch[!d]!=nil) x->ch[!d]->f=y;
    x->f=y->f;
    if(x->f!=nil) x->f->ch[y->dir()]=x;
    x->ch[!d]=y, y->f=x;
    if(y==root) root=x;
    if(y==root2) root2=x;
    y->upd();
}

void splay(Node *t,Node *x) {
    if(x==nil) return;
    while(x->f!=t) {
        Node *y=x->f, *z=y->f;
        if(z==t) rot(x);
        else if(x->dir()==y->dir()) rot(y), rot(x);
        else rot(x), rot(x);
    }
    x->upd();
}

Node* findk(Node *x,int k) {
    int d=x->cmp(k);
    if(d==-1 || x->ch[d]==nil) return x;
    return findk(x->ch[d], k);
}

void split(int val) {
    if(pos.count(val)) val=pos[val];
    splay(nil, findk(root2,val));
    Node *it=root2->con;
    splay(nil, it);
    if(it->v) return;
    if(root->l==root->r) { root->v=val; root2->v=val; return; }
    
    splay(root, findk(root->ch[0],INF)), splay(root, findk(root->ch[1],1));
    Node *a,*b;
    if(val!=root->l) {
        if(root->ch[0]!=nil) root->ch[0]->ch[1]=new Node(root->l,val-1), root->ch[0]->ch[1]->f=root->ch[0], a=root->ch[0]->ch[1];
        else root->ch[0]=new Node(root->l,val-1), root->ch[0]->f=root, a=root->ch[0];
    }
    if(val!=root->r) {
        if(root->ch[1]!=nil) root->ch[1]->ch[0]=new Node(val+1, root->r), root->ch[1]->ch[0]->f=root->ch[1], b=root->ch[1]->ch[0];
        else root->ch[1]=new Node(val+1,root->r), root->ch[1]->f=root, b=root->ch[1];
    }
    root->l=root->r=root->v=val;
    root->c=1;
    root->ch[0]->upd(), root->ch[1]->upd();
    root->upd();
    
    #define root root2
    splay(root, findk(root->ch[0],INF)), splay(root, findk(root->ch[1],1));
    if(val!=root->l) {
        if(root->ch[0]!=nil) root->ch[0]->ch[1]=new Node(root->l,val-1), root->ch[0]->ch[1]->f=root->ch[0], root->ch[0]->ch[1]->con=a;
        else root->ch[0]=new Node(root->l,val-1), root->ch[0]->f=root, root->ch[0]->con=a;
    }
    if(val!=root->r) {
        if(root->ch[1]!=nil) root->ch[1]->ch[0]=new Node(val+1, root->r), root->ch[1]->ch[0]->f=root->ch[1], root->ch[1]->ch[0]->con=b;
        else root->ch[1]=new Node(val+1,root->r), root->ch[1]->f=root, root->ch[1]->con=b;
    }
    root->l=root->r=root->v=val;
    root->c=1;
    root->ch[0]->upd(), root->ch[1]->upd();
    root->upd();
    #undef root
}

int ranking(int val) {
    splay(nil,findk(root,val));
    if(!root->v) {
        split(root->l+val-root->ch[0]->s-1);
        return root->v;
    }
    return root->v;
}

int change(int f,int t) {
    split(f);
    root->v=t;
    auto it=pos.find(f);
    if(it==pos.end()) pos[t]=f;
    else {
        pos[t]=it->second;
        pos.erase(it);
    }
    return root->ch[0]->s+1;
}

int toup(int x) {
    int ret=0;
    split(x);
    ret=root->ch[0]->s+1;
    splay(root,findk(root->ch[1],1));
    if(root->ch[1]==nil) swap(root->ch[0],root->ch[1]);
    else {
        swap(root->ch[1]->ch[0],root->ch[0]);
        root->ch[1]->ch[0]->f=root->ch[1];
        root->ch[1]->upd();
    }
    return ret;
}

int tobot(int x) {
    int ret=0;
    split(x);
    ret=root->ch[0]->s+1;
    splay(root,findk(root->ch[0],INF));
    if(root->ch[0]==nil) swap(root->ch[0], root->ch[1]);
    else {
        swap(root->ch[0]->ch[1], root->ch[1]);
        root->ch[0]->ch[1]->f=root->ch[0];
        root->ch[0]->upd();
    }
    return ret;
}

inline void gn(int &x) {
    x=0;
    _rg char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

int main() {
    init();
    gn(n),gn(m);
    root=new Node(1,n);
    root2=new Node(1,n);
    root2->con=root;
    int con,x,y,ans=0;
    while(m--) {
        gn(con),gn(x), x-=ans;
        if(con==1) {
            gn(y), y-=ans;
            ans=change(x,y);
        }
        else if (con==2) ans=toup(x);
        else if (con==3) ans=tobot(x);
        else ans=ranking(x);
        printf("%d\n",ans);
    }
    
    return 0;
}