[luogu5048] [Ynoi2019模拟赛] Yuno loves sqrt technology III

题目链接

Solution

思路同[BZOJ2724] [Violet 6]蒲公英，只不过由于lxl过于毒瘤，我们有一些更巧妙的操作。

首先还是预处理$f[l][r]$表示$l\sim r$块的众数数量，注意这里不要求具体是什么，我们就有一些奇技淫巧了。

当然第一步还是离散化，对于权值为$v$的点，我们开一个$vector$来从小到大存这个权值在哪里出现过，在记个$pos[i]$表示$i$在$vector $内的下标是什么。

那么预处理$f[l][r]$的时候，我们参照区间$dp$，令$ans=f[l][r-1]$，然后扫一遍$r$这个块，设当前的点为$i$，那么如果$pos[i]-ans$这个$vector$内的位置$x$，满足$x\geqslant st[l]$，其中$st[l]$表示$l$块起始位置，那么我们就暴力的$ans++$。

至于为什么很显然，留给读者自己思考。

那么询问也可以仿照上面的，中间的整块直接用预处理的答案，左边的倒序枚举，然后右边的顺序枚举，暴力更新答案就好了。

#include<bits/stdc++.h>

using namespace std;

void read(int &x) {

    x=0;int f=1;char ch=getchar();

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;

    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;

}

void print(int x) {

    if(x<0) putchar('-'),x=-x;

    if(!x) return ;print(x/10),putchar(x%10+48);

}

void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double

#define ll long long 

const int maxn = 8e5+10;

const int inf = 1e9;

const lf eps = 1e-8;

vector<int > v[maxn];

int n,m,a[maxn],p[maxn],pos[maxn],bel[maxn],st[maxn],ed[maxn],f[800][800],s[maxn];

int solve(int l,int r) {

    int ans=f[bel[l]+1][bel[r]-1];

    if(bel[l]==bel[r]) {

        for(int i=l;i<=r;i++) s[a[i]]=0;

        for(int i=l;i<=r;i++) ans=max(ans,++s[a[i]]);

        return ans;

    }

    for(int i=ed[bel[l]];i>=l;i--)

        if(pos[i]+ans<(int)v[a[i]].size())

            if(v[a[i]][pos[i]+ans]<=r) ans++;

    for(int i=st[bel[r]];i<=r;i++)

        if(pos[i]-ans>=0)

            if(v[a[i]][pos[i]-ans]>=l) ans++;

    return ans;

}

int main() {

    read(n),read(m);for(int i=1;i<=n;i++) read(a[i]),p[i]=a[i];

    sort(p+1,p+n+1);int M=unique(p+1,p+n+1)-p-1,b=sqrt(n);

    for(int i=1;i<=n;i++) a[i]=lower_bound(p+1,p+M+1,a[i])-p;

    for(int i=1;i<=n;i++) v[a[i]].push_back(i),pos[i]=v[a[i]].size()-1;

    for(int i=1;i<=n;i++) bel[i]=(i-1)/b+1;int cnt=bel[n];

    for(int i=1;i<=n;i++) if(bel[i]!=bel[i-1]) st[bel[i]]=i,ed[bel[i]-1]=i-1;

    st[1]=1,ed[cnt]=n;

    for(int x=1;x<=cnt;x++) {

        for(int i=st[x];i<=ed[x];i++) s[a[i]]=0;

        for(int i=st[x];i<=ed[x];i++) s[a[i]]++,f[x][x]=max(f[x][x],s[a[i]]);

    }

    for(int len=2;len<=cnt;len++)

        for(int j=1;j<=cnt-len+1;j++) {

            int l=j,r=j+len-1,ans=f[l][r-1];

            for(int i=st[r];i<=ed[r];i++) {

                if(pos[i]-ans<0) continue;

                if(v[a[i]][pos[i]-ans]>=st[l]) ans++;

            }f[l][r]=ans;

        }

    int lstans=0;

    for(int q=1;q<=m;q++) {

        int l,r;read(l),read(r);

        l^=lstans,r^=lstans;

        write(lstans=solve(l,r));

    }

    return 0;

}

巴特西

[luogu5048] [Ynoi2019模拟赛] Yuno loves sqrt technology III

题目链接

Solution

最新文章

热门文章