标题效果：给定一个序列，单点变化，询价区间k大。
思维：假设没有变化。然后划分树就可以解决，但树的分工仍然是一棵树，它不支持的变化。
主席舒变化实际上是在外带fenwick右护套层值段树，但正确的值线段树必须动态开节点。然后改动的时候就像树状数组改动那样，每次改动logn个权值线段树。
查询的时候也一样。返回logn个权值线段树统计的和。
最后为了求区间第k大，还须要二分答案。
CODE：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 10010
#define MAX_RANGE 1000000000
using 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);
}
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。