Description：

带修改区间第 $K$ 大。

$1\le n \le 100000$

Solution：

做法一：树状数组套权值线段树，也就是带修改主席树。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

int a1[300100],s[300100],a2[300100];

int b[700100];

int in[300100][10];

int totn = 0;

int lowbit(int x)

{

    return x & (-x);

}

bool cmp(int k1,int k2)

{

    return b[k1] < b[k2];

};

struct node

{

    int l,r;

    node *ls,*rs;

    int sum;

    node(){l = r = sum = 0;ls = NULL;rs = NULL;}

}t[1500000];

node *ptr = t;

node *c[300100];

node *newnode(){return ++ptr;}

void build(node *(&root))

{

    root = newnode();

    root -> l = 1;

    root -> r = totn;

    return;

}

int search(int k)

{

    int l = 1,r = totn,mid;

    while(l < r)

    {

        mid = (l + r) >> 1;

        if(b[s[mid]] == k)return mid;

        if(b[s[mid]] < k)

        {

            l = mid + 1;

        }

        else

        {

            r = mid - 1;

        }

    }

}

void get(node *p,int c)

{

    if(c == 1 && p -> ls == NULL)

    {

        p -> ls = newnode();

        p -> ls -> l = p -> l;

        p -> ls -> r = (p -> l + p -> r) >> 1;

        return;

    }

    if(c == 2 && p -> rs == NULL)

    {

        p -> rs = newnode();

        p -> rs -> l = ((p -> l + p -> r) >> 1) + 1;

        p -> rs -> r = p -> r;

        return;

    }

    return;

}

void insert(node *root,int x)

{

    int mid;

    while(root -> l != root -> r)

    {

        root -> sum += 1;

        mid = (root -> l + root -> r) >> 1;

        if(x <= mid)

        {

            get(root,1);

            root = root -> ls;

        }

        else

        {

            get(root,2);

            root = root -> rs;

        }

    }

    root -> sum += 1;

    return;

}

void remove(node *root,int x)

{

    int mid;

    while(root -> l != root -> r)

    {

        root -> sum -= 1;

        mid = (root -> l + root -> r) >> 1;

        if(x <= mid)

        {

            root = root -> ls;

        }

        else

        {

            root = root -> rs;

        }

    }

    root -> sum -= 1;

    return;

}

void add(int p,int x)

{

    int k = search(x);

    for(int i = p;i <= n;i += lowbit(i))

    {

        insert(c[i],k);

    }

    return;

}

void dec(int p,int x)

{

    int k = search(x);

    for(int i = p;i <= n;i += lowbit(i))

    {

        remove(c[i],k);

    }

    return;

}

node *d1[30000],*d2[30000];

int t1,t2;

int query(int l,int r,int k)

{

    t1 = t2 = 0;

    for(int i = l - 1;i >= 1;i -= lowbit(i))d1[++t1] = c[i];

    for(int i = r;i >= 1;i -= lowbit(i))d2[++t2] = c[i];

    int k1 = 0,k2 = 0,x;

    int _l = 1,_r = totn;

    while(_l != _r)

    {

        k1 = k2 = 0;

        for(int i = 1;i <= t1;++i){if(d1[i] -> ls == NULL)continue;k1 += d1[i] -> ls -> sum;}

        for(int i = 1;i <= t2;++i){if(d2[i] -> ls == NULL)continue;k2 += d2[i] -> ls -> sum;}

        x = k2 - k1;

        if(k > x)

        {

            k -= x;

            for(int i = 1;i <= t1;++i){get(d1[i],2);d1[i] = d1[i] -> rs;}

            for(int i = 1;i <= t2;++i){get(d2[i],2);d2[i] = d2[i] -> rs;}

            _l = ((_l + _r) >> 1) + 1;

        }

        else

        {

            for(int i = 1;i <= t1;++i){get(d1[i],1);d1[i] = d1[i] -> ls;}

            for(int i = 1;i <= t2;++i){get(d2[i],1);d2[i] = d2[i] -> ls;}

            _r = (_l + _r) >> 1;

        }

    }

    return b[s[_l]];

}

void change(int p,int x)

{

    dec(p,a1[p]);

    a1[p] = x;

    add(p,x);

    return;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = 1;i <= n;++i)

    {

        scanf("%d",&a1[i]);

        b[++totn] = a1[i];

        s[totn] = totn;

    }

    char k1;

    for(int i = 1;i <= m;++i)

    {

        cin >> k1;

        if(k1 == 'Q')

        {

            in[i][0] = 1;

            scanf("%d%d%d",&in[i][1],&in[i][2],&in[i][3]);

        }

        else

        {

            in[i][0] = 0;

            scanf("%d%d",&in[i][1],&in[i][2]);

            b[++totn] = in[i][2];

            s[totn] = totn;

        }

    }

    sort(s + 1,s + 1 + totn,cmp);

    for(int i = 1;i <= totn;++i)a2[s[i]] = i;

    for(int i = 1;i <= n;++i)build(c[i]);

    for(int i = 1;i <= n;++i)add(i,a1[i]);

    for(int i = 1;i <= m;++i)

    {

        if(in[i][0] == 1)

        {

            printf("%d\n",query(in[i][1],in[i][2],in[i][3]));

        }

        else

        {

            change(in[i][1],in[i][2]);

        }

    }

    return 0;

}

做法二：整体二分。

首先把最开始的数列变成单点赋值的操作，询问操作不变，单点修改操作变为一个单点清空，一个单点赋值，然后把整个操作序列和值域丢进去整体二分。

依次遍历所有操作，如果是修改操作，那么如果修改后的值小于等于 $mid$ ，就在树状数组中把他加进去并丢到左区间，否则什么都不做并丢到右区间，如果是询问操作，那么就在树状数组中查询区间 $[l,r]$ ，因为只把小于等于 $mid$ 的数插进去，所以查询出来的结果只是这些区间中小于等于 $mid$ 的数的个数，如果小于等于 $mid$ ，就把它丢到左区间，否则 $-res$ ，并丢到右区间，这样每个值域保存的就是在值域内的操作和询问。

简单来说整体二分就是对于一些二分 $check$ 复杂度太高，如果每个询问都二分会超时，而很多 $check$ 的预处理有很多公共部分，所以把这些询问的 $check$ 放到一起。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

inline char getc()

{

	register char c = getchar();

	while(c != 'Q' && c != 'C')c = getchar();

	return c;

}

int n,m;

#define MAXN 100010

int a[MAXN];

int num[MAXN << 1],cur = 0;

int to[MAXN << 1],cnt = 0;

map<int,int> fr;

int ans[MAXN];

struct option

{

	int type,x,y,k,id;

}q[MAXN * 3],q1[MAXN * 3],q2[MAXN * 3];

int tot = 0;

int c[MAXN << 1];

inline int lowbit(int x){return x & (-x);}

inline void add(int p,int k){for(register int i = p;i <= cnt;i += lowbit(i))c[i] += k;return;}

inline int query(int p){int res = 0;for(register int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

void solve(int l,int r,int L,int R)

{

	if(L == R)

	{

		for(register int i = l;i <= r;++i)if(q[i].id)ans[q[i].id] = L;

		return;

	}

	register int mid = ((L + R) >> 1);

	register int l1 = 0,l2 = 0;

	for(register int i = l;i <= r;++i)

	{

		if(q[i].type)

		{

			if(fr[q[i].y] <= mid)add(q[i].x,q[i].k),q1[++l1] = q[i];

			else q2[++l2] = q[i];

		}

		else

		{

			register int res = query(q[i].y) - query(q[i].x - 1);

			if(q[i].k <= res)q1[++l1] = q[i];

			else q[i].k -= res,q2[++l2] = q[i];

		}

	}

	for(register int i = 1;i <= l1;++i)if(!q1[i].id)add(q1[i].x,-q1[i].k);

	for(register int i = 1;i <= l1;++i)q[l + i - 1] = q1[i];

	for(register int i = 1;i <= l2;++i)q[l + l1 - 1 + i] = q2[i];

	solve(l,l + l1 - 1,L,mid);solve(l + l1,r,mid + 1,R);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(register int i = 1;i <= n;++i)

	{

		a[i] = read();

		q[++tot].x = i;q[tot].y = a[i];q[tot].type = 1;q[tot].k = 1;

		num[++cur] = a[i];

	}

	register char c;

	register int x,y;

	for(register int i = 1;i <= m;++i)

	{

		c = getc();

		if(c == 'Q')

		{

			++tot;

			q[tot].x = read();q[tot].y = read();q[tot].k = read();

			q[tot].id = i;q[tot].type = 0;

		}

		else

		{

			x = read();y = read();

			q[++tot].type = 1;q[tot].k = -1;q[tot].x = x;q[tot].y = a[x];

			q[++tot].type = 1;q[tot].k = 1;q[tot].x = x;q[tot].y = y;

			a[x] = y;

			num[++cur] = y;

		}

	}

	sort(num + 1,num + 1 + cur);

	for(register int i = 1;i <= cur;++i)

	{

		if(i == 1 || num[i] != num[i - 1])

		{

			to[++cnt] = num[i];

			fr[num[i]] = cnt;

		}

	}

	solve(1,tot,1,cnt);

	for(register int i = 1;i <= m;++i)

	{

		if(ans[i])printf("%d\n",to[ans[i]]);

	}

	return 0;

}