题目描述
神犇SJY虐完HEOI之后给傻×LYD出了一题&＃xff1a;
SHY是T国的公主&＃xff0c;平时的一大爱好是作诗。
由于时间紧迫&＃xff0c;SHY作完诗之后还要虐OI&＃xff0c;于是SHY找来一篇长度为N的文章&＃xff0c;阅读M次&＃xff0c;每次只阅读其中连续的一段[l,r]&＃xff0c;从这一段中选出一些汉字构成诗。因为SHY喜欢对偶&＃xff0c;所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认为选出的汉字的种类数&＃xff08;两个一样的汉字称为同一种&＃xff09;越多越好&＃xff08;为了拿到更多的素材&＃xff01;&＃xff09;。于是SHY请LYD安排选法。
LYD这种傻×当然不会了&＃xff0c;于是向你请教……
问题简述&＃xff1a;N个数&＃xff0c;M组询问&＃xff0c;每次问[l,r]中有多少个数出现正偶数次。
输入输出格式
输入格式&＃xff1a;
输入第一行三个整数n、c以及m。表示文章字数、汉字的种类数、要选择M次。
第二行有n个整数&＃xff0c;每个数Ai在[1, c]间&＃xff0c;代表一个编码为Ai的汉字。
接下来m行每行两个整数l和r&＃xff0c;设上一个询问的答案为ans(第一个询问时ans&＃61;0)&＃xff0c;令L&＃61;(l&＃43;ans)mod n&＃43;1, R&＃61;(r&＃43;ans)mod n&＃43;1&＃xff0c;若L>R&＃xff0c;交换L和R&＃xff0c;则本次询问为[L,R]。
输出格式&＃xff1a;
输出共m行&＃xff0c;每行一个整数&＃xff0c;第i个数表示SHY第i次能选出的汉字的最多种类数。
输入输出样例
5 3 5
1 2 2 3 1
0 4
1 2
2 2
2 3
3 5
2
0
0
0
1
说明
对于100%的数据&＃xff0c;1<&＃61;n,c,m<&＃61;10^5
题解
1.我们考虑一下分块的话要每一块都保存是正偶数的数字的个数&＃xff0c;用一个ans[i][j]保存第i块到第j块内符合条件的数字的个数&＃xff0c;o(1)的查询&＃xff0c;前缀和的思想
2.在最左端的最右端的用一个统计数组暴力即可
3.但是要记住最左端和最右端的数字要与整个[l,r]区间相关联&＃xff0c;所以用一个sum[i][j]保存第[i]块第[j]种颜色的数量
4.luogu上记得开02....
// luogu-judger-enable-o2
#include
#include
#include
#include
#include
using namespace std;
const int N&＃61;100001;
int ch[N],bl[N],cnt[N],ans[330][330],sum[330][N];
int l[N],r[N],n,m,c,last,tmp,res;
int read()
{int x&＃61;0,w&＃61;1;char ch&＃61;getchar();while(ch>&＃39;9&＃39;||ch<&＃39;0&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)w&＃61;-1;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;)x&＃61;x*10&＃43;ch-&＃39;0&＃39;,ch&＃61;getchar();return x*w;
}/*int prep(int x)
{return (x&＃43;last)%n&＃43;1;
}*/void build()
{for(int i&＃61;1;i<&＃61;tmp;i&＃43;&＃43;)l[i]&＃61;(i-1)*tmp&＃43;1,r[i]&＃61;tmp*i;r[tmp]&＃61;n;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){bl[i]&＃61;(i-1)/(tmp)&＃43;1;sum[bl[i]][ch[i]]&＃43;&＃43;;}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)for(int j&＃61;1;j<&＃61;tmp;j&＃43;&＃43;){sum[j][i]&＃43;&＃61;sum[j-1][i];}for(int i&＃61;1;i<&＃61;tmp;i&＃43;&＃43;){int now&＃61;0;for(int j&＃61;l[i];j<&＃61;n;j&＃43;&＃43;){&＃43;&＃43;cnt[ch[j]];if (!(cnt[ch[j]] & 1)) &＃43;&＃43;now;else if (cnt[ch[j]] > 2) --now;ans[i][bl[j]]&＃61;now;}for(int j&＃61;l[i];j<&＃61;n;j&＃43;&＃43;)--cnt[ch[j]];}
}int query(int x,int y)
{ x&＃61;(x&＃43;res)%n&＃43;1;y&＃61;(y&＃43;res)%n&＃43;1;if(x>y)swap(x,y);res&＃61;0;if(bl[y]<&＃61;bl[x]&＃43;1){for(int i&＃61;x;i<&＃61;y;i&＃43;&＃43;){&＃43;&＃43;cnt[ch[i]];if(!(cnt[ch[i]]&1))res&＃43;&＃43;;else if(cnt[ch[i]]>2)res--;}for(int i&＃61;x;i<&＃61;y;i&＃43;&＃43;)--cnt[ch[i]];return last&＃61;res;}res&＃61;ans[bl[x]&＃43;1][bl[y]-1];for(int i&＃61;x;i<&＃61;r[bl[x]];i&＃43;&＃43;){&＃43;&＃43;cnt[ch[i]];if(!((cnt[ch[i]]&＃43;sum[bl[y]-1][ch[i]]-sum[bl[x]][ch[i]])&1))&＃43;&＃43;res;else if(cnt[ch[i]]&＃43;sum[bl[y]-1][ch[i]]-sum[bl[x]][ch[i]]>2)--res;}for (int i&＃61;l[bl[y]];i<&＃61;y;&＃43;&＃43;i){&＃43;&＃43;cnt[ch[i]];if(!((cnt[ch[i]]&＃43;sum[bl[y]-1][ch[i]]-sum[bl[x]][ch[i]])&1))&＃43;&＃43;res;else if(cnt[ch[i]]&＃43;sum[bl[y]-1][ch[i]]-sum[bl[x]][ch[i]]>2)--res;}for(int i&＃61;x;i<&＃61;r[bl[x]];i&＃43;&＃43;)--cnt[ch[i]];for(int i&＃61;l[bl[y]];i<&＃61;y;i&＃43;&＃43;)--cnt[ch[i]];return last&＃61;res;
}int main()
{n&＃61;read();c&＃61;read();m&＃61;read();tmp&＃61;sqrt(n);tmp&＃43;&＃43;;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)ch[i]&＃61;read();build();while(m--){int x&＃61;read(),y&＃61;read();printf("%d\n",query(x,y));}return 0;
}
京公网安备 11010802041100号