hdu5412--CRB and Queries（整體二分）

hdu5412--CRB and Queries（整體二分）

題目大意：給出n個數的初始序列，有兩種操作，1 l v將第l個數換成v，2 l r k 問在區間[l,r]內的第k大是多少，並輸出

經典的題目，但是樹狀數組+主席樹（TLE）伸展樹（MLE），聽說他們用的塊狀鏈表，zhazha表示不會，後來補題，發現整體二分是一個好方法。

首先，這個整體二分是將數據范圍和操作放到一起，不斷二分數據的范圍，可以得到有某些操作可以被完成，有某些操作不可以被完成。

例如：當前數據范圍的區間是[l,r]，那麼mid = (l+r)/2 ，所有修改操作如果修改的數小於等於mid，那麼就是可以被完成的，那麼就修改數，否則就是不能被完成的。對於查詢操作，如果查詢到的范圍內的數的個數x小於k，那麼要查詢的數是不在區間[1,5]內的，所以這個操作是不會再[l,mid]中被完成，將該操作的k改為k-x。否則就會在[l,mid]內被完成。按照數據范圍向下二分得到[l,mid],[mid+1,r]，將能被完成的操作放入左區間，不能完成的操作放入右區間。（注意放到同一區間的的操作的相對順序是不能被改變的），這樣最終的查詢操作都會被確定到一個數值，這個數值就是要輸出的值。

#include 
#include 
#include 
using namespace std ;
#define maxn 300100
struct node{
    int type, l, r, v , ans;
}p[maxn];
int c[maxn], n, q, cnt, max1;
int a[maxn];
int id1[maxn], id2[maxn];
void p_add(int type, int l,int r, int v) {
    p[cnt].type = type;
    p[cnt].l = l; p[cnt].r = r;
    p[cnt].v = v;
    id1[cnt] = cnt;
    cnt++;
}
int lowbit(int x) {
    return x & -x ;
}
void add(int i,int k) {
    while( i <= n ) {
        c[i] += k ;
        i += lowbit(i) ;
    }
}
int sum(int i) {
    int num = 0 ;
    while( i ) {
        num += c[i] ;
        i -= lowbit(i) ;
    }
    return num ;
}
void solve(int L, int R, int low, int high) {
    if( L > R ) return;
    if( low == high ) {
        while(L <= R) {
            if( p[ id1[L] ].type == 2 ) p[ id1[L] ].ans = low;
            L++;
        }
        return ;
    }
    int i, j, num, l = L, r = R;
    int mid = (low + high)/2;
    for(i = L; i <= R; i++) {
        j = id1[i];
        if( p[j].type == 2 ) {
            num = sum(p[j].r) - sum(p[j].l-1);
            if( num < p[j].v ) {
                p[j].v -= num;
                id2[r--] = j;
            }
            else
                id2[l++] = j;
        }
        else {
            if( p[j].v <= mid ) {
                add(p[j].l,p[j].type);
                id2[l++] = j;
            }
            else
                id2[r--] = j;
        }
    }
    for(i = L; i <= R; i++) {
        j = id1[i];
        if( p[j].type != 2 && p[j].v <= mid ) add(p[j].l,-p[j].type);
    }
    for(i = L; i < l; i++)
        id1[i] = id2[i];
    for(r = R; i <= R; r--, i++)
        id1[i] = id2[r];
    solve(L,l-1,low,mid);
    solve(l,R,mid+1,high);
}
int main() {
    int i, j, type, l, r, v;
    while( scanf(%d, &n) != EOF ) {
        memset(c,0,sizeof(c));
        cnt = max1 = 0;
        for(i = 1; i <= n; i++) {
            scanf(%d, &a[i]);
            p_add(1, i, i, a[i]);
            max1 = max(max1, a[i]);
        }
        scanf(%d, &q);
        while( q-- ) {
            scanf(%d, &type);
            if( type == 1 ) {
                scanf(%d %d, &l, &v);
                p_add(-1, l, l, a[l]);
                a[l] = v;
                p_add(1, l, l, a[l]);
                max1 = max(max1, a[l]);
            }
            else {
                scanf(%d %d %d, &l, &r, &v);
                p_add(2, l, r, v);
            }
        }
        solve(0,cnt-1,0,max1) ;
        for(i = 0; i < cnt; i++) {
            if( p[i].type == 2 )
                printf(%d
, p[i].ans);
        }
    }
    return 0 ;
}