Codeforces 455D Serega and Fun【解法二】 -开发者知识库

Codeforces 455D Serega and Fun【解法二】 -开发者知识库,第1张

把序列分成 n 塊,每一塊用鏈表維護元素,再維護每種顏色出現的次數。每次修改直接暴力移動並且修改顏色計數,這些都可以 O(n) 完成。詢問的時候整塊直接統計,不完整的暴力。也是 O(n) 的。注意到修改太多以后可能讓塊的大小不平衡,我們每 n 次修改之后 O(n) 重構一次,這樣保證任何時刻塊的大小都是 O(n)

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100010,maxm=320;
int a[maxn],val[maxn],cnt[maxm][maxn],edi[maxm][maxn],head[maxm],next[maxn],L[maxn],R[maxn],n,m,q,clo;
void init()
{
    clo  ;
    for (int i=1;i<=m;i  )
    {
        L[i]=R[i-1] 1;
        R[i]=(i==m?n:L[i] m-1);
        head[i]=a[L[i]];
        for (int j=L[i];j<R[i];j  ) next[a[j]]=a[j 1];
        next[a[R[i]]]=0;
        for (int j=head[i];j;j=next[j])
            if (edi[i][val[j]]<clo)
            {
                edi[i][val[j]]=clo;
                cnt[i][val[j]]=1;
            }
            else cnt[i][val[j]]  ;
    }
}
void modi(int l,int r)
{
    int pl,pr,u,v,x;
    for (int i=1;i<=m;i  )
        if (L[i]<=r&&r<=R[i])
        {
            pr=i;
            v=head[i];
            for (int j=L[i] 1;j<=r;j  )
            {
                x=v;
                v=next[v];
            }
            if (head[i]==v) head[i]=next[v];
            else next[x]=next[v];
            cnt[i][val[v]]--;
        }
    for (int i=1;i<=m;i  )
        if (L[i]<=l&&l<=R[i])
        {
            pl=i;
            u=head[i];
            for (int j=L[i] 1;j<=l;j  )
            {
                x=u;
                u=next[u];
            }
            if (head[i]==u) head[i]=v;
            else next[x]=v;
            next[v]=u;
            if (edi[i][val[v]]<clo)
            {
                edi[i][val[v]]=clo;
                cnt[i][val[v]]=1;
            }
            else cnt[i][val[v]]  ;
        }
    if (pl<pr)
    {
        R[pl]  ;
        L[pr]  ;
        for (int i=pl 1;i<pr;i  )
            L[i]  ,R[i]  ;
    }
}
int qry(int l,int r,int k)
{
    int ans=0,pl,pr;
    for (int i=1;i<=m;i  )
    {
        if (L[i]<=l&&l<=R[i]) pl=i;
        if (L[i]<=r&&r<=R[i]) pr=i;
    }
    if (pl==pr)
    {
        for (int i=head[pl],j=L[pl];j<=r;i=next[i],j  )
            if (j>=l&&val[i]==k) ans  ;
        return ans;
    }
    for (int i=head[pl],j=L[pl];j<=R[pl];i=next[i],j  )
        if (j>=l&&val[i]==k) ans  ;
    for (int i=head[pr],j=L[pr];j<=r;i=next[i],j  )
        if (val[i]==k) ans  ;
    for (int i=pl 1;i<pr;i  )
        if (edi[i][k]==clo) ans =cnt[i][k];
    return ans;
}
int main()
{
    //freopen("f.in","r",stdin);
    int last=0,now=0,opt,l,r,k,t;
    scanf("%d",&n);
    for (int i=1;i<=n;i  ) scanf("%d",&val[i]);
    m=sqrt(n);
    for (int i=1;i<=n;i  ) a[i]=i;
    init();
    scanf("%d",&q);
    while (q--)
    {
        scanf("%d%d%d",&opt,&l,&r);
        l=(l last-1)%n 1;
        r=(r last-1)%n 1;
        if (l>r) swap(l,r);
        if (opt==1)
        {
            modi(l,r);
            if (  now==m)
            {
                t=0;
                for (int i=1;i<=m;i  )
                    for (int j=head[i];j;j=next[j])
                        a[  t]=j;
                init();
                now=0;
            }
        }
        else
        {
            scanf("%d",&k);
            k=(k last-1)%n 1;
            printf("%d\n",last=qry(l,r,k));
        }
    }
}

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复