[HDU 5412] CRB and Queries （整體二分）

HDU - 5412

動态區間第 K小

很經典的題，可以用線段樹套平衡樹線上解決

但是這題貌似卡樹套樹，況且我也不會手寫平衡樹

可以使用“整體二分”的分治思想解決

将每個資料處理成 (x,y,v) 的三元組

其中 x 為這個數的下标，y為大小， v 為 1時表示添加，-1表示删除

開始時讀入 N個資料，進行 N 次添加操作

修改操作視作删除這個數，然後在原位置再添加一個數這樣兩個操作

對于每個詢問，處理成 (l,r,k)的三元組

l 表示詢問左端點，r為右端點， k 為k小

然後把詢問和資料按照出現的時間順序放在一起，

這樣這些三元組就對時間天然有序

然後進行整體二分，二分答案為 mid ，

在每層遞歸中，按時間順序處理三元組

1. 如果目前處理一個資料，并且這個數大小 <=mid，

   就把它的影響用資料結構來維護一下 （樹狀數組）

   如果 <=mid，就放到左邊，反之放到右邊

2. 如果目前處理一個詢問，那麼從資料結構中就能知道，

   [l,r] 區間中 <=mid的數有多少個

   1. 如果個數 >=mid，說明目前二分的這個mid太大了

      那麼就把這個三元組放到左邊，和哪些<=mid的資料在一起

   2. 如果個數 < mid，說明目前二分的這個mid太小了

      那麼就将其放到右邊，和那些 >mid的資料放在一起

      并且 k要減去目前個數（扣去左區間的影響）

這樣将詢問和資料放在一起，對資料進行了一個歸并排序

最後資料将會是有序的，但與此同時，詢問也跟着資料進行了排序

詢問與答案資料的距離會随着遞歸層數的增加越來越小，直到得出答案，遞歸結束

#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef pair<int,int> Pii;
typedef long long LL;
typedef unsigned long long ULL;
typedef double DBL;
typedef long double LDBL;
#define MST(a,b) memset(a,b,sizeof(a))
#define CLR(a) MST(a,0)
#define Sqr(a) ((a)*(a))

const int maxn=+;
struct Discrete
{
    int d[*maxn], siz;
    void init()
    {
        sort(d, d+siz);
        siz = unique(d, d+siz) - d;
    }
    void add(int _n){ d[siz++]=_n;}
    int id(int _n){ return lower_bound(d, d+siz, _n)-d+;}
};
struct data
{
    int opt, l, r, v;
    data(){};
    data(int a,int b,int c,int d){opt=a; l=b; r=c; v=d;}
    void pri()
    {
        printf("o:%d l:%d r:%d v:%d\n", opt, l, r, v);
    }
};
struct BIT
{
    int bit[maxn], siz;
    void init(int _n){ siz=_n; CLR(bit);}
    void add(int p, int x){ for(int i=p; i<=siz; i+=i&-i) bit[i]+=x;}
    int sum(int p){ int res=; for(int i=p; i>; i-=i&-i) res+=bit[i]; return res;}
};
int N,Q;
int inpt[maxn];
data list[*maxn], teml[*maxn], temr[*maxn];
Discrete D;
BIT bit;
int ans[maxn];

void solve(int,int,int,int);

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
    #endif

    while(~scanf("%d", &N))
    {
        D.siz=;
        int ap=, list_siz=;
        for(int i=; i<=N; i++)
        {
            scanf("%d", &inpt[i]);
            D.add(inpt[i]);
            list[list_siz++] = data(,i,inpt[i],);
        }
        scanf("%d", &Q);
        for(int i=; i<=Q; i++)
        {
            int opt, l, r, k;
            scanf("%d", &opt);
            if(opt==)
            {
                scanf("%d%d", &l, &k);
                D.add(k);
                list[list_siz++] = data(,l,inpt[l],-);
                list[list_siz++] = data(,l,k,);
                inpt[l]=k;
            }
            else
            {
                scanf("%d%d%d", &l, &r, &k);
                list[list_siz++] = data(++ap,l,r,k);
            }
        }

        D.init();
        bit.init(N);
        for(int i=; i<list_siz; i++) if(!list[i].opt) list[i].r = D.id(list[i].r);
        solve(,list_siz,,D.siz);

        for(int i=; i<=ap; i++) printf("%d\n", ans[i]);
    }
    return ;
}

void solve(int ql, int qr, int nl, int nr)
{
//  printf("ql:%d qr:%d nl:%d nr:%d mid:%d\n", ql, qr, nl, nr, (nl+nr)>>1);
//  for(int i=ql; i<qr; i++) list[i].pri();
    if(nl==nr)
    {
        for(int i=ql; i<qr; i++) if(list[i].opt)
        {
            ans[list[i].opt] = D.d[nl-];
        }
//      puts("--------");
        return;
    }

    int mid=(nl+nr)>>;
    int sizl=, sizr=;
    for(int i=ql; i<qr; i++)
    {
        if(!list[i].opt)
        {
            if(list[i].r <= mid)
            {
                bit.add(list[i].l, list[i].v);
                teml[sizl++] = list[i];
            }
            else temr[sizr++] = list[i];
        }
        else
        {
            int have = bit.sum(list[i].r) - bit.sum(list[i].l-);
//          printf("i:%d have:%d o:%d\n", i, have, list[i].opt);
            if(have >= list[i].v) teml[sizl++] = list[i];
            else
            {
                list[i].v -= have;
                temr[sizr++] = list[i];
            }
        }
    }
    for(int i=; i<sizl; i++) if(!teml[i].opt)
        bit.add(teml[i].l, -teml[i].v);
    for(int i=; i<sizl; i++) list[ql+i]=teml[i];
    for(int i=; i<sizr; i++) list[ql+sizl+i]=temr[i];
//  puts("--------");
    solve(ql, ql+sizl, nl, mid);
    solve(ql+sizl, qr, mid+, nr);
}