[III (XIV) Volga Region Open Team Student Programming Contest pB][Treap][sqrt method] Time to read

原題連結
個人很喜歡這一題
大致上，這道題的難點在於如何「快速得知某頁的顏色」還有維護「塗色」操作。



這題最關鍵的地方大概是要想到主角是「顏色」而非「序列」，所以資料結構的選用必須套用在「顏色」上。像我一樣一開始想對原序列開線段樹之類的童鞋，如果你這樣做的出來請務必聯繫我<(_ _)>

總之，對每個顏色都建立一個二分搜尋樹(that is,Treap)，裡面存他出現的位置。那麼如果我們已經知道要在[L,R]裡面把顏色c通通變成顏色d的話，對應到的操作就是把c的Treap中值在[L,R]之中的節點都分裂出來，然後塞進顏色d的Treap裡。

現在這題最難(至少我這麼認為)的地方來了，如何快速得知某個頁碼的顏色呢？
考慮兩個作法：
1.直接維護page陣列，裡面放該頁是哪種顏色
2.把我們要找的那頁一個個丟進各個顏色的Treap裡，看哪個顏色的Treap中有他

第一個作法在顏色數少，每個顏色佔的位置多時很慢；第二個方法在顏色數多(很多棵Treap)，每個顏色佔的位置少時很慢。
這讓我們聯想到分類討論的方法，設置一個值lim，當顏色佔的位置低於lim時直接維護陣列，否則使用第二個查詢法。
那麼查詢的時間複雜度會是O(lim * Q + N/lim * Q) ，取lim=sqrt(N)時最優

最後還有一個細節部份是，怎麼塗那些沒有顏色的頁碼呢？
答案其實很簡單，因為一旦被塗色就不會再變成無色，我們只要維護一個「無色頁碼陣列」，讓我們能快速查到比L大的最小可用頁碼，然後一路掃到比R小的最大可用頁碼就好，這件事情最多只會執行N次。
可以用并查集或是set來完成，經過實測只有差200ms左右。(code內註解的部份就是set的作法)

時間複雜度： O(Q(sqrt(N) + logN)+ NlogN),最後的logN是並查集的複雜度

#define LL long long
#include<bits/stdc++.h>
using namespace std;
const LL maxn=300000+5;
const LL maxQ=300000+5;
unsigned ran()
{
    static unsigned x=20150306;
    return x=x*0xdefaced+1;
}
struct Node
{
    Node *lc,*rc;
    LL size,pri,val;
    void pull() {size=(lc?lc->size:0)+(rc?rc->size:0)+1;}
    Node() {}
    Node(LL x) {size=1;pri=ran();val=x;lc=rc=NULL;}
}*root[maxQ];
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,LL k,Node*& a,Node*& b)
{
    if(!t) {a=b=NULL;return;}
    else if(t->val<=k)
    {
        a=t;
        split(t->rc,k,a->rc,b);
        a->pull();
    }
    else
    {
        b=t;
        split(t->lc,k,a,b->lc);
        b->pull();
    }
}
bool find(Node* now,LL x)
{
    if(now->val==x) return 1;
    else if(now->lc && now->val>x) return find(now->lc,x);
    else if(now->rc && now->val<x) return find(now->rc,x);
    return 0;
}
set<int> large;
LL page[maxn];
void dfs(Node* now,LL c)
{
    if(!now) return;
    dfs(now->lc,c);
    page[now->val]=c;
    dfs(now->rc,c);
}
LL getcolor(LL p)
{
    for(auto it:large) if(find(root[it],p)) return it;
    return page[p];
}
void update(LL c,const LL lim)
{
    if((root[c]?root[c]->size:0)<=lim)
    {
        if(large.count(c)) large.erase(c);
        dfs(root[c],c);
    }
    else large.insert(c);
}
int fa[maxn];
int findset(int x) {return x==fa[x]?x:fa[x]=findset(fa[x]);}
set<int> totest;
LL query(LL c,LL nc,LL L,LL R,const LL lim)
{
    Node *t1,*t2,*t3;
    if(c)
    {
        split(root[c],L-1,t1,t2);
        split(t2,R,t2,t3);
        root[c]=merge(t1,t3);
        update(c,lim);

        root[nc]=merge(root[nc],t2); // should be t2 itself
    }
    
    for(LL i=findset(L);i<=R;i=findset(i))
    {
        split(root[nc],i-1,t1,t2);
        root[nc]=merge(t1,merge(new Node(i),t2));
        fa[i]=findset(i+1);
    }
/*
    vector<int> todel;
    for(auto it=totest.lower_bound(L);it!=totest.end() && (*it)<=R;it++)
    {
        todel.push_back(*it);
        split(root[nc],(*it)-1,t1,t2);
        root[nc]=merge(t1,merge(new Node(*it),t2));
    }
    for(int i=0;i<todel.size();i++) totest.erase(todel[i]);
*/
    update(nc,lim);

    return root[nc]->size;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    LL N,Q,ans=0;
    scanf("%I64d%I64d",&N,&Q);
    for(LL i=1;i<=N;i++) totest.insert(i);
    for(LL i=1;i<=N+1;i++) fa[i]=i;
    const LL lim=sqrt(N);
    for(LL i=1,L,R;i<=Q;i++)
    {
        scanf("%I64d%I64d",&L,&R);
        LL c=getcolor(L);
        ans+=query(c,i,L,R,lim);
    }
    printf("%I64d\n",ans);
}