[Ynoi2019模拟赛]Yuno loves sqrt technology III 题解 分块

· · 题解

题目传送门

题意

Sol

看到 \text{Ynoi} 考虑分块。（

常规套路，先预处理每组连续块内的答案。

共 \sqrt n 个块，对于每个块作为左端点有 O(n) 的处理，预处理 O(n\sqrt n)。

考虑询问操作。

对于囊括在其中的块，可以直接拿来用。

剩余边界上最多 2\sqrt n 个元素。

考虑对于每个边界元素进行查询。

然鹅现在已经 O(m\sqrt n) 了，似乎查询需要很小的复杂度才行诶qaq。

考虑利用上面已处理的答案。

对一个元素，考虑它向右答案位的同值元素是否在答案区间内。

由于每次更新答案会 +1，而答案最多会 +2\sqrt n，于是更新答案复杂度也为 \sqrt n。

那么我们还需考虑 O(1) 解决查询同值元素的位置。

考虑 \text{vector} 记录同值元素位置，再随便拿个东西记该数在 \text{vector} 中位置即可。记得离散化。

总复杂度 (n+m)\sqrt n

\text{Code}

// wish to get better qwq

#include<bits/stdc++.h>
#define re register int
#define pb push_back

using namespace std;
typedef long long ll;

template <typename T> inline void rd(T &x){
    int fl=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    x*=fl;
}
void wr(int x){
    if(x<0) x=-x,putchar('-');
    if(x<10) putchar(x+'0');
    if(x>9) wr(x/10),putchar(x%10+'0');
}

inline int mx(int x,int y){return x<y?y:x;}

// ---------- IO ---------- //

const int N=5e5+5,SQ=735;
int n,m,sum[SQ][SQ],a[N],b[N],ans,sub[N],len=SQ-5,cnt[N];
vector<int> ran[N];

// ---------- Sqrt ---------- //

inline int block(int x){return (x-1)/len+1;}
inline int L(int x){return (x-1)*len+1;}
inline int R(int x){return x*len;}

inline void init(){
    int lst=block(n);
    for(re i=1;i<=lst;i++){
        memset(cnt,0,sizeof(cnt));
        for(re j=i;j<=lst;j++){
            sum[i][j]=sum[i][j-1];
            int qaq=L(j),qwq=R(j);
            for(re k=qaq;k<=qwq;k++) sum[i][j]=mx(sum[i][j],++cnt[a[k]]);
        }
    }
}

inline int query(int l,int r){
    int tot=0;
    if(block(l)==block(r)){
        for(re i=l;i<=r;i++) cnt[a[i]]=0;
        for(re i=l;i<=r;i++) tot=mx(tot,++cnt[a[i]]);
        return tot;
    }
    tot=sum[block(l)+1][block(r)-1];
    int qaq=R(block(l));
    for(re i=l;i<=qaq;i++){
        int nw=sub[i]+tot;
        while(nw<ran[a[i]].size()&&ran[a[i]][nw]<=r) tot++,nw++;
    }
    qaq=L(block(r));
    for(re i=qaq;i<=r;i++){
        int nw=sub[i]-tot;
        while(nw>=0&&ran[a[i]][nw]>=l) tot++,nw--;
    }
    return tot;
}

// ---------- Operation ---------- //

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    rd(n);rd(m);
    for(re i=1;i<=n;i++) rd(a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    for(re i=1;i<=n;i++) a[i]=lower_bound(b+1,b+n+1,a[i])-b,ran[a[i]].pb(i),sub[i]=ran[a[i]].size()-1;
    init();
    for(re i=1,u,v;i<=m;i++){
        rd(u);rd(v);
        u^=ans;v^=ans;
        wr(ans=query(u,v));puts("");
    }
    return 0;
}

// ---------- Main ---------- //

改进了码风果然更好看了qwq