福建省建设法制协会网站,数据库和网站建设的论文,安徽搜索引擎优化,普通二本软件工程薪水题目链接#xff1a; BZOJ - 3236 BZOJ - 3809 算法一#xff1a;莫队 首先#xff0c;单纯的莫队算法是很好想的#xff0c;就是用普通的第一关键字为 l 所在块#xff0c;第二关键字为 r 的莫队。 这样每次端点移动添加或删除一个数字#xff0c;用树状数组维护所求的…题目链接 BZOJ - 3236 BZOJ - 3809 算法一莫队 首先单纯的莫队算法是很好想的就是用普通的第一关键字为 l 所在块第二关键字为 r 的莫队。 这样每次端点移动添加或删除一个数字用树状数组维护所求的信息就是很容易的。由于这里有 logn复杂度所以这样移动端点的复杂度还是挺高的。 于是 BZOJ-3236 的时限 100s我的代码跑了 98s险过...... Paste一个BZOJ-3236的纯莫队代码 #include iostream
#include cstdlib
#include cstdio
#include cmath
#include algorithm
#include cstringusing 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;
}算法二莫队分块 这是一个神奇的做法还是用莫队转移区间端点但是每次移动端点都是O(1)的不再用树状数组而是将 [1,n] 的数值分成大小为 sqrt(n) 的块。 莫队时加入一个数如果它之前不存在就将它所在的块的数组值加一删除时类似。 然后每个询问转移完区间之后用分块的方法查询答案中间的整块直接查两边的零散的数就暴力枚举这样每个询问就是 sqrt(n) 的。 总复杂度也大约是 O(n^1.5) 主要就是把移动区间端点变为了 O(1)十分神奇 我用这个算法写了 3809代码如下 #include iostream
#include cstdio
#include cstdlib
#include cmath
#include algorithm
#include cstringusing 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, MaxBlk 350 5;int n, m, BlkSize, TotBlk;
int A[MaxN], Cnt[MaxN], T[MaxBlk], L[MaxBlk], R[MaxBlk], Ans[MaxM], Blk[MaxN];struct Query
{int l, r, Index, a, b;Query() {}Query(int f, int x, int y, int p, int q) {Index f; l x; r y; a p; b q;}bool operator (const Query b) const {if (Blk[l] Blk[b.l]) return r b.r;return Blk[l] Blk[b.l];}
} Q[MaxM];inline void Add_Num(int x) {if (Cnt[x] 0) T[Blk[x]];Cnt[x];
}inline void Del_Num(int x) {--Cnt[x];if (Cnt[x] 0) --T[Blk[x]];
}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 GetAns(int a, int b) {int x, y, ret;x Blk[a]; if (L[x] ! a) x;y Blk[b]; if (R[y] ! b) --y;ret 0;if (x y) {for (int i a; i b; i) if (Cnt[i] 0) ret;}else {for (int i x; i y; i) ret T[i];for (int i a; i L[x]; i) if (Cnt[i] 0) ret;for (int i b; i R[y]; --i) if (Cnt[i] 0) ret; }return ret;
}int main()
{Read(n); Read(m);for (int i 1; i n; i) Read(A[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 n; i) Blk[i] (i - 1) / BlkSize 1;int l, r, a, b;for (int i 1; i m; i) {Read(l); Read(r); Read(a); Read(b);Q[i] Query(i, l, r, a, b);}sort(Q 1, Q m 1);memset(Cnt, 0, sizeof(Cnt));memset(T, 0, sizeof(T));for (int i Q[1].l; i Q[1].r; i) Add_Num(A[i]);Ans[Q[1].Index] GetAns(Q[1].a, Q[1].b);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);}Ans[Q[i].Index] GetAns(Q[i].a, Q[i].b);}for (int i 1; i m; i) printf(%d\n, Ans[i]);return 0;
}转载于:https://www.cnblogs.com/JoeFan/p/4246291.html
