主席树---求第k大的数poj2104

xiaoxiao2022-06-28 36

主席树链接

http://wenku.baidu.com/link?url=RjMLWxKZ-fw6U7PvP9LcGtXYzJZ2uH1H6gJrCPA1mP_o4NkzGqyl9QqcS9xoI6tFP4S7k9x8vFNl-57hvakfmS6TWvzhzEr4A5LNEgD5xi7

</pre>主席树<a target=_blank target="_blank" href="http://wenku.baidu.com/link?url=EBBTaEcXOKwZvD3jbmZYPv7Z-aUWif582qcOwaWdz313eVInLS9UjPOIfSu06YLKqOn2hOw3DdAuYQir0GcbMgK8qeIFtXG7rlqlCzmbW7W">百度文库---主席树详解</a>主席树就是对原来的数列[1..n]的每一个前缀[1..i]（1≤i≤n）建立一棵线段树，每一个线段树范围都是[1,n]，每一个线段树存储[1,i]的对应的数（经离散化后的序列）在区间[1,n]出现的个数。举例：序列：4 1 3 2查询：[1,3]内第2大的数1.建树（建立一颗空的范围为[1,n]的线段树）首先需要建立一棵空的线段树，也是最原始的主席树，此时主席树只含一个空节点，此时设根节点为rt[0],表示刚开始的初值状态，然后依次对原序列按某种顺序更新，即将原序列加入到对应位置。此过程与线段树一样，时间复杂度为O（nlogn)，空间复杂度O（nlog(n))<img src="https://img-blog.csdn.net/20160914133913127?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />2.更新操作从前缀[1,1]到[1,n]更新，一共n次，每次更新相当于在上一棵线段树上更新点的标号和权值，物理上还是用了之前的树，逻辑上新建了一棵线段树。<img src="https://img-blog.csdn.net/20160914134320372?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" /><img src="https://img-blog.csdn.net/20160914134947758?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" /><img src="https://img-blog.csdn.net/20160914135034493?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />3.查询若要在区间[l,r]查询，则将rt[l]-rt[l-1]（线段树每个结点相减）得到的线段树进行查询，设左节点中存的个数为cnt，当k<=cnt时，我们直接查询左儿子中第k小的数即可，如果k>cnt，我们只要去查右儿子中第k-cnt小的数即可，这边是一道很简单的线段树了。就如查找[1, 3]的第2小数（图上为了方便，重新给节点标号），从根节点1向下搜，发现左儿子2的个数为1,1<2，所有去右儿子3中搜第2-1级第1小的数，然后再往下搜，发现左儿子6便可以了，此时已经搜到底端，所以直接返回节点6维护的值3即可就可以了。<img src="https://img-blog.csdn.net/20160914135054259?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />Description<div class="ptx" lang="en-US" style="font-family:'Times New Roman',Times,serif; font-size:14px">You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment. That is, given an array a[1...n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i...j] segment, if this segment was sorted?" For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.</div>Input<div class="ptx" lang="en-US" style="font-family:'Times New Roman',Times,serif; font-size:14px">The first line of the input file contains n --- the size of the array, and m --- the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000). The second line contains n different integer numbers not exceeding 109 by their absolute values --- the array for which the answers should be given. The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).</div>Output<div class="ptx" lang="en-US" style="font-family:'Times New Roman',Times,serif; font-size:14px">For each question output the answer to it --- the k-th number in sorted a[i...j] segment.</div>Sample Input<pre class="sio" style="font-family:'Courier New',Courier,monospace; font-size:14px">7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3

Sample Output

5 6 3

Hint

This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed. #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<vector> #include<stack> #define inf 0x3f3f3f3f #define ll long long using namespace std; const int MAX=100010; int root[MAX];//存储根节点的序号 int ls[MAX*20];//存储左节点的序号，乘20是最多20层 int rs[MAX*20];//存储右节点的序号 int num[MAX];//序列的值 int lisan[MAX];//离散化后的序列值 int sum[MAX*20];//每个结点的权值，即数字出现的次数 int tot;//当前结点个数 void build(int l,int r,int &rt)//建一棵空的范围为[1,n]的线段树 { rt=++tot; sum[rt]=0; if(l==r) return ; int mid=(l+r)/2; build(l,mid,ls[rt]); build(mid+1,r,rs[rt]); } void update(int pre,int x,int l,int r,int &rt)//使用上一棵线段树模板进行更新,l，r是指数值的区间，而不是下标 { rt=++tot; ls[rt]=ls[pre]; rs[rt]=rs[pre]; sum[rt]=sum[pre]+1; if(l==r) return ; int mid=(l+r)/2; if(x<=mid) update(ls[pre],x,l,mid,ls[rt]); else update(rs[pre],x,mid+1,r,rs[rt]); } int query(int s,int t,int l,int r,int k)//使用根节点标号为s和t的线段树做差得到合的线段树并查询 { if(l==r) return l; int mid=(l+r)/2; int cnt=sum[ls[t]]-sum[ls[s]]; if(k<=cnt) return query(ls[s],ls[t],l,mid,k); else return query(rs[s],rs[t],mid+1,r,k-cnt); } int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { scanf("%d",&num[i]); lisan[i]=num[i]; } tot=0;//当前为第几个结点 //离散化处理 sort(lisan+1,lisan+n+1); int cnt=unique(lisan+1,lisan+n+1)-lisan-1;//unique返回去重后最后一个元素的下一个地址 build(1,cnt,root[0]); for(int i=1;i<=n;i++) { num[i]=lower_bound(lisan+1,lisan+cnt+1,num[i])-lisan; cout<<num[i]<<endl; } for(int i=1;i<=n;i++) update(root[i-1],num[i],1,cnt,root[i]); while(m--) { int l,r,k; scanf("%d%d%d",&l,&r,&k); int id=query(root[l-1],root[r],1,cnt,k); cout<<lisan[id]<<endl; } return 0; }

转载请注明原文地址: https://ju.6miu.com/read-1124201.html

专利

最新回复(0)