題目大意:給出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 ; }