Written with StackEdit.
Description
Give you a sequence and ask you the kth big number of a interval.
Input
The first line is the number of the test cases.
For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the queries.
The second line contains n integers, describe the sequence.
Each of following m lines contains three integers s, t, k.
[s, t] indicates the interval and k indicates the kth big number in interval [s, t]
Output
For each test case, output m lines. Each line contains the kth big number.
Sample Input
1
10 1
1 4 2 3 5 6 7 8 9 0
1 3 2
Sample Output
2
Solution
发现我一直不会主席树,于是今天找了个板子题来学习一下...
- 主席树是可持久化线段树,而对区间查询第(k)大问题,更准确的说,是可持久化权值线段树.所以需要有权值线段树的前置技能.
- 考虑对区间([1,1],[1,2],[1,3]...[1,n])都各自维护一颗权值线段树.那么询问([L,R])时,某个数的出现次数就应该是这个数在([1,R])这颗权值线段树中的出现次数减去在([1,L-1])这颗权值线段树中的出现次数.
- 这就是其他博客中所说的(T[R]-T[L-1])的含义.我们在查询时,就可以当做是在一颗权值线段树里查询第(k)大,这里就是基本操作了.
- 然而,如果真的去建(n)颗线段树,空间无法承受.注意到后一颗线段树比前一颗线段树,只有修改的位置到根节点的路径有变化,最多(logn)个节点.所以我们新建线段树的时候,可以直接复制上颗树对应节点的信息.递归后链上的信息会自动被修改(参见代码).
#include<bits/stdc++.h>
using namespace std;
typedef long long LoveLive;
inline int read()
{
int out=0,fh=1;
char jp=getchar();
while ((jp>'9'||jp<'0')&&jp!='-')
jp=getchar();
if (jp=='-')
{
fh=-1;
jp=getchar();
}
while (jp>='0'&&jp<='9')
{
out=out*10+jp-'0';
jp=getchar();
}
return out*fh;
}
const int MAXN=1e5+10;
int a[MAXN],b[MAXN];
int n,m;
int rt[MAXN];
struct PreSegTree{
struct node{
int lson,rson,cnt;
}Tree[MAXN*20];
int idx,siz;
PreSegTree()
{
idx=0;
Tree[0].lson=Tree[0].rson=Tree[0].cnt=0;
}
int BuildTree(int l,int r)
{
int cur=++idx;
Tree[cur].cnt=0;
if(l==r)
return cur;
int mid=(l+r)>>1;
Tree[cur].lson=BuildTree(l,mid);
Tree[cur].rson=BuildTree(mid+1,r);
return cur;
}
void update(int &cur,int last,int l,int r,int pos)
{
cur=++idx;
Tree[cur]=Tree[last];
++Tree[cur].cnt;
if(l==r)
return;
int mid=(l+r)>>1;
if(pos<=mid)
update(Tree[cur].lson,Tree[last].lson,l,mid,pos);
else
update(Tree[cur].rson,Tree[last].rson,mid+1,r,pos);
}
int query(int L,int R,int l,int r,int k)
{
if(l==r)
return l;
int p=Tree[Tree[R].lson].cnt-Tree[Tree[L].lson].cnt;
int mid=(l+r)>>1;
if(p>=k)
return query(Tree[L].lson,Tree[R].lson,l,mid,k);
else
return query(Tree[L].rson,Tree[R].rson,mid+1,r,k-p);
}
}T;
int main()
{
int cases=read();
while(cases--)
{
n=read(),m=read();
for(int i=1;i<=n;++i)
b[i]=a[i]=read();
sort(b+1,b+1+n);
int siz=unique(b+1,b+1+n)-(b+1);
T.idx=0;
rt[0]=T.BuildTree(1,siz);
for(int i=1;i<=n;++i)
{
a[i]=lower_bound(b+1,b+1+siz,a[i])-b;
T.update(rt[i],rt[i-1],1,siz,a[i]);
}
for(int i=1;i<=m;++i)
{
int L=read(),R=read(),k=read();
int ans=T.query(rt[L-1],rt[R],1,siz,k);
printf("%d
",b[ans]);
}
}
return 0;
}