LUOGU P3709 大爺的字元串題

傳送門

解題思路

看了五分鐘不知道題目在說啥。。。（國文題），後來才知道其實要求的區間衆數（tmd要叙述這麼麻煩嗎）。因為是離線可做，是以自然想到莫隊，開個桶num[x]，表示個數為x的有幾個數，再開個cnt[x]表示x這個數出現的次數，就可以愉快的A了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;
const int MAXN = 200005;

inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}
    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?x:-x;
}

int n,m,cpy[MAXN],a[MAXN],bl[MAXN],siz,rk[MAXN],cnt[MAXN],num[MAXN];
int ans[MAXN],Ans;

struct Data{
    int l,r,id;
}q[MAXN];

inline bool cmp(Data A,Data B){
    if(bl[A.l]!=bl[B.l]) return bl[A.l]<bl[B.l];
    return A.r<B.r;
}

inline void Del(int x){
    num[cnt[x]]--;if(Ans==cnt[x] && !num[cnt[x]]) Ans--;
    cnt[x]--;num[cnt[x]]++;
}

inline void Add(int x){
    num[cnt[x]]--;if(Ans==cnt[x]) Ans++;
    cnt[x]++;num[cnt[x]]++;
}

int main(){
    n=rd(),m=rd();siz=sqrt(n)+1;
    for(int i=1;i<=n;i++) a[i]=rd(),cpy[i]=a[i],bl[i]=i/siz+1;
    sort(cpy+1,cpy+1+n);int u=unique(cpy+1,cpy+1+n)-cpy-1;
    for(int i=1;i<=n;i++) rk[i]=lower_bound(cpy+1,cpy+1+u,a[i])-cpy;
    for(int i=1;i<=m;i++)
        q[i].l=rd(),q[i].r=rd(),q[i].id=i;
    sort(q+1,q+1+m,cmp);
    int L=1,R=0;
    for(int i=1;i<=m;i++){
        while(L<q[i].l) {Del(rk[L]);L++;}
        while(L>q[i].l) {L--;Add(rk[L]);}
        while(R<q[i].r) {R++;Add(rk[R]);}
        while(R>q[i].r) {Del(rk[R]);R--;}
        ans[q[i].id]=Ans;
    }
    for(int i=1;i<=m;i++) printf("-%d\n",ans[i]);
    return 0;
}      

View Code

轉載于:https://www.cnblogs.com/sdfzsyq/p/9687435.html