建设银行园湖路支行网站,网站建设茶店网,有限公司和有限责任公司,wordpress 文章公开编辑静态主席树总结(静态区间的#xff4b;大) 首先我们先来看一道题 给定N个正整数构成的序列#xff0c;将对于指定的闭区间查询其区间内的第K小值。 输入格式#xff1a;
第一行包含两个正整数N、M#xff0c;分别表示序列的长度和查询的个数。
第二行包含N个正整数大) 首先我们先来看一道题 给定N个正整数构成的序列将对于指定的闭区间查询其区间内的第K小值。 输入格式
第一行包含两个正整数N、M分别表示序列的长度和查询的个数。
第二行包含N个正整数表示这个序列各项的数字。
接下来M行每行包含三个整数 l, r, kl,r,k , 表示查询区间[l, r][l,r] 内的第k小值。
输出格式
输出包含k行每行1个正整数依次表示每一次查询的结果 对于100%的数据满足\(1 \leq N, M \leq 2\cdot 10^5\) \(1≤N,M≤2⋅10^5\) 对于数列中的所有数\(a_i\),都有\(-10^9\leq a_i\leq 10^9\) 基本思路 这个题目看上去很像一道线段树或者树状数组之类的裸题但是仔细想想区间第\(k\)小是线段树等数据结构维护不了的这个时候我们就需要引进一种新的数据结构就是可持久化线段树也就是主席树。(可持久化数据结构是可以访问历史版本的这里也可以做到但是这里不需要访问历史版本我们只利用可持久化数据结构的思想) 主席树的本质上是N颗值域线段树(不知道值域线段树的请自行转走)对于每一颗线段树我们都维护从序列开始到这个元素的值域(即第\(i\)颗线段树维护的区间是第一号元素到第\(i\)号元素的值域)。 但实际上我们没有那么多时间和空间去维护\(n\)颗线段树所以我们就要想每一颗线段树由于值域相同它们的形状是完全相同的并且对于一颗第\(i\)颗线段树来说它相对于第\(i-1\)颗线段树只增加了一个值放在值域中也就只有包含这个值的log个节点不同所以对于每一颗线段树我们只需要新开\(log\)个节点,其它的节点就用第\(i-1\)颗线段树的节点(如果你会可持久化数组就会发现这其实跟可持久化数组很像,准确的说可持续化数组的模型就是主席树)。 注意要离散化 实现过程 --- 构建 我们先开一个root数组来保存每一颗线段树的根对于每一个线段树的节点记录它的值左儿子和右儿子的编号在构建第i颗线段树时我们要同时访问第i-1颗线段树每次构建一个节点之后对于不包含这个新增值的儿子我们就直接将第i-1颗线段树的相应的那个儿子作为第i颗线段树的这个儿子。 比如说假设离散化之后的值域是1~5第i号元素是1,我们先构建根节点然后发现这个节点左儿子的值域是1~2,右儿子的值域是3~5右儿子的值域不包括1,所以右儿子就直接用第i-1颗线段树的右儿子而此时我们就新建一个节点作为这个节点的左儿子值为第i-1颗线段树的左儿子的值1。 int modify(int l,int r,int x,int k){//x表示上一颗线段树当前节点的标号//k表示需要新增的元素int ycnt;//新建当前节点y位编号t[y]t[x];//将上一颗线段树的节点的信息传递给当前节点t[y].x;/*因为不包含k的节点不会被访问所以实质上只要被访问过的节点都要加1*/if(lr)return y;int mid(lr)1;if(kmid)t[y].lmodify(l,mid,t[x].l,k);else t[y].rmodify(mid1,r,t[x].r,k);/*根据k值修改左右儿子信息*/return y;//将当前节点的编号号返回上一层} 查询 主席树的查询跟值域线段树的查询差不多值域线段树的查询大家都会吧我这里就不再赘述不过主席树每次需要同时查询两颗线段树如果我们需要查询\([l,r]\)闭区间中第\(k\)小的值我们就查询第\(l-1\)颗线段树和第\(r\)颗线段树的信息由于所有线段树维护的值域完全一样所以我们可以用第r颗线段树询问到的值减去第\(l-1\)颗线段树的值就可以得出\([l,r]\)闭区间的值。(注意你查询到的是离散之后的值你需要输出的是离散之前的值) 具体实现过程 int query(int l,int r,int la,int no,int k){//la,no,分别表示你要查询的两颗线段树的相应节点编号if(lr)return l;/*如果节点内只有一个值这就是第k大直接返回*/int l1t[la].l,l2t[no].l,r1t[la].r,r2t[no].r;//l1,r1,l2,r2分别表示这两个节点的左右儿子。int st[l2].s-t[l1].s , mid(lr)1;if(sk)return query(l,mid,l1,l2,k);else return query(mid1,r,r1,r2,k-s);} 代码 #includebits/stdc.husing namespace std;inline int gi(){char agetchar();int b0;while(a0||a9)agetchar();while(a0a9)bb*10a-0,agetchar();return b;}const int N1e620;struct ljq{int x,id;}b[N];struct tree{int l,r,s;}t[N*5];int cmp(ljq x,ljq y){return x.xy.x;}int a[N],p[N],root[N],n,m,cnt;void work1(){ngi();mgi();for(int i1;in;i)b[i].xgi(),b[i].idi;sort(b1,bn1,cmp);b[0].x-2e9;for(int s0,i1;in;i){if(b[i].x!b[i-1].x)p[s]b[i].x;a[b[i].id]s;}}void bt(int l,int r,int x){if(lr)return;int mid(lr)1;t[x].lcnt;t[x].rcnt;bt(l,mid,t[x].l);bt(mid1,r,t[x].r);}void work2(int l,int r,int la,int no,int x){t[no].st[la].s1;if(lr)return;int mid(lr)1;t[no].lt[la].l;t[no].rt[la].r;if(xmid){t[no].lcnt;work2(l,mid,t[la].l,t[no].l,x);}else{t[no].rcnt;work2(mid1,r,t[la].r,t[no].r,x);}}/*这个构建主席树的实现过程和上面略有不同上面的更方便是我在打带修改的主席树的时候写的这里我懒得改了仅做参考*/int query(int l,int r,int la,int no,int k){if(lr)return l;int l1t[la].l,l2t[no].l,r1t[la].r,r2t[no].r;int st[l2].s-t[l1].s,mid(lr)1;if(sk)return query(l,mid,l1,l2,k);else return query(mid1,r,r1,r2,k-s);}int main(){work1();root[0]cnt;bt(1,n,1);for(int i1;in;i){root[i]cnt;work2(1,n,root[i-1],root[i],a[i]);}while(m--){int lgi(),rgi(),kgi();int xquery(1,n,root[l-1],root[r],k);printf(%d\n,p[x]);}return 0;}转载于:https://www.cnblogs.com/ljq-despair/p/8639345.html
