[HDU 5412][ZOJ 2112][整體二分] CRB and Queries

原題連結
yee~想看對於區間第k小問題討論的同學可以戳這邊。

整體二分在幾種解法當中是思維算相當簡單，但是coding難度是其中最低的。
如果不懂整體二分的童鞋可以先做這題。

討論與上面那題相當類似，我還是稍微花些篇幅講一下。

先理解一個樸素的作法：

先將所有操作存起來。對於每一個詢問，我們可以二分搜答案，判斷方法如下：(假設詢問區間[L,R]的第k小,目前二分搜區間[vL,vR])

對於現在二分搜的值vM=(vL+vR)/2，我們將所有以前的操作做一遍，最後統計在區間[L,R]中有幾個<=vM的數字(以上都可以用BIT或線段樹完成)，如果數量<=k，那麼答案會在[vL,vM]之中，否則答案會在[vM+1,vR]之中。

回答一個詢問的時間是O((N+Q)logc)
這樣我們有了一個時間複雜度O(Q(N+Q)logc)的作法(c是值域)

接下來要做的事情就很顯然了，套用整體二分的框架讓大家一起二分搜，實做方式也極度類似上面那一題。

比較難想的地方應該是要將「修改操作」轉化成「每個數字的存活時間」的概念，然後依照時間這個序去做上面那個判斷方法。(好難解釋orz，請參悟一下吧)

#include<cstring>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=100000+5;
const int maxQ=100000+5;
struct Query
{
    int L,R,k,qt,id;
    Query(int a,int b,int c,int d,int e):L(a),R(b),k(c),qt(d),id(e) {}
    bool operator < (const Query& rhs) const {return qt<rhs.qt;}
};
struct Event
{
    int p,x,flag,et;
    Event(int a,int b,int c,int d):p(a),x(b),flag(c),et(d) {}
    bool operator < (const Event& rhs) const {return et<rhs.et;}
};
inline int lowbit(int x) {return x&(-x);}
vector<int> disc;
int N,Q,c[maxn];
void add(int p,int x)
{
    while(p<=N)
    {
        c[p]+=x;
        p+=lowbit(p);
    }
}
int query(int p)
{
    int ret=0;
    while(p)
    {
        ret+=c[p];
        p-=lowbit(p);
    }
    return ret;
}
void operate_split(int M,vector<Event>& eve,vector<Query>& qu,vector<Event>& Leve,vector<Event>& Reve,vector<Query>& Lqu,vector<Query>& Rqu)
{
    for(int i=0;i<eve.size();i++)
    {
        if(eve[i].x<=M) Leve.push_back(eve[i]);
        else Reve.push_back(eve[i]);
    }
    vector<Event> ().swap(eve);
    
    int ep=-1,qp=0;
    for(qp=0;qp<qu.size();qp++)
    {
        while(ep+1<Leve.size() && Leve[ep+1].et<=qu[qp].qt)
        {
            add(Leve[ep+1].p,Leve[ep+1].flag);
            ep++;
        }
        int cnt=query(qu[qp].R)-query(qu[qp].L-1);
        if(qu[qp].k<=cnt) {Lqu.push_back(qu[qp]);}
        else {qu[qp].k-=cnt;Rqu.push_back(qu[qp]);}
    }
    vector<Query> ().swap(qu);
    while(ep>=0) {add(Leve[ep].p,-Leve[ep].flag);ep--;}
    
}
int ans[maxQ];
void totBS(int L,int R,vector<Event>& eve,vector<Query>& qu)
{
    if(L==R)
    {
        for(int i=0;i<qu.size();i++) ans[qu[i].id]=L;
        return;
    }
    int M=L+(R-L)/2;

    vector<Event> Leve,Reve;
    vector<Query> Lqu,Rqu;

    operate_split(M,eve,qu,Leve,Reve,Lqu,Rqu);
    totBS(L,M,Leve,Lqu);
    totBS(M+1,R,Reve,Rqu);

}
int a[maxn];
vector<Query> qu;
vector<Event> eve;
int main()
{
    while(scanf("%d",&N)==1)
    {
        qu.clear();eve.clear();
        for(int i=1;i<=N;i++) {scanf("%d",a+i);eve.push_back(Event(i,a[i],1,0));disc.push_back(a[i]);}
        scanf("%d",&Q);
        for(int i=0,type,L,R,k;i<Q;i++)
        {
            scanf("%d",&type);
            if(type==1)
            {
                scanf("%d%d",&L,&k);
                eve.push_back(Event(L,a[L],-1,i));
                eve.push_back(Event(L,k,1,i));
                a[L]=k;
                disc.push_back(k);
            }
            else
            {
                scanf("%d%d%d",&L,&R,&k);
                qu.push_back(Query(L,R,k,i,(int)qu.size()));
            }
        }
        sort(disc.begin(),disc.end());
        disc.resize(unique(disc.begin(),disc.end())-disc.begin());
         
        sort(eve.begin(),eve.end());
        sort(qu.begin(),qu.end());
        for(int i=0;i<eve.size();i++) eve[i].x=lower_bound(disc.begin(),disc.end(),eve[i].x)-disc.begin();
        
        memset(ans,-1,sizeof ans);
        totBS(0,disc.size()-1,eve,qu);
        for(int i=0;ans[i]!=-1;i++) printf("%d\n",disc[ans[i]]);
    }
}