浙江龙网

  1. 首页 > 生活百科 > >

洛谷 P4135 作诗 题解( 二 )

生活百科

处理单次询问时间复杂度为n1/2，可以通过本题 。
#include<bits/stdc++.h>using namespace std;const int h=100010;const int b_h=1010;int n,m,c;int len;int a[h];int sum[b_h][b_h];int tim[b_h][h];int tmp[h];int get_pos(int x){    return (x-1)/len+1;}void get_pre(){    for(int i=1;i<=get_pos(n);i++)        for(int j=1;j<=c;j++)            tim[i][j]+=tim[i-1][j];    for(int i=1;i<=get_pos(n);i++){        int kin=0;        for(int j=i;j<=get_pos(n);j++){            for(int k=(j-1)*len+1;k<=min(n,j*len);k++){                tmp[a[k]]++;                if((tmp[a[k]]&1))                    if(tmp[a[k]]>1)                        kin--;                    else                        kin+=0;                else                    kin++;            }            sum[i][j]=kin;        }        for(int j=1;j<=c;j++)            tmp[j]=0;    }}int l,r,lb,rb;int ans;void get_vio(){    ans=0;    for(int i=l;i<=r;i++){        tmp[a[i]]++;        if((tmp[a[i]]&1))            if(tmp[a[i]]>1)                ans--;            else                ans+=0;        else            ans++;    }    for(int i=l;i<=r;i++)        tmp[a[i]]--;}void get_q(){    ans=0;    for(int i=l;i<=lb*len;i++){        tmp[a[i]]++;        if(tmp[a[i]]&1)            if((tim[rb-1][a[i]]-tim[lb][a[i]])&1)                ans++;            else                if(tim[rb-1][a[i]]-tim[lb][a[i]]>0)                    ans--;                else                    if(tmp[a[i]]>1)                        ans--;                    else                        ans-=0;        else            if(tim[rb-1][a[i]]-tim[lb][a[i]]&1)                ans--;            else                ans++;    }    for(int i=(rb-1)*len+1;i<=r;i++){        tmp[a[i]]++;        if(tmp[a[i]]&1)            if((tim[rb-1][a[i]]-tim[lb][a[i]])&1)                ans++;            else                if(tim[rb-1][a[i]]-tim[lb][a[i]]>0)                    ans--;                else                    if(tmp[a[i]]>1)                        ans--;                    else                        ans-=0;        else            if(tim[rb-1][a[i]]-tim[lb][a[i]]&1)                ans--;            else                ans++;    }    for(int i=l;i<=lb*len;i++)        tmp[a[i]]--;    for(int i=(rb-1)*len+1;i<=r;i++)        tmp[a[i]]--;    ans+=sum[lb+1][rb-1];}int main(){    scanf("%d%d%d",&n,&c,&m);    len=sqrt(n);    for(int i=1;i<=n;i++)        scanf("%d",&a[i]),tim[get_pos(i)][a[i]]++;    get_pre();    int lst=0;    for(int i=1;i<=m;i++){        scanf("%d%d",&l,&r);        l=(l+lst)%n+1,r=(r+lst)%n+1;        if(l>r)            swap(l,r);        lb=get_pos(l),rb=get_pos(r);        if(lb>=rb-1)            get_vio();        else            get_q();        lst=ans;        printf("%d\n",ans);    }    return 0;}

推荐阅读


上一篇：带权bitset?/bitset优化莫队 模板 洛谷P4135 Ynoi2016 掉进兔子洞 题解

下一篇：洛谷P4168 蒲公英 分块处理区间众数模板