标题效果：给定一个序列，单点变化，询价区间k大。
思维：假设没有变化。然后划分树就可以解决，但树的分工仍然是一棵树，它不支持的变化。
主席舒变化实际上是在外带fenwick右护套层值段树，但正确的值线段树必须动态开节点。然后改动的时候就像树状数组改动那样，每次改动logn个权值线段树。
查询的时候也一样。返回logn个权值线段树统计的和。
最后为了求区间第k大，还须要二分答案。
CODE：
#include#include #include #include #define MAX 10010#define MAX_RANGE 1000000000using namespace std;struct Complex{ Complex *son[2]; int num; Complex() { son[0] = son[1] = NULL; num = 0; }}*fenwick[MAX];int cnt,asks;int src[MAX];char c[10];inline void Fix(int x,int c);inline void _Fix(int x,int c);inline int GetSum(int x,int k);void Insert(Complex *&a,int l,int r,int x);void Delete(Complex *&a,int l,int r,int x);int Ask(Complex *a,int l,int r,int k);int Ask(int x,int y,int k);int main(){ cin >> cnt >> asks; for(int i = 1;i <= cnt; ++i) { scanf("%d",&src[i]); Fix(i,src[i]); } for(int x,y,z,i = 1;i <= asks; ++i) { scanf("%s",c); if(c[0] == 'Q') { scanf("%d%d%d",&x,&y,&z); printf("%d\n",Ask(x,y,z)); } else { scanf("%d%d",&x,&y); _Fix(x,src[x]); Fix(x,src[x] = y); } } return 0;}inline void Fix(int x,int c){ for(;x <= cnt;x += x&-x) Insert(fenwick[x],0,MAX_RANGE,c);}inline void _Fix(int x,int c){ for(;x <= cnt;x += x&-x) Delete(fenwick[x],0,MAX_RANGE,c);}inline int GetSum(int x,int k){ int re = 0; for(;x;x -= x&-x) re += Ask(fenwick[x],0,MAX_RANGE,k); return re;}int Ask(int x,int y,int k){ int l = 0,r = MAX_RANGE,ans = 0; while(l <= r) { int mid = (l + r) >> 1; int temp = GetSum(y,mid) - GetSum(x - 1,mid); if(temp >= k) r = mid - 1,ans = mid; else l = mid + 1; } return ans;}void Insert(Complex *&a,int l,int r,int x){ if(a == NULL) a = new Complex(); a->num++; if(l == r) return ; int mid = (l + r) >> 1; if(x <= mid) Insert(a->son[0],l,mid,x); else Insert(a->son[1],mid + 1,r,x);}void Delete(Complex *&a,int l,int r,int x){ if(!--a->num) { free(a); a = NULL; return ; } if(l == r) return ; int mid = (l + r) >> 1; if(x <= mid) Delete(a->son[0],l,mid,x); else Delete(a->son[1],mid + 1,r,x);}int Ask(Complex *a,int l,int r,int k){ if(a == NULL) return 0; if(l == r) return a->num; int mid = (l + r) >> 1; if(k <= mid) return Ask(a->son[0],l,mid,k); else { int left = a->son[0] == NULL ? 0:a->son[0]->num; return left + Ask(a->son[1],mid + 1,r,k); }}
版权声明：本文博客原创文章，博客，未经同意，不得转载。