题目大意：
给定一个长为n的序列,每次询问一个区间内出现了偶数次的数的个数.强制在线.
题解:
据说这道题正解只用了5MB的内存 QAQ...
反正我是120MB + 卡过去的... 我们可以分块！既然我们要分块,首先我们考虑怎么对块的信息快速合并.
我们发现我们无法快速合并两个单独的块的信息。 因为单次合并的代价一定是\(O(c)\)的 所以我们考虑预处理,设\(ans[i][j]\)表示第\(i\)块到第\(j\)块综合起来统计得到的答案. 对于这个数组的预处理我们直接\(O(n\sqrt{n})\)即可统计. 然后我们就可以快速计算出所有被包含的块的答案。 那么现在考虑块和单点之间的信息合并。我们我们发现这时候进行合并,我们需要知道在被包含的块中每种数字有多少个。
所以我们对所有的块的含有的数字的桶做一个前缀和,\(O(\sqrt{n}c)\)所以我们可以做到查询\(O(m\sqrt(n))\)
#include#include #include #include using namespace std;typedef long long ll;inline void read(int &x){ x=0;char ch;bool flag = false; while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true; while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}const int maxn = 320;const int maxm = 100010;int belong[maxm];int block,a[maxm],ws[maxm],anss[maxn][maxn];int sum[maxn][maxm],sta[maxm],top;int main(){ int n,c,m;read(n);read(c);read(m); block = sqrt(n); for(int i=1;i<=n;++i){ read(a[i]); belong[i] = i/block + 1; } int sz = belong[n]; for(int i=1;i<=sz;++i){ int p = max(1,(i-1)*block); memset(ws,0,sizeof ws); int ans = 0; while(p <= n){ if(ws[a[p]] != 0){ if(ws[a[p]]&1) ++ ans; else -- ans; }++ ws[a[p]]; if(p == n || belong[p] != belong[p+1]){ anss[i][belong[p]] = ans; }++p; } } for(int i=1;i<=sz;++i){ int l = max(1,(i-1)*block); int r = min(n,i*block-1); for(int j=l;j<=r;++j) sum[i][a[j]] ++ ; for(int j=1;j<=c;++j) sum[i][j] += sum[i-1][j]; } int l,r,ans=0; while(m--){ read(l);read(r); top = 0; l = (l + ans) % n + 1; r = (r + ans) % n + 1; if(l > r) swap(l,r); if(belong[l] == belong[r]){ ans = 0; for(int i=l;i<=r;++i) sta[++top] = a[i]; sort(sta+1,sta+top+1); for(int i=1,c=0,x;i<=top;++i){ ++ c; if(sta[i] != sta[i+1] || i == top){ if(c !=0 ){ if((c&1) == 0) ++ ans; }c = 0; } } printf("%d\n",ans); continue; } for(int i=l;belong[i] == belong[l];++i) sta[++top] = a[i]; for(int i=r;belong[i] == belong[r];--i) sta[++top] = a[i]; int bl = belong[l] + 1; int br = belong[r] - 1; ans = anss[bl][br]; if(br < bl) ans = 0; sort(sta+1,sta+top+1); for(int i=1,c=0,x;i<=top;++i){ ++ c; if(sta[i] != sta[i+1] || i == top){ x = sum[br][sta[i]] - sum[bl-1][sta[i]]; if(br < bl) x = 0; if(x == 0 && (c&1) == 0) ++ ans; if(x && (x&1) == 0 && (c&1) == 1) -- ans; if(x && (x&1) == 1 && (c&1) == 1) ++ ans; c = 0; } } printf("%d\n",ans); } return 0;}