[平衡树试炼场R.I.P.] [题解] LP3285 [SCOI2014] 方伯伯的OJ

平衡树试炼场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;
}

本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可
本文链接:https://acxblog.site/archives/sol_luogu_3285.html