首页 > 代码库 > [BZOJ 2821] 作诗(Poetize) 【分块】
[BZOJ 2821] 作诗(Poetize) 【分块】
题目链接：BZOJ - 2821
题目分析
因为强制在线了，所以无法用莫队..可以使用分块来做。
做法是，将 n 个数分成 n/x 个块，每个块大小为 x 。先预处理出 f[i][j] ，表示从第 i 个块到第 j 个块的出现次数为偶数的数的个数。
这个复杂度是 n * (n / x) 的。
然后把数与位置存在结构体里，按照数字第一关键字，位置为第二关键字排序。这样是为了方便之后二分查找 [l, r] 中 Num 出现了几次。
对于每次询问，先把答案加上中间包含的整块的答案。然后对于两边至多 2x 个数，单独处理，二分求出它们在中间整块中出现的次数，以更新答案。
更新的思路大概是：看加上当前这个数后，这个数出现的次数是从odd -> even 还是从 even -> odd ，还是 0 -> 1，然后选择 ++Ans 或是 --Ans 或是什么也不做。
处理询问的复杂度是 n * x * logn 。
分析 x 的最优大小。总复杂度为 (n^2 / x) + (nlogn * x) ，由均值不等式得，当 n^2 / x == nlogn * x 时，总复杂度最小，所以 x 的最优值为 x = sqrt(n / logn) 。
代码
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm> using namespace std; const int MaxN = 100000 + 5, MaxBlk = 1300 + 5; inline void Read(int &num) { char c = getchar(); while (c < ‘0‘ || c > ‘9‘) c = getchar(); num = c - ‘0‘; c = getchar(); while (c >= ‘0‘ && c <= ‘9‘) { num = num * 10 + c - ‘0‘; c = getchar(); }} int n, m, Cset, Ans, BlkSize, LastBlk;int A[MaxN], First[MaxN], Last[MaxN], Cnt[MaxN], f[MaxBlk][MaxBlk], L[MaxBlk], R[MaxBlk]; struct ES{ int Pos, Num; bool operator < (const ES &b) const { if (Num == b.Num) return Pos < b.Pos; return Num < b.Num; }} E[MaxN]; int Get(int s, int t, int Num) { if (s > t || s > E[Last[Num]].Pos || t < E[First[Num]].Pos) return 0; int l, r, mid, pl, pr; l = First[Num]; r = Last[Num]; while (l <= r) { mid = (l + r) >> 1; if (E[mid].Pos >= s) { pl = mid; r = mid - 1; } else l = mid + 1; } l = First[Num]; r = Last[Num]; while (l <= r) { mid = (l + r) >> 1; if (E[mid].Pos <= t) { pr = mid; l = mid + 1; } else r = mid - 1; } return pr - pl + 1;} int main() { //Init Read(n); Read(Cset); Read(m); for (int i = 1; i <= n; ++i) Read(A[i]); BlkSize = (int)sqrt((double)n / log((double)n) * log(2.0)); LastBlk = (n - 1) / BlkSize + 1; for (int i = 1; i <= LastBlk; ++i) { L[i] = (i - 1) * BlkSize + 1; R[i] = i * BlkSize; } R[LastBlk] = n; memset(Cnt, 0, sizeof(Cnt)); for (int i = 1; i <= LastBlk; ++i) { for (int j = 1; j <= Cset; ++j) Cnt[j] = 0; for (int j = i; j <= LastBlk; ++j) { f[i][j] = f[i][j - 1]; for (int k = L[j]; k <= R[j]; ++k) { ++Cnt[A[k]]; if ((Cnt[A[k]] & 1) == 0) ++f[i][j]; else if (Cnt[A[k]] != 1) --f[i][j]; } } } for (int i = 1; i <= n; ++i) { E[i].Pos = i; E[i].Num = A[i]; } sort(E + 1, E + n + 1); for (int i = 1; i <= n; ++i) { if (First[E[i].Num] == 0) First[E[i].Num] = i; Last[E[i].Num] = i; } //The array Cnt[] will be used later. memset(Cnt, 0, sizeof(Cnt)); //Solve queries int l, r, x, y, Lx, Ry, G; Ans = 0; for (int Case = 1; Case <= m; ++Case) { Read(l); Read(r); l = (l + Ans) % n + 1; r = (r + Ans) % n + 1; if (l > r) swap(l, r); x = (l - 1) / BlkSize + 1; if (l != L[x]) ++x; y = (r - 1) / BlkSize + 1; if (r != R[y]) --y; if (x > y) { Ans = 0; for (int i = l; i <= r; ++i) { ++Cnt[A[i]]; if ((Cnt[A[i]] & 1) == 0) ++Ans; else if (Cnt[A[i]] != 1) --Ans; } for (int i = l; i <= r; ++i) --Cnt[A[i]]; } else { Lx = L[x]; Ry = R[y]; Ans = f[x][y]; for (int i = l; i < Lx; ++i) { ++Cnt[A[i]]; G = Get(Lx, Ry, A[i]); if (((Cnt[A[i]] + G) & 1) == 0) ++Ans; else if (Cnt[A[i]] + G != 1) --Ans; } for (int i = r; i > Ry; --i) { ++Cnt[A[i]]; G = Get(Lx, Ry, A[i]); if (((Cnt[A[i]] + G) & 1) == 0) ++Ans; else if (Cnt[A[i]] + G != 1) --Ans; } for (int i = l; i < Lx; ++i) --Cnt[A[i]]; for (int i = r; i > Ry; --i) --Cnt[A[i]]; } printf("%d\n", Ans); } return 0;}
[BZOJ 2821] 作诗(Poetize) 【分块】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。