[Coder-Strike 2014 - Finals (online edition, Div. 1) pD][Treap] Cup Trick

原題連結
可以想像一下，要能夠快速維護他給出的所有操作我們應該要能實做哪些事情呢？

如果一開始我們的序列是這樣
id :    -1 -1 -1 -1 -1 -1 .....
pos:   1  2  3  4  5  6
(-1代表編號未定)

那麼經過操作3 a後.....
id :    a -1 -1 -1 -1 -1 -1 ......
pos:  3  1  2  4  5  6  7

再經過操作6 b......
id:    b a -1 -1 -1 -1 -1 .....
pos: 6 3  1  2  4  5  7

大概可以觀察出來，我們只需要維護節點的初始位置和他是否確定id就好！
這可以很直覺的聯想到可分裂合併Treap，就不客氣的摳下去吧
最後輸出答案時再依據貪心思想把數字填進去

細節上，記得要判資訊之間是否有互相衝突。

最後說說優化部份，placement new在POJ上效果顯著，但是在codeforces上反而會拖慢速度；某個資訊衝突之後直接break輸出答案的作法，竟然比全部操作都做完才輸出還慢(其餘部份全都相同)。

我相信存在不需要平衡樹的解法，就交給後人(?了。

#include<cassert>
#include<cstdio>
#include<new>
using namespace std;
const int maxn=1000000+5;
unsigned ran()
{
    static unsigned x=20160306;
    return x=x*0xdefaced+1;
}
struct Node
{
    static Node mem[maxn];
    Node *lc,*rc;
    int pri,id,pos,size;
    void pull() {size=(lc?lc->size:0)+(rc?rc->size:0)+1;}
    Node() {}
    Node(int x) {pri=ran();id=-1;lc=rc=NULL;pos=x;size=1;}
}*root,Node::mem[maxn],*pmem=Node::mem;
Node* merge(Node* a,Node* b)
{
    if(!a || !b) return a?a:b;
    else if(a->pri > b->pri)
    {
        a->rc=merge(a->rc,b);
        a->pull();
        return a;
    }
    else
    {
        b->lc=merge(a,b->lc);
        b->pull();
        return b;
    }
}
void split(Node* t,int k,Node*& a,Node*& b)
{
    if(!t) {a=b=NULL;return;}
    else if(((t->lc?t->lc->size:0)+1)<=k)
    {
        a=t;
        split(t->rc,k-(t->lc?t->lc->size:0)-1,a->rc,b);
        a->pull();
    }
    else
    {
        b=t;
        split(t->lc,k,a,b->lc);
        b->pull();
    }
}
Node *t1,*t2,*t3;
int ans[maxn],show[maxn],cnt=1;
void dfs(Node* now)
{
    if(!now) return;
    dfs(now->lc);
    if(now->id!=-1) ans[now->pos]=now->id;
    else
    {
        while(show[cnt]) cnt++;
        ans[now->pos]=cnt;
        show[cnt]=1;
    }
    dfs(now->rc);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) root=merge(root,new (pmem++) Node(i));
    bool flag=1;
    for(int i=0,id,pos;i<m;i++)
    {
        scanf("%d%d",&id,&pos);
        if(!flag) continue;
        split(root,pos-1,t1,t2);
        split(t2,1,t2,t3);
        assert(t2);
        if(t2->id!=-1 && t2->id!=id) {flag=0;continue;}
        if(show[id]!=0 && show[id]!=t2->pos) {flag=0;continue;}
        t2->id=id;show[id]=t2->pos;
        root=merge(t2,merge(t1,t3));
    }
    if(!flag) {printf("-1\n");return 0;}
    dfs(root);
    for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n?'\n':' ');
}