\(\;\)
给定一个含有\(n\)个数的序列\(a_1,a_2,\cdots,a_n\)，需要支持两种操作
1.\(\;Q\;l\;r\;k\)：表示查询下标在区间\([l,r]\)中第\(k\)小的数
2.\(\;C\;x\;y\)：表示将\(a_x\)改为\(y\)
\(n,m\leq 10^5,a_i\leq 10^9\)
题目地址： https://www.luogu.com.cn/problem/P2617
\(\;\)
与上道题相比只多了修改操作(废话)
\(\;\)
树状数组维护
\(\;\)
我们考虑把\(a_x\)改为\(y\)的影响，设\(a_x\)原先等于\(v\)，显然，第\(x\)到\(n\)个版本的线段树下标为\(y\)的值要\(+1\)，为\(v\)的要\(-1\)
如果只是单纯的\(for(x\;to\;n)\)，然后对这些线段树进行修改的话，很明显：每次修改的复杂度是\(O(n\;log\;n)\)，而\(m\)次操作，时间复杂度为\(O(nm\times log\;n)\)，显然不行。
所以我们考虑如何优化这个东西。
与上题相同我们想要知道的是\(sum[r]-sum[l-1]\)这样的区间和。
如果仔细观察你就可以发现，这个东西可以用树状数组的思路来做。
在这里：以\(root[x]\)为根的线段树存储的不再是\([1,x]\)的信息了，而是\([x-lowbit(x)+1,x]\)中的信息。
而根据树状数组的套路，每次修改会对\(log(n)\)个点产生影响，查询也是同理。
通俗点说：就是把每颗线段树当做一个点，这样就形成了一个长度为\(n\)的序列，然后再用树状数组维护这个序列的修改查询操作。（外层是树状数组，内层是线段树）
而每次至多修改\(log(n)\)个点(线段树)，每个线段树修改的复杂度为\(log(n)\)。
由此可得，时间复杂度：\(O(m\times log_2 n)\)。
而空间复杂度？由于每次修改都至多新建\(log_2 n\)个点，所以为\(O((n+m)\times log_2 n)\)
剩下的东西就和Problem 1完全一样了。
\(\;\)
code
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, q, a[N], len, ask_x[N], ask_y[N], ask_k[N], tmp1[100], tmp2[100];
int root[N << 1], idx, cnt1, cnt2, g[N << 1];
struct Node
{
int l, r, cnt;
}tree[N * 400]; //注意要开到O((n+m) log2 n)的大小
int lowbit(int x)
{
return x&-x;
}
int Getit(int x)
{
return lower_bound(g + 1, g + len + 1, x) - g;
}
int Update(int Last,int l,int r,int x,int v)
{
//函数的意义：对线段树中下标为x的值加上v
int Now = ++idx; tree[Now] = tree[Last];
if(l == r)
{
tree[Now].cnt += v;
return Now;
}
int mid = (l + r) >> 1;
if(x <= mid)
{
tree[Now].l = Update(tree[Now].l, l, mid, x, v);
}
else tree[Now].r = Update(tree[Now].r, mid + 1, r, x, v);
tree[Now].cnt = tree[tree[Now].l].cnt + tree[tree[Now].r].cnt;
return Now;
}
inline void Add(int x,int val,int v)
{
for(;x <= n; x += lowbit(x))
{
root[x] = Update(root[x], 1, len, val, v);
//修改时，所有被它影响的线段树中下标为x的值都要加上v
}
}
int Query(int l,int r,int k)
{
if(l == r)
{
return l;
}
int mid = (l + r) >> 1, sum = 0;
for(register int i=1;i<=cnt1;i++)
{
sum -= tree[tree[tmp1[i]].l].cnt;
}
for(register int i=1;i<=cnt2;i++)
{
sum += tree[tree[tmp2[i]].l].cnt;
}
//sum就是维护一个前缀和，只不过使用树状数组算的
if(sum >= k)
{
for(register int i=1;i<=cnt1;i++)
{
tmp1[i] = tree[tmp1[i]].l;
}
for(register int i=1;i<=cnt2;i++)
{
tmp2[i] = tree[tmp2[i]].l;
}
return Query(l, mid, k);
}
else
{
//跟着向下遍历
for(register int i=1;i<=cnt1;i++)
{
tmp1[i] = tree[tmp1[i]].r;
}
for(register int i=1;i<=cnt2;i++)
{
tmp2[i] = tree[tmp2[i]].r;
}
return Query(mid + 1, r, k - sum);
}
}
int main()
{
scanf("%d%d",&n,&q);
for(register int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
g[ ++ len] = a[i];
}
char op[2];
for(register int i=1;i<=q;i++)
{
scanf("%s%d%d",op,&ask_x[i],&ask_y[i]);
if(op[0] == 'C')
{
ask_k[i] = 0;
g[ ++ len] = ask_y[i];
}
else
{
scanf("%d",&ask_k[i]);
}
}
sort(g + 1, g + len + 1);
len = unique(g + 1, g + len + 1) - g - 1;
for(register int i=1;i<=n;i++)
{
Add(i, Getit(a[i]), 1); //在i这个版本的线段树上a[i]离散化后的上的值加上1
}
for(register int i=1;i<=q;i++)
{
if(ask_k[i] == 0)
{
Add(ask_x[i], Getit(a[ask_x[i]]), -1);
a[ask_x[i]] = ask_y[i];
Add(ask_x[i], Getit(a[ask_x[i]]), 1);
}
else
{
cnt1 = 0, cnt2 = 0;
int L = ask_x[i] - 1, R = ask_y[i];
for(;L; L ^= lowbit(L)) //这里预处理出我们要算的是哪些版本的线段树
{
tmp1[ ++ cnt1 ] = root[L];
}
for(;R; R ^= lowbit(R))
{
tmp2[ ++ cnt2 ] = root[R];
}
printf("%d\n",g[Query(1, len, ask_k[i])]); //输出排名为k的值
}
}
return 0;
}
