[Codeforces 100186B]Time to read

這題目不好找，附上題目連結

我們先把標籤的顏色給個編號，第一次閱讀使用顏色$1$的標籤，第二次閱讀使用顏色$2$的標籤......，依此類推

說明：
$C_{i}$為第$i$頁標籤的顏色

可以發現，對於每個顏色，標籤數量只會減少 (被改成最新的顏色) 而不會增加
發現了嗎？我們只需處理分裂而不用合併！
因此，我們可以對每個顏色維護一個$splay\ tree$，第$i$棵存顏色為$i$的所有頁碼
這樣對於第$i$次閱讀操作$[l_{i},r_{i}]$，就將第$C_{l_{i}}$棵$splay\ tree$的區間$[l_{i},r_{i}]$分裂出來
於是我們就完成第$i$棵$splay\ tree$的一半了

再來是還沒讀的頁碼
可以發現，還沒讀的頁碼數量是會隨時間遞減的，因此操次數不超過$N$次
我們只要取$lower\_bound$，然後慢慢一頁一頁將範圍內的頁碼移動 (注意和複製的區別) 到第$i$棵$splay\ tree$即可

我們完成了第$i$棵$splay\ tree$了！

可是有一個問題
要怎麼得到$C_{i}$呢？
對於包含頁數少的顏色，我們可以直接建表，用頁碼查詢顏色
對於包含頁數多的顏色，直接到對應的$splay\ tree$查詢有沒有這個頁碼即可

如果包含頁數多寡以$\sqrt{M}$為邊界
對於包含頁數$\leq \sqrt{M}$的顏色
因為每種顏色最多$\sqrt{M}$個頁碼，維護表的時間複雜度不會超過$O(\sqrt{M})$
對於包含頁數$>\sqrt{M}$的顏色
因為顏色不會超過$\sqrt{M}$種，因此查詢不會超過$\sqrt{M}$棵$splay\ tree$，時間複雜度不會超過$O(\sqrt{M}\log N)$

因此我們做到了$O(\sqrt{M}\log N)$維護並查詢$C_{i}$

時間複雜度：$O(N\log N+M\sqrt{M}\log N)$

code:

#include<cstdio>
#include<cassert>
#include<map>
#include<set>
#include<cmath>
using namespace std;
unsigned int Rand()
{
    static unsigned int seed=20160220;
    seed*=0xdefaced,seed+=84033;
    return seed+=seed>>20; 
}
struct Node
{
    Node *ch[2];
    const int val;
    unsigned int sz;
    Node(const int _val):ch{NULL,NULL},val(_val),sz(1){}
}*S[300000];
unsigned int Sz(Node *o){return o?o->sz:0;}
void Maintain(Node *o){o->sz=Sz(o->ch[0])+1+Sz(o->ch[1]);}
Node *Merge(Node *a,Node *b)
{
    if(!a||!b)return a?a:b;
    if(Rand()%((a->sz)+(b->sz))<(a->sz))
    {
        a->ch[1]=Merge(a->ch[1],b);
        Maintain(a);
        return a;
    }
    else
    {
        b->ch[0]=Merge(a,b->ch[0]);
        Maintain(b);
        return b;
    }
}
void Split(Node *o,Node* &a,Node* &b,const int loc)
{
    if(!o){a=b=NULL;return;}
    if(loc<(o->val))
    {
        b=o;
        Split(b->ch[0],a,b->ch[0],loc);
        Maintain(b);
    }
    else
    {
        a=o;
        Split(a->ch[1],a->ch[1],b,loc);
        Maintain(a);
    }
}
Node *Split(Node* &o,const int l,const int r)
{
    Node *a,*b,*c;
    Split(o,b,c,r);
    Split(b,a,b,l-1);
    o=Merge(a,c);
    return b;
}
bool Contains(Node *o,const int loc)
{
    if(!o)return false;
    if((o->val)==loc)return true;
    if(loc<(o->val))return Contains(o->ch[0],loc);
    else return Contains(o->ch[1],loc);
}
void RemoveTag(Node* &o,int *tag)
{
    if(!o)return;
    assert(tag[o->val]!=-1);
    tag[o->val]=-1;
    for(int d=0;d<2;d++)RemoveTag(o->ch[d],tag);
}
void AddTag(Node* &o,int *tag,const int color)
{
    if(!o)return;
    assert(tag[o->val]==-1);
    tag[o->val]=color;
    for(int d=0;d<2;d++)AddTag(o->ch[d],tag,color);
}
set<int>UNREAD,LARGE;
int TAG[300000];
int N;
unsigned int SQ;
int main()
{
//    freopen("in.txt","r",stdin);
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int querycount;scanf("%d%d",&N,&querycount);
    SQ=sqrt(N)+1;
    UNREAD.clear();
    for(int i=1;i<=N;i++)UNREAD.insert(i),TAG[i]=-1;
    LARGE.clear();
    long long ans=0LL;
    for(int l,r,i=0;i<querycount;i++)
    {
        scanf("%d%d",&l,&r);
        if(UNREAD.find(l)!=UNREAD.end())S[i]=NULL;
        else if(TAG[l]!=-1)
        {
            S[i]=Split(S[TAG[l]],l,r);
            RemoveTag(S[i],TAG);
        }
        else
        {
            bool found=false;
            for(const int v:LARGE)if(Contains(S[v],l))
            {
                S[i]=Split(S[v],l,r);
                if(Sz(S[v])<=SQ)LARGE.erase(v),AddTag(S[v],TAG,v);
                found=true;
                break;
            }
            assert(found);
        }
        auto it=UNREAD.lower_bound(l);
        while(it!=UNREAD.end()&&(*it)<=r)
        {
            Node *a,*b;
            Split(S[i],a,b,*it);
            S[i]=Merge(a,Merge(new Node(*it),b));
            UNREAD.erase(it++);
        }
        ans+=Sz(S[i]);
        if(Sz(S[i])<=SQ)AddTag(S[i],TAG,i);
        else LARGE.insert(i);
    }
    printf("%I64d\n",ans);
    return 0;
}