P3730 曼哈顿交易题解

补充一种其他题解很少提到的做法。

题目分析

设

cnt_i

为持有

i

股票的人数，本题要在区间内查询

cnt_i

的第

k

小，这个信息很难直接用线段树等其他数据结构维护，于是考虑莫队。

我们将

cnt_i

再放入一个桶中，记

cnt2_j

为

cnt_i=j

的个数，想要在这个桶中找到第

k

小的，自然而然就可以想到对这个桶求前缀和，然后就可以通过二分快速地找到第

k

小的数了。

接下来我们考虑莫队在区间扩展中对这个前缀和数组的影响。首先考虑向区间内加入一个数，设这个数为

v

，则

cnt_v

会加一，对应到

cnt2

上就是

cnt2_{cnt_v}-1,cnt2_{cnt_v+1}+1

，再看前缀和数组，

cnt_v

之后的位置

-1

和

+1

都会抵消掉，所以只需在

cnt_v

的位置上减一。从区间中去除一个数也是同理。

总的时间复杂度为

O(n\sqrt n+m\log n)

AC代码

CPP

#include<bits/stdc++.h>
#define FOR(i, l, r) for(int (i)=(l); (i)<=(r); (i)++)
#define ROF(i, r, l) for(int (i)=(r); (i)>=(l); (i)--)
#define deb(x) cerr << "debug " << #x << ": " << x << endl;
using namespace std;
inline int read(){
	int x = 0, f = 1;
	char c = getchar();
	while(c>'9' || c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9'){
		x = (x<<1)+(x<<3)+c-48;
		c = getchar();
	}
	return x*f;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x = -x;
	}
	if(x>=10) write(x/10);
	putchar(x%10+48);
}
const int N = 1e5+10;
int cnt[N], sum[N], a[N], ls[N], ans[N];
struct ask{
	int l, r, k, id;
}q[N]; 
inline void add(int v){
	sum[cnt[v]++]--;
}
inline void del(int v){
	sum[--cnt[v]]++;
}
int main(){
	int n = read(),m = read(); 
	FOR(i,1,n)ls[i] = a[i] = read();
	sort(ls+1, ls+n+1);
	FOR(i,1,n)a[i] = lower_bound(ls+1, ls+n+1, a[i])-ls;
	FOR(i,1,m){
		q[i].id = i;
		q[i].l=read(),q[i].r=read(),q[i].k=read();
	}
	int t = sqrt(n);
	sort(q+1, q+m+1, [&](ask a, ask b){
		return a.l/t!=b.l/t?a.l/t<b.l/t:a.r<b.r;
	});
	int l = 0, r = 0;
	FOR(i,1,m){
		while(r>q[i].r)del(a[r--]);
		while(r<q[i].r)add(a[++r]);
		while(l<q[i].l)del(a[l++]);
		while(l>q[i].l)add(a[--l]);
		if(sum[n]-sum[0]<q[i].k)ans[q[i].id]=-1;
		else ans[q[i].id] = lower_bound(sum+1, sum+n+1, sum[0]+q[i].k)-sum; 
	} 
	FOR(i,1,m){
		printf("%d\n", ans[i]);
	}
	return 0;
}

AC记录

P3730 曼哈顿交易题解

文章操作

题目分析

AC代码

相关推荐

评论

P3730 曼哈顿交易题解