程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu5412--CRB and Queries(整體二分)

hdu5412--CRB and Queries(整體二分)

編輯:C++入門知識

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 ;
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved