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代码

#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记录