首页 > 代码库 > [BZOJ 2724] [Violet 6] 蒲公英 【分块】
[BZOJ 2724] [Violet 6] 蒲公英 【分块】
题目链接：BZOJ - 2724
题目分析
这道题和 BZOJ-2821 作诗 那道题几乎是一样的，就是直接分块，每块大小 sqrt(n) ，然后将数字按照数值为第一关键字，位置为第二关键字排序，方便之后二分查找某个值在某个区间内出现的次数。
预处理出 f[i][j] 即从第 i 块到第 j 块的答案。
对于每个询问，中间的整块直接用预处理出的，两端的 sqrtn 级别的数暴力做，用二分查找它们出现的次数。
每次询问的复杂度是 sqrtn * logn 。
注意：写代码的时候又出现了给 sort 写的 Cmp() 不保证双向一致的错误！！Warning！注意代码中的 Cmp_Num() 函数，即使在不需要第二关键字的情况下，由于 Num 可能会有相同的，也必须加第二关键字以保证比较结果双向一致！
代码
#include <iostream>#include <cstdlib>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;inline void Read(int &Num) { char c; 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(); }}const int MaxN = 40000 + 5, MaxBlk = 200 + 5;int n, m, BlkSize, TotBlk;int A[MaxN], TL[MaxN], T[MaxN], Cnt[MaxN], L[MaxBlk], R[MaxBlk], First[MaxN], Last[MaxN];int f[MaxBlk][MaxBlk], g[MaxBlk][MaxBlk];struct ES{ int Pos, Num, v;} E[MaxN];inline bool Cmp_Num(ES e1, ES e2) { if (e1.Num == e2.Num) return e1.Pos < e2.Pos; return e1.Num < e2.Num;}inline bool Cmp_Pos(ES e1, ES e2) {return e1.Pos < e2.Pos;}int GetNum(int Num, int x, int y) { if (x > y || x > E[Last[Num]].Pos || y < E[First[Num]].Pos) return 0; int l, r, mid, p1, p2; l = First[Num]; r = Last[Num]; while (l <= r) { mid = (l + r) >> 1; if (E[mid].Pos >= x) { p1 = 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 <= y) { p2 = mid; l = mid + 1; } else r = mid - 1; } return p2 - p1 + 1;}int main() { Read(n); Read(m); for (int i = 1; i <= n; ++i) { Read(E[i].Num); E[i].Pos = i; } sort(E + 1, E + n + 1, Cmp_Num); int v_Index = 0; for (int i = 1; i <= n; ++i) { if (i == 1 || E[i].Num > E[i - 1].Num) ++v_Index; E[i].v = v_Index; TL[v_Index] = E[i].Num; } sort(E + 1, E + n + 1, Cmp_Pos); for (int i = 1; i <= n; ++i) A[i] = E[i].v; sort(E + 1, E + n + 1, Cmp_Num); for (int i = 1; i <= n; ++i) { if (First[E[i].v] == 0) First[E[i].v] = i; Last[E[i].v] = i; } BlkSize = (int)sqrt((double)n); TotBlk = (n - 1) / BlkSize + 1; for (int i = 1; i <= TotBlk; ++i) { L[i] = (i - 1) * BlkSize + 1; R[i] = i * BlkSize; } R[TotBlk] = n; for (int i = 1; i <= TotBlk; ++i) { for (int j = 1; j <= n; ++j) Cnt[j] = 0; f[i][i - 1] = 0; g[i][i - 1] = 0; for (int j = i; j <= TotBlk; ++j) { f[i][j] = f[i][j - 1]; g[i][j] = g[i][j - 1]; for (int k = L[j]; k <= R[j]; ++k) { ++Cnt[A[k]]; if (Cnt[A[k]] > f[i][j] || (Cnt[A[k]] == f[i][j] && A[k] < g[i][j])) { f[i][j] = Cnt[A[k]]; g[i][j] = A[k]; } } } } memset(Cnt, 0, sizeof(Cnt)); for (int i = 1; i <= n; ++i) T[i] = -1; int l, r, x, y, Ct, Ans, Cu; Ans = 0; for (int i = 1; i <= m; ++i) { Read(l); Read(r); l = (l + Ans - 1) % n + 1; r = (r + Ans - 1) % 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) { Ct = 0; Ans = 0; for (int j = l; j <= r; ++j) { ++Cnt[A[j]]; if (Cnt[A[j]] > Ct || (Cnt[A[j]] == Ct && A[j] < Ans)) { Ct = Cnt[A[j]]; Ans = A[j]; } } for (int j = l; j <= r; ++j) --Cnt[A[j]]; } else { Ct = f[x][y]; Ans = g[x][y]; for (int j = l; j < L[x]; ++j) { ++Cnt[A[j]]; if (T[A[j]] == -1) T[A[j]] = GetNum(A[j], L[x], R[y]); Cu = Cnt[A[j]] + T[A[j]]; if (Cu > Ct || (Cu == Ct && A[j] < Ans)) { Ct = Cu; Ans = A[j]; } } for (int j = r; j > R[y]; --j) { ++Cnt[A[j]]; if (T[A[j]] == -1) T[A[j]] = GetNum(A[j], L[x], R[y]); Cu = Cnt[A[j]] + T[A[j]]; if (Cu > Ct || (Cu == Ct && A[j] < Ans)) { Ct = Cu; Ans = A[j]; } } for (int j = l; j < L[x]; ++j) {--Cnt[A[j]]; T[A[j]] = -1;} for (int j = r; j > R[y]; --j) {--Cnt[A[j]]; T[A[j]] = -1;} } Ans = TL[Ans]; printf("%d\n", Ans); } return 0;}
[BZOJ 2724] [Violet 6] 蒲公英 【分块】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。