首页 > 代码库 > [BZOJ 3236] [Ahoi2013] 作业 && [BZOJ 3809] 【莫队 | 分块】
[BZOJ 3236] [Ahoi2013] 作业 && [BZOJ 3809] 【莫队 | 分块】
题目链接： BZOJ - 3236 BZOJ - 3809
算法一：莫队
首先，单纯的莫队算法是很好想的，就是用普通的第一关键字为 l 所在块，第二关键字为 r 的莫队。
这样每次端点移动添加或删除一个数字，用树状数组维护所求的信息就是很容易的。由于这里有 logn复杂度，所以复杂度还是挺高的。
于是 BZOJ-3236 的时限 100s，我的代码跑了 98s，险过......
However..BZOJ-3809 的出题人（SLYZ的神犇）就没有这么善良了！直接内存限制 28MB 就直接把我的莫队卡成 MLE！这是处心积虑卡莫队的恶劣行为！严正抗议！
Paste一个BZOJ-3236的纯莫队代码：
#include <iostream>#include <cstdlib>#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>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 = 100000 + 5, MaxM = 1000000 + 5;int n, m, BlkSize;int A[MaxN], Cnt[MaxN], T1[MaxN], T2[MaxN];struct Query{ int l, r, a, b, Pos, e, Ans1, Ans2; Query() {} Query(int x, int y, int p, int q, int o) { l = x; r = y; a = p; b = q; Pos = o; } bool operator < (const Query &q) const { if (e == q.e) return r < q.r; return e < q.e; }} Q[MaxM];inline bool Cmp(Query q1, Query q2) { return q1.Pos < q2.Pos;}inline void Add1(int x, int Num) { for (int i = x; i <= n; i += i & -i) T1[i] += Num;}inline int Get1(int x) { if (x == 0) return 0; //Notice! int ret = 0; for (int i = x; i; i -= i & -i) ret += T1[i]; return ret;}inline void Add2(int x, int Num) { for (int i = x; i <= n; i += i & -i) T2[i] += Num;}inline int Get2(int x) { if (x == 0) return 0; //Notice! int ret = 0; for (int i = x; i; i -= i & -i) ret += T2[i]; return ret;}inline void Add_Num(int x) { if (Cnt[x] == 0) Add2(x, 1); ++Cnt[x]; Add1(x, 1);}inline void Del_Num(int x) { --Cnt[x]; Add1(x, -1); if (Cnt[x] == 0) Add2(x, -1);}void Pull(int f, int x, int y) { if (x == y) return; if (f == 0) if (x < y) for (int i = x; i < y; ++i) Del_Num(A[i]); else for (int i = x - 1; i >= y; --i) Add_Num(A[i]); else if (x < y) for (int i = x + 1; i <= y; ++i) Add_Num(A[i]); else for (int i = x; i > y; --i) Del_Num(A[i]);}int main() { Read(n); Read(m); BlkSize = (int)sqrt((double)n); for (int i = 1; i <= n; ++i) Read(A[i]); int l, r, a, b; for (int i = 1; i <= m; ++i) { Read(l); Read(r); Read(a); Read(b); Q[i] = Query(l, r, a, b, i); Q[i].e = (l - 1) / BlkSize + 1; } sort(Q + 1, Q + m + 1); memset(Cnt, 0, sizeof(Cnt)); memset(T1, 0, sizeof(T1)); memset(T2, 0, sizeof(T2)); for (int i = Q[1].l; i <= Q[1].r; ++i) Add_Num(A[i]); Q[1].Ans1 = Get1(Q[1].b) - Get1(Q[1].a - 1); Q[1].Ans2 = Get2(Q[1].b) - Get2(Q[1].a - 1); for (int i = 2; i <= m; ++i) { if (Q[i].r < Q[i - 1].l) { Pull(0, Q[i - 1].l, Q[i].l); Pull(1, Q[i - 1].r, Q[i].r); } else { Pull(1, Q[i - 1].r, Q[i].r); Pull(0, Q[i - 1].l, Q[i].l); } Q[i].Ans1 = Get1(Q[i].b) - Get1(Q[i].a - 1); Q[i].Ans2 = Get2(Q[i].b) - Get2(Q[i].a - 1); } sort(Q + 1, Q + m + 1, Cmp); for (int i = 1; i <= m; ++i) printf("%d %d\n", Q[i].Ans1, Q[i].Ans2); return 0;}
算法二：
[BZOJ 3236] [Ahoi2013] 作业 && [BZOJ 3809] 【莫队 | 分块】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。