题解：CF1227D2 Optimal Subsequences (Hard Version)

非常简单的贪心题。

显然这个子序列肯定是这样的：

先选大的数，再选小的数
每一次会尽量把当前那个数选完

于是我们可以把

a_i

离散化，并把

a_i

出现的位置放在 vector 中。

然后把询问离线下来，按照

k

的大小从小到大排序，方便我们一个一个加数来计算答案。令

f_i

表示

a_i

是否被选到了子序列中。

接下来就是求

pos

位的值，我们考虑二分。记

sum_i=\displaystyle\sum_{j=1}^i f_j

，我们在二分的时候只需要判断

sum_{mid}

与

pos

的大小关系即可。

至于如何维护，一个支持单点修改的线段树就行了。

时间复杂度：

O(n \log^2 n)

CPP

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define ls(p) ((p)<<1)
#define rs(p) ((p)<<1|1)
#define lowbit(x) ((x)&(-(x)))
#define abs(x) ((x)>0?(x):(-(x)))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define gc getchar
#define pc putchar
#define sz(v) ((int)(v.size()))
using namespace std;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
inline int read(){
	int x=0,f=1;
	char ch=gc();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=gc();}
	return x*f;
}
inline void print(int x){
	if (x<0) pc('-'),x*=-1;
	if (x<10) pc(x+'0');
    else print(x/10),pc(x%10+'0');
}
const int N=2e5+5;
int a[N],num[N];
vector<int> v[N];
int sum[N];
struct node{
	int k,pos;
	int id,ans;
}qq[N];
bool cmp(node xx,node yy){
	return xx.k<yy.k;
}
int t[N<<2];
void push_up(int p){
	t[p]=t[ls(p)]+t[rs(p)];
}
void update(int l,int p,int pl,int pr){
	if (pl==pr){
		t[p]=1;
		return ;
	}
	int mid=(pl+pr)>>1;
	if (l<=mid) update(l,ls(p),pl,mid);
	else update(l,rs(p),mid+1,pr);
	push_up(p);
}
int query(int l,int r,int p,int pl,int pr){
	if (l<=pl&&pr<=r) return t[p];
	int mid=(pl+pr)>>1;
	int ans=0;
	if (l<=mid) ans+=query(l,r,ls(p),pl,mid);
	if (r>mid) ans+=query(l,r,rs(p),mid+1,pr);
	return ans;
}
bool cmp2(node xx,node yy){
	return xx.id<yy.id;
}
void sol(){
	int n;
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i],num[i]=a[i];
	sort(num+1,num+n+1);
	int cnt=unique(num+1,num+n+1)-num-1;
	for (int i=1;i<=n;i++) a[i]=lower_bound(num+1,num+cnt+1,a[i])-num;
	for (int i=1;i<=n;i++) v[a[i]].pb(i);
	int q;
	cin>>q;
	for (int i=1;i<=q;i++) cin>>qq[i].k>>qq[i].pos,qq[i].id=i;
	sort(qq+1,qq+q+1,cmp);
	int now=cnt;
	int _=0;
	int __=1;
	for (int i=1;i<=n;i++){
		_++;
		if (_>v[now].size()){
			now--;
			_=1;
		}
		update(v[now][_-1],1,1,n);
		while (qq[__].k==i){
			int L=1,R=n;
			int Ans=0;
			while (L<=R){
				int mid=(L+R)>>1;
				if (query(1,mid,1,1,n)>=qq[__].pos) Ans=mid,R=mid-1;
				else L=mid+1;
			}
			qq[__++].ans=Ans;
		}
	}
	sort(qq+1,qq+q+1,cmp2);
	for (int i=1;i<=q;i++) cout<<num[a[qq[i].ans]]<<endl;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=1;
	while (t--) sol();
	return 0;
}

题解：CF1227D2 Optimal Subsequences (Hard Version)

文章操作

相关推荐

评论

题解：CF1227D2 Optimal Subsequences (Hard Version)