简易版第k大（权值线段树）_权值线段树第k大

武汉加油！中国加油！！！
（希望疫情早点过去，大家平安健康！宅在家里实在太无聊了，好想开学 ）
题目传送门
先简单说一下权值线段树吧（自己见解，不完善的希望大佬指点）

权值线段树

权值线段树最重要还是基于线段数的结构形式，在线段树的基础上改变了区间维护信息，权值线段树的每个区间表示更像是一个桶，保存的信息是这个区间的L到R的每个数的出现次数总和，如果L=R，那么就直接表示这个数总共出现了多少次。
看到简单的入门题，应该就可以更好的理解权值线段树的作用了，它可以在允许区间修改的情况下很快的查询区间第K大。
这道题就很好的一道权值线段树的入门题，可以让你很好的理解权值线段树的作用感，本来我感觉权值线段树好像没有什么太大的作用，但是有时候真的给你意想不到的惊喜。
直接上AC代码了解一下权值线段树的这添加和查询两个操作。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int tree[5*N];
int an[300005];
void add(int l,int r,int k,int x,int op)
{
    tree[k]+=op;
    if(l==r)
    {
        return;
    }
    int mid=(l+r)/2;
    if(x<=mid)
    {
        add(l,mid,k*2,x,op);
    }
    else
    {
        add(mid+1,r,k*2+1,x,op);
    }
}
int xth(int l,int r,int k,int x)
{
    if(l==r)
    {
        return l;
    }
    int mid=(l+r)/2;
    if(tree[k*2]>=x)
    {
        return xth(l,mid,k*2,x);
    }
    else
    {
        return xth(mid+1,r,k*2+1,x-tree[k*2]);
    }
}
int main()
{
    int  n,p;
    scanf("%d%d",&n,&p);
    int v;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&an[i]);
        add(1,1e6,1,an[i],1);
    }
    while(p--)
    {
        int o,x,y;
        scanf("%d",&o);
        if(o==1)
        {
            scanf("%d",&x);
            printf("%d\n",xth(1,1e6,1,x));
        }
        else
        {
            scanf("%d%d",&x,&y);
            add(1,1e6,1,an[x],-1);
            an[x]=y;
            add(1,1e6,1,an[x],1);
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71