【解题报告】Marisa采蘑菇

前言

采用了离线后树状数组的做法，常数极小，且树状数组只需要维护单点修改，区间查找，轻松跑到最优解

题意

给你一个长度为 $n$ 的序列 $a_1,a_2,a_3\dots a_n$ ，$m$ 次询问一个区间 $[l,r]$ ，求区间中出现次数与区间外出现次数的差小于 $k$ 的不同权值个数，对于每个询问 $k$ 相同
$1\le a_i,n,m\le1e6$

题解

类似于各种区间求众数题，很显然的我们可以将询问离线后从左到右依次处理

当找到一个对于 $a[x]$ 满足条件的前缀 x ，即满足 $|2\times cnt[a[x]]-sum[a[x]]|<=k$ 时
我们在 $x$ 插入 1，并删除掉之前在 $pre[x]$ 插入的 1，一直维护最小区间即可

当现在所在的前缀第一次满足 $2\times cnt[a[x]]-sum[a[x]]>k$ 时
我们在区间从左到右第一个 $a[x]$ 处插入 -1，同时将 1 右移，之后每多遍历到一个 $a[x]$ ，我们就分别将 -1 和 1 向右移到下一个 $a[x]$，这里可以对每个权值预处理维护一个仅包含 $next$ 指针的链表来 $O(1)$ 解决

注意判断之前是否插入过，防止树状数组访问到 0 下标，同时也注意对于一个数，如果没有进入过第一种情况，那么它将不可能有贡献

把思路理清楚，代码实现可能有点绕
$$
\large\color{grey}{\text{Talk is cheap , show you the code}}
$$

代码

#include<stdio.h>
#include<iostream>
#include<cstring>
#include<math.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1000005;
const int inf=0x3f3f3f3f;
int n,m,k,col[maxn],net[maxn],pos[maxn],la[maxn];
int cnt[maxn],a[maxn],sum[maxn],ans[maxn];
struct ques
{
    int l,r,id;
    friend bool operator<(ques x,ques y){return x.r<y.r;}
}q[maxn];

inline int read(void)
{
    int num,sign=1;char c;
    while(!isdigit(c=getchar()))if(c=='-')sign=0;num=c-'0';
    while(isdigit(c=getchar()))num=(num<<1)+(num<<3)+c-'0';
    return sign?num:-num;
}
int tr[maxn];
inline void insert(int x,int d){for(;x<=n;x+=x&-x)tr[x]+=d;}
inline int query(int x){int res=0;for(;x;x-=x&-x)res+=tr[x];return res;}

signed main(void)
{
    n=read(),m=read(),k=read();
    for(register int i=1;i<=n;++i)a[i]=read(),++sum[a[i]];
    for(register int i=n;i;--i)net[i]=col[a[i]],col[a[i]]=i;
    for(register int i=1;i<=m;++i)q[i].l=read(),q[i].r=read(),q[i].id=i;
    sort(q+1,q+1+m);
    for(register int j=1,i=1;i<=n;++i)
    {
        ++cnt[a[i]];
        if(2*cnt[a[i]]-sum[a[i]]<=k&&2*cnt[a[i]]-sum[a[i]]>=-k)
        {
            int u;
            if(pos[a[i]])
            {
                insert(pos[a[i]],-1);
                u=net[pos[a[i]]];
            }
            else u=col[a[i]];
            insert(u,1),pos[a[i]]=u;
        }
        else if(2*cnt[a[i]]-sum[a[i]]>k)
        {
            int u;
            if(la[a[i]])insert(la[a[i]],1);
            if(pos[a[i]])
            {
                insert(pos[a[i]],-1);
                u=net[pos[a[i]]];
                if(!la[a[i]])la[a[i]]=col[a[i]];
                else la[a[i]]=net[la[a[i]]];
                insert(la[a[i]],-1);
                insert(u,1);pos[a[i]]=u;
            }
        }
        while(q[j].r==i)ans[q[j].id]=query(q[j].r)-query(q[j].l-1),++j;
    }
    for(register int i=1;i<=m;++i)printf("%d\n",ans[i]);
    return 0;
}