[COCI2020-2021#6] Index 题解

· · 题解

前置知识：普通莫队

前言：

熟悉的区间询问，熟悉的数据范围。嗯？好！上莫队！

由于本人做这道题时是初学莫队，根本不知道还有值域分块这种东西，好像所有的莫队都可值域分块，其他大佬的题解里要么用了主席树和整体二分 ( 蒟蒻太弱啦，根本不会！) ，要么都是值域分块莫队，所以这里给出一种普通莫队的做法。

想要 \Theta (1) 转移当前答案看起来不太可做，但我们考虑答案在什么情况才会改变。

  1. 当 sum[k+1] > k ：k + 1 。

  2. 当 sum[k] < k : k - 1 。

根据这两个性质，我们可以开一个桶维护每个数的出现次数，再用一个数维护大于等于 k 的数有多少个。在每次增 / 删数时检查是否需要更改答案就行了。在每次询问结束后更新答案也行。

然后就做到 \Theta(1) 转移和查询答案啦！

最后附上代码:

#include <bits/stdc++.h>
using namespace std;
int read() {
    int x=0; char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x;
}
void put(int x) {
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
const int Maxn=2e5+10;
int n,q,unit,a[Maxn],cnt[Maxn],ans[Maxn];
struct node {
    int l,r,id;
    bool operator<(const node &b) const {
        if(l/unit!=b.l/unit) return l<b.l;
        return l/unit&1?r<b.r:r>b.r;
    }
} ask[Maxn];
signed main() {
    n=read(),q=read(),unit=sqrt(n);
    for(register int i=1; i<=n; ++i) a[i]=read();
    for(register int i=1; i<=q; ++i) ask[i].l=read(),ask[i].r=read(),ask[i].id=i;
    sort(ask+1,ask+q+1);
    register int l=ask[1].l,r=ask[1].l-1,k=0,t=0;
    for(register int i=1; i<=q; ++i) {
        while(l>ask[i].l) ++cnt[a[--l]],t+=(a[l]>=k);
        while(r<ask[i].r) ++cnt[a[++r]],t+=(a[r]>=k);
        while(l<ask[i].l) t-=(a[l]>=k),--cnt[a[l++]];
        while(r>ask[i].r) t-=(a[r]>=k),--cnt[a[r--]];
        while(t-cnt[k]>k) t-=cnt[k++];
        while(t<k) t+=cnt[--k]; 
        ans[ask[i].id]=k;
    }
    for(register int i=1;i<=q;++i) put(ans[i]),putchar('\n');
    return 0;
}