洛谷3834 主席树模板，动态查询区间第k小

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef unsigned int ui;
 4 typedef long long ll;
 5 typedef unsigned long long ull;
 6 #define pf printf
 7 #define mem(a,b) memset(a,b,sizeof(a))
 8 #define prime1 1e9+7
 9 #define prime2 1e9+9
10 #define pi 3.14159265
11 #define lson l,mid,rt<<1
12 #define rson mid+1,r,rt<<1|1
13 #define scand(x) scanf("%llf",&x) 
14 #define f(i,a,b) for(int i=a;i<=b;i++)
15 #define scan(a) scanf("%d",&a)
16 #define mp(a,b) make_pair((a),(b))
17 #define P pair<int,int>
18 #define dbg(args) cout<<#args<<":"<<args<<endl;
19 #define inf 0x3f3f3f3f
20 const int maxn=2e5+10;
21 int n,m;
22 int a[maxn];
23 vector<int>v;//离散化之后将内容存储在vector中 
24 int getid(int x)
25 {
26     return lower_bound(v.begin(),v.end(),x)-v.begin()+1;//下标是从1开始直到n结束 
27 }
28 struct node{
29     int l,r,sum;
30     //分别保存左右子树的根节点的编号以及当前结点的数值，
31     //在还没插入点信息的时候子树中每个结点的值都是0，所以主席树不需要建树，是边插入边建树的 
32 }t[maxn*40]; //适应O(nlogn)空间需求，2^40次方大小的数据是不可能的，所以可以根据习惯进行选择 
33 int cnt=0,root[maxn];
34 //权值线段树中插入的值p就是插到位置p ,由于当前结点是需要变化的，所以传入引用使他指向内存池中新的结点 
35 void insert(int l, int r,int pre,int& now,int p)//参数中有前面一棵树的结点以及当前树的结点， 
36 {
37     t[++cnt]=t[pre];//从内存池中生成一个根结点并将前面树的根节点复制到其中， 
38     now=cnt; //使当前结点指向新生成的根结点， 
39     t[now].sum++;
40     //要在第p位上插入，所以当前访问的结点是一定是增1的，
41     //后面我们将会决定访问左子树的结点还是右子树的结点 
42     if(l==r)return;//到达了点信息而且前面已经在叶子结点上面更新过点信息，所以直接return 
43     int m=l+r>>1;
44     //如果左子树的区间包括了p点就向左子树递归，否则走右子树，同时也要分别移动到左子树和右子树 
45     if(p<=m)insert(l,m,t[pre].l,t[now].l,p);
46     else insert(m+1,r,t[pre].r,t[now].r,p);
47 }
48 int query(int l,int r,int L,int R,int k)//两个结点同步相减 
49 {
50     if(l==r)return l;//返回的是点信息，就是离散化之后的坐标，便于之后通过vector进行索引 
51     int m=l+r>>1;
52     int tmp=t[t[R].l].sum-t[t[L].l].sum;//先获取两棵树左子树的键值之差决定向哪一棵数递归 
53     if(k<=tmp)return query(l,m,t[L].l,t[R].l,k);
54     else return query(m+1,r,t[L].r,t[R].r,k-tmp);//如果tmp<k,就查询右子树中的第k-tmp小的数，有点分治的意味 
55 }
56 int main()
57 {
58     //freopen("input.txt","r",stdin);
59     //freopen("output.txt","w",stdout);
60     std::ios::sync_with_stdio(false);
61     scan(n);
62     scan(m);
63     f(i,1,n)
64     {
65         scan(a[i]);
66         v.push_back(a[i]); 
67     }
68     sort(v.begin(),v.end());
69     //将数列先排序再去重放入vector中以便通过位置获取在线段树中代表的区间点信息 
70     v.erase(unique(v.begin(),v.end()),v.end());
71     //unique函数将不重复元素放到vector的前部，
72     //返回的时所有不重复元素的下一个位置，所以将后面的元素删去就可以离散的成为线段树的坐标点信息 
73     f(i,1,n)
74     {
75         insert(1,n,root[i-1],root[i],getid(a[i]));//在第i-1棵树上建第i棵树，所以传入的是两棵树的根节点 
76     }
77     int l,r,k;
78     while(m--)
79     {
80         scanf("%d%d%d",&l,&r,&k);
81         pf("%d\n",v[query(1,n,root[l-1],root[r],k)-1]);
82         //查询[l,r]区间更新的信息，实现动态查询第k小，
83         //注意vector中下标是从0开始的，而线段树中下标是从1开始的，所以错位了1，为了达到原来的元素就要减一 
84     }
85  }