2821: 作诗(Poetize)
Time Limit: 50 Sec Memory Limit: 128 MBSubmit: 996 Solved: 318
[Submit][Status]
Description
神犇SJY虐完HEOI之后给傻×LYD出了一题：
SHY是T国的公主，平时的一大爱好是作诗。
由于时间紧迫，SHY作完诗之后还要虐OI，于是SHY找来一篇长度为N的文章，阅读M次，每次只阅读其中连续的一段[l,r]，从这一段中选出一些汉字构成诗。因为SHY喜欢对偶，所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认为选出的汉字的种类数（两个一样的汉字称为同一种）越多越好（为了拿到更多的素材！）。于是SHY请LYD安排选法。
LYD这种傻×当然不会了，于是向你请教……
问题简述：N个数，M组询问，每次问[l,r]中有多少个数出现正偶数次。
Input
输入第一行三个整数n、c以及m。表示文章字数、汉字的种类数、要选择M次。
第二行有n个整数，每个数Ai在[1, c]间，代表一个编码为Ai的汉字。
接下来m行每行两个整数l和r，设上一个询问的答案为ans(第一个询问时ans=0)，令L=(l+ans)mod n+1, R=(r+ans)mod n+1，若L>R，交换L和R，则本次询问为[L,R]。
Output
输出共m行，每行一个整数，第i个数表示SHY第i次能选出的汉字的最多种类数。
Sample Input
1 2 2 3 1
0 4
1 2
2 2
2 3
3 5
Sample Output
0
0
0
1
HINT
对于100%的数据，1<=n,c,m<=10^5
分块……
为什么不让用莫队！！！！！
可恶的强制在线！！！！！
于是只能用分块了……
分成sqrt(n)块……
ans[i][j]表示第i块到第j块的答案……预处理……
sum[i][j]表示从开头到底i块，数字j出现的次数……预处理……
对于l~r,中间包含的块直接ans算答案，旁边多余的暴力维护答案……
具体的自己yy……
效率O(n√n)……
常数忽略……
好了就这样了……
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <set>
using namespace std;
inline int maxx(const int &a,const int &b){if (a>b)return a;return b;}
inline int minn(const int &a,const int &b){if (a<b)return a;return b;}
int a[100005],b[100005],c,d,e,f[100005],g,h,i,j,k,l,m,n,cnt,tot,X,r;
int sum[318][100002];
int ans[350][350];
int main(){
scanf("%d%d%d",&n,&cnt,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
X=(int)sqrt(n);
for(i=1;i<=X;i++){
for(j=1;j<=cnt;j++)sum[i][j]=sum[i-1][j];
for(j=(i-1)*X+1;j<=i*X;j++)
sum[i][a[j]]++;
}
for(i=1;i<=X;i++){
for(j=1;j<=cnt;j++)f[j]=0;
for(j=(i-1)*X+1;j<=i*X;j++){
f[a[j]]++;
if (!(f[a[j]]&1))ans[i][i]++;
if ((f[a[j]]&1)&&f[a[j]]>1)ans[i][i]--;
}
for(l=i+1;l<=X;l++){
ans[i][l]=ans[i][l-1];
for(j=(l-1)*X+1;j<=l*X;j++){
f[a[j]]++;
if (!(f[a[j]]&1))ans[i][l]++;
if ((f[a[j]]&1)&&f[a[j]]>1)ans[i][l]--;
}
}
}
int lastans=0;
memset(f,0,sizeof(f));
for(i=1;i<=m;i++){
scanf("%d%d",&l,&r);
l=(l+lastans)%n+1;
r=(r+lastans)%n+1;
if (l>r)swap(l,r);
int L=(l-1)/X+1,R=(r-1)/X+1;
if (L==R){
h=0;
for(j=l;j<=r;j++){
f[a[j]]++;
if (!(f[a[j]]&1))h++;
if ((f[a[j]]&1)&&f[a[j]]!=1)h--;
}
for(j=l;j<=r;j++)f[a[j]]=0;
printf("%d\n",h);
lastans=h;
continue;
}
L++;R--;
h=ans[L][R];
int tot=0;
for(j=l;j<=(L-1)*X;j++)b[++tot]=a[j];
for(j=R*X+1;j<=r;j++)b[++tot]=a[j];
for(j=1;j<=tot;j++){
if (!f[b[j]])f[b[j]]=sum[R][b[j]]-sum[L-1][b[j]]+1;
else f[b[j]]++;
if ((f[b[j]]&1)&&f[b[j]]>1)h--;
else if (!(f[b[j]]&1))h++;
}
for(j=1;j<=tot;j++)f[b[j]]=0;
printf("%d\n",h);
lastans=h;
}
return 0;
}
2020年3月18日 17:47
The struggle of the joyful places done for humans. The nature of the https://bestwritingsclues.com/reviews/paperhelp-com-review/ is visited for the ailment for the field. The box is ensured for all games. The part is played for the individuals. The struggle is done for al opens. the chances vital for the approval of the terms for al goals for urns.
2022年9月11日 16:06
Mathematics is one of the tough subjects and also an easy subject for class 10th standard students of TM, EM, AP 10th Maths Model Paper UM and HM studying at government and private schools of the state. Department of School Education and teaching staff of various institutions have designed and suggested the Mathematics question paper with solutions for all chapters topic wide for each lesson of the course, and the AP SSC Maths Model Paper 2023 Pdf designed based on the new revised syllabus and curriculum.