codeforces 1262D Optimal Subsequences 主席树询问第k小

题意

给定长度为\(n\)的序列\(a\)，以及m个询问\(<k,pos>\)，每次询问满足下列条件的子序列中第\(pos\)位的值为多少。

子序列长度为\(k\)
序列和是所有长度为\(k\)的子序列中最大的
字典序是所有满足上述两个条件的序列中最小的

解题思路

稍作分析即可得出，将序列按值的大小作为第一关键字（升序），下标作为第二关键字（降序）排序，所得序列的后\(k\)个元素即为询问长度为\(k\)时满足给定条件的序列中的元素，所以答案就是后\(k\)个元素中下标第\(pos\)小的元素的值，用主席树维护即可。

AC代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=2e5+5;

int n,m,t[maxn];

struct node{

	int v,id;

	bool operator<(const node& nd){

		if(v==nd.v)return id>nd.id;

		return v<nd.v;

	}

}a[maxn];

int T[maxn],tot;

int sum[maxn<<5],L[maxn<<5],R[maxn<<5];

int update(int rt,int l,int r,int p){

	int nrt=++tot;

	L[nrt]=L[rt]; R[nrt]=R[rt]; sum[nrt]=sum[rt]+1;

	if(l!=r){

		int mid=(l+r)>>1;

		if(p<=mid)L[nrt]=update(L[rt],l,mid,p);

		else R[nrt]=update(R[rt],mid+1,r,p);

	}

	return nrt;

}

int query(int u,int v,int l,int r,int k){

	if(l==r)return l;

	int cnt=sum[L[v]]-sum[L[u]];

	int mid=(l+r)>>1;

	if(k<=cnt)return query(L[u],L[v],l,mid,k);

	else return query(R[u],R[v],mid+1,r,k-cnt);

}

int main()

{

//	freopen("in.txt","r",stdin);

	scanf("%d",&n);

	for(int i=1;i<=n;i++){

		scanf("%d",&a[i].v);

		a[i].id=i;	t[i]=a[i].v;

	}

	sort(a+1,a+1+n);

	for(int i=1;i<=n;i++)T[i]=update(T[i-1],1,n,a[i].id);

	int k,pos;

	scanf("%d",&m);

	while(m--){

		scanf("%d %d",&k,&pos);

		printf("%d\n",t[query(T[n-k],T[n],1,n,pos)]);

	}

	return 0;

}

巴特西

codeforces 1262D Optimal Subsequences 主席树询问第k小

题意

解题思路

AC代码

最新文章

热门文章