[HDU 5412]CRB and Queries

經典題型：區間第$k$小帶修改

這種題目經典做法有兩種：
1. $BIT$ ($Binary\ Indexed\ Tree$) 套持久化線段樹 (幾乎每次都MLE的作法)
時間複雜度：$O(\log^{2}N)$修改，$O(\log^{2}N)$查詢
空間複雜度：$O(N\log N+Q\log^{2}N)$
2. 線段樹套名次樹 (請參考這篇)
時間複雜度：$O(\log^{2}N)$修改，$O(\log^{3}N)$查詢
空間複雜度：$O(N)$

這次，我來向大家介紹一種只用到$vector$和$BIT$的作法，神奇吧

說明：
$q_{i}$代表第$i$次修改或詢問
$q_{i}.l$和$q_{i}.r$代表詢問$q_{i}$的左右邊界
$q_{i}.k$代表詢問$q_{i}$的名次

首先，不考慮TLE問題的話

我們把原序列的所有數字，以及修改操作的數字，都賦予一個「生命週期」
也就是，這個數字在第幾次到第幾次詢問內有效
於是我們把序列和以後修改後的樣貌取代成了$O(N+Q)$個物件，有值、位置、生命週期這幾個屬性
再提醒一次，序列已經不存在，我們只剩一堆具有生命週期的物件

對每個詢問$q_{i}$，我們可以二分搜值域 (值域大小經離散化後為$O(N+Q)$)
假設我們現在搜到值域$[l,r]$，算出$mid=\frac{l+r}{2}$
然後檢查看看有幾個數字，生命週期涵蓋$q_{i}$、$\leq mid$且位在$[q_{i}.l,q_{i}.r]$內
如果這種數字數量$<q_{i}.k$，代表$q_{i}$的答案$>mid$
否則，代表$q_{i}$的答案$\leq mid$

直接做的話時間複雜度是$O(Q(N+Q)\log(N+Q))$

信不信，我們可以把那個$Q(N+Q)$合併成$N+Q\log N$！

方法是全部的$q_{i}$一起二分搜
假設我們現在搜到值域$[l,r]$，算出$mid=\frac{l+r}{2}$
現在，只把值$\leq mid$的數字拿出來
然後隨著時間推進，在這些$\leq mid$的數字中，有些數字會出現，有些數字會消失
我們可以用線段樹來維護目前數字的分布狀況，或者像我簡單一點，用$BIT$
當時間到達$q_{i}$的位置的時候，我們可以立即從線段樹中$O(\log N)$得出$[q_{i}.l,q_{i}.r]$內有幾個數字$\leq mid$
如果數字數量$<q_{i}.k$，代表$q_{i}$的答案$>mid$
否則，代表$q_{i}$的答案$\leq mid$

把所有答案$>mid$的$q_{i}$，$q_{i}.k$減掉剛剛找出的數字數量後 (想一想，為甚麼XD)，丟到區間$[mid+1,r]$遞迴繼續二分搜
把所有答案$\leq mid$的$q_{i}$丟到區間$[l,mid]$遞迴繼續二分搜

這就是整體二分的概念

時間複雜度：$O((N+Q\log N)\log(N+Q))$

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
struct QueryType
{
    int l,r,k,id,win;
};
vector<QueryType>QUERY;
struct Event
{
    int val,loc,moment,cnt;
    Event(const int _val,const int _loc,const int _moment,const int _cnt):val(_val),loc(_loc),moment(_moment),cnt(_cnt){}
    bool operator<(const Event &e)const{return moment<e.moment;}
};
vector<Event>EVENT;
struct Bit
{
    int data[100001],n;
    void Clear(const int _n){n=_n;for(int i=1;i<=n;i++)data[i]=0;}
    void Add(int i,const int val){while(i<=n)data[i]+=val,i+=(i&(-i));}
    int Query(int i){int ans=0;while(i)ans+=data[i],i-=(i&(-i));return ans;}
}BIT;
int ANS[100000];
void Solve(const int l,const int r,const vector<int>&events,const vector<int>&queries)
{
    if(l==r)
    {
        for(const int i:queries)ANS[i]=r;
        return;
    }
    const int mid=(l+r)/2;
    vector<int>left_events,right_events;
    for(const int i:events)(EVENT[i].val<=mid?left_events:right_events).push_back(i);
    static int change_query[100000];
    vector<int>::const_iterator ei=left_events.begin();
    for(vector<int>::const_iterator qi=queries.begin();qi!=queries.end();qi++)
    {
        for(;ei!=left_events.end()&&EVENT[*ei].moment<=(*qi);ei++)
        {
            const Event &e=EVENT[*ei];
            BIT.Add(e.loc,e.cnt);
        }
        QueryType &q=QUERY[*qi];
        change_query[*qi]=BIT.Query(q.r)-BIT.Query(q.l-1);
        q.win+=change_query[*qi];
    }
    while(ei!=left_events.begin())
    {
        const Event &e=EVENT[*--ei];
        BIT.Add(e.loc,-e.cnt);
    }
    vector<int>left_queries,right_queries;
    for(const int i:queries)
    {
        QueryType &q=QUERY[i];
        if(q.win<q.k)right_queries.push_back(i);
        else
        {
            q.win-=change_query[i];
            left_queries.push_back(i);
        }
    }
    Solve(l,mid,left_events,left_queries);
    Solve(mid+1,r,right_events,right_queries);
    vector<int>().swap(left_events);
    vector<int>().swap(left_queries);
    vector<int>().swap(right_events);
    vector<int>().swap(right_queries);
}
vector<int>RANGE;
int N,M,S[100001];
void Discretize()
{
    vector<int>&v=RANGE;v.clear();
    for(int i=1;i<=N;i++)v.push_back(S[i]);
    for(const QueryType &q:QUERY)if(q.l==-1)v.push_back(q.k);
    sort(v.begin(),v.end()),v.resize(M=unique(v.begin(),v.end())-v.begin());
    for(int i=1;i<=N;i++)S[i]=lower_bound(v.begin(),v.end(),S[i])-v.begin();
    for(QueryType &q:QUERY)if(q.l==-1)q.k=lower_bound(v.begin(),v.end(),q.k)-v.begin();
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&N)==1)
    {
        for(int i=1;i<=N;i++)scanf("%d",&S[i]);
        int querycount;scanf("%d",&querycount);
        QUERY.clear();
        for(int i=0,type;i<querycount;i++)
        {
            static QueryType q;
            q.id=i,q.win=0;
            scanf("%d",&type);
            if(type==1)q.l=-1,scanf("%d%d",&q.r,&q.k);
            else if(type==2)scanf("%d%d%d",&q.l,&q.r,&q.k);
            else assert(0);
            QUERY.push_back(q);
        }
        Discretize();
        if(true)
        {
            static vector<pair<int,int> >life[100001];
            for(int i=1;i<=N;i++)life[i].clear(),life[i].push_back(make_pair(S[i],0));
            for(const QueryType &q:QUERY)if(q.l==-1)life[q.r].push_back(make_pair(q.k,q.id));
            for(int i=1;i<=N;i++)life[i].push_back(make_pair(-1,querycount));
            EVENT.clear();
            for(int i=1;i<=N;i++)
            {
                for(int j=0;j+1<(int)life[i].size();j++)
                {
                    const auto &p1=life[i][j],&p2=life[i][j+1];
                    EVENT.push_back(Event(p1.first,i,p1.second,1));
                    EVENT.push_back(Event(p1.first,i,p2.second,-1));
                }
            }
            sort(EVENT.begin(),EVENT.end());
        }
        vector<int>events,queries;
        for(int i=0;i<(int)EVENT.size();i++)events.push_back(i);
        for(int i=0;i<querycount;i++)if(QUERY[i].l!=-1)queries.push_back(i);
        BIT.Clear(N);
        Solve(0,M-1,events,queries);
        for(int i=0;i<querycount;i++)if(QUERY[i].l!=-1)printf("%d\n",RANGE[ANS[i]]);
    }
    return 0;
}