首页 > 代码库 > 【分块】bzoj2821 作诗(Poetize)
【分块】bzoj2821 作诗(Poetize)
分块，预处理出：
①第i块到第j块之间的偶数值的种类数。
②在前i块中，每个值出现的次数。（前缀和）（差分）
每次询问时，对于不在整块中的元素，进行暴力转移。
注意：减少memset的使用，千万不要写100000个memset，否则会TLE，宁愿每次询问之后O(sqrt(n))地一个个减掉那个记录每个值出现次数的临时数组。
Code:
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 int n,kind,m,a[100001],sz,sum,num[100001],l[320],r[320],w[320][320]; 7 int Time[100001],ans,x,y; 8 int ev[100001][320]; 9 void makeev() 10 { 11 for(int i=1;i<=n;i++) 12 for(int j=num[i];j<=sum;j++) 13 ev[a[i]][j]++; 14 } 15 inline int getsum(const int &v,const int &L,const int &R){return ev[v][R]-ev[v][L-1];} 16 void makeblock() 17 { 18 for(sum=1;sum*sz<n;sum++) 19 { 20 l[sum]=(sum-1)*sz+1; 21 r[sum]=sum*sz; 22 for(int i=l[sum];i<=r[sum];i++) 23 num[i]=sum; 24 } 25 l[sum]=sz*(sum-1)+1; 26 r[sum]=n; 27 for(int i=l[sum];i<=r[sum];i++) 28 num[i]=sum; 29 } 30 void init() 31 { 32 for(int i=1;i<=sum;i++) 33 { 34 memset(Time,0,sizeof(Time)); 35 for(int j=i;j<=sum;j++) 36 { 37 w[i][j]=w[i][j-1]; 38 for(int k=l[j];k<=r[j];k++) 39 { 40 Time[a[k]]++; 41 if(!(Time[a[k]]&1))w[i][j]++; 42 else if(Time[a[k]]!=1)w[i][j]--; 43 } 44 } 45 } 46 } 47 int res,CH[20],Num;char c; 48 inline int G() 49 { 50 res=0;c=‘*‘; 51 while(c<‘0‘||c>‘9‘)c=getchar(); 52 while(c>=‘0‘&&c<=‘9‘){res=res*10+(c-‘0‘);c=getchar();} 53 return res; 54 } 55 inline void P(int x) 56 { 57 if(!x){putchar(‘0‘);putchar(‘\n‘);return;}Num=0; 58 while(x>0){CH[++Num]=x%10;x/=10;} 59 while(Num)putchar(CH[Num--]+48); 60 putchar(‘\n‘); 61 } 62 int main() 63 { 64 n=G();kind=G();m=G(); 65 sz=sqrt(n); 66 for(int i=1;i<=n;i++)a[i]=G(); 67 makeblock();init();makeev(); 68 memset(Time,0,sizeof(Time)); 69 for(int i=1;i<=m;i++) 70 { 71 x=G();y=G();x=(x+ans)%n+1;y=(y+ans)%n+1;if(x>y)swap(x,y); 72 ans=w[num[x]+1][num[y]-1]; 73 if(num[x]+1>=num[y]) 74 { 75 for(int j=x;j<=y;j++) 76 { 77 Time[a[j]]++; 78 if(!(Time[a[j]]&1))ans++; 79 else if(Time[a[j]]!=1)ans--; 80 } 81 for(int j=x;j<=y;j++)Time[a[j]]--; 82 } 83 else 84 { 85 for(int j=x;j<=r[num[x]];j++) 86 { 87 Time[a[j]]++; 88 if(!((Time[a[j]]+getsum(a[j],num[x]+1,num[y]-1))&1))ans++; 89 else if(Time[a[j]]+getsum(a[j],num[x]+1,num[y]-1)!=1)ans--; 90 } 91 for(int j=l[num[y]];j<=y;j++) 92 { 93 Time[a[j]]++; 94 if(!((Time[a[j]]+getsum(a[j],num[x]+1,num[y]-1))&1))ans++; 95 else if(Time[a[j]]+getsum(a[j],num[x]+1,num[y]-1)!=1)ans--; 96 } 97 for(int j=x;j<=r[num[x]];j++)Time[a[j]]--; 98 for(int j=l[num[y]];j<=y;j++)Time[a[j]]--; 99 }100 P(ans);101 }102 return 0;103 }
【分块】bzoj2821 作诗(Poetize)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。