首页 > 代码库 > 【BZOJ】2453: 维护队列&&【BZOJ】2120: 数颜色 二分+分块 双倍经验
【BZOJ】2453: 维护队列&&【BZOJ】2120: 数颜色 二分+分块 双倍经验
Description
你小时候玩过弹珠吗？
小朋友A有一些弹珠，A喜欢把它们排成队列，从左到右编号为1到N。为了整个队列鲜艳美观，小朋友想知道某一段连续弹珠中，不同颜色的弹珠有多少。当然，A有时候会依据个人喜好，替换队列中某个弹珠的颜色。但是A还没有学过编程，且觉得头脑风暴太浪费脑力了，所以向你来寻求帮助。
Input
输入文件第一行包含两个整数N和M。
第二行N个整数，表示初始队列中弹珠的颜色。
接下来M行，每行的形式为“Q L R”或“R x c”，“Q L R”表示A想知道从队列第L个弹珠到第R个弹珠中，一共有多少不同颜色的弹珠，“R x c”表示A把x位置上的弹珠换成了c颜色。
Output
对于每个Q操作，输出一行表示询问结果。
Sample Input
2 3
1 2
Q 1 2
R 1 2
Q 1 2
Sample Output
2
1
1
HINT
对于100%的数据，有1 ≤ N ≤ 10000, 1 ≤ M ≤ 10000，小朋友A不会修改超过1000次，所有颜色均用1到10^6的整数表示。
题解：
这个跟教主的魔法差不多，问题转化过程贴hzwer
http://hzwer.com/2793.html
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;const int MAXN = 1000001;int pos[MAXN], a[MAXN], b[MAXN], add[MAXN];int last[MAXN], pre[MAXN];int n, m ,block;void reset(int x){ int i; int l = (x-1) * block + 1; int r = x * block; if (r > n) r = n; for (i = l; i <= r; i++) { pre[i] = b[i]; } sort(pre + l, pre + r + 1);}int find(int x, int tar){ int l = (x - 1)*block + 1; int r = x*block; if (r > n) r = n; int mid, ret=l; while (l <= r) { mid = (l + r) >> 1; if (pre[mid] >= tar) r = mid-1; else l = mid + 1; } return l-ret;}void Modify(int x, int tar){ int i, temp; for (i = 1; i <= n; i++) last[a[i]] = 0; a[x] = tar; for (i = 1; i <= n; i++) { temp = b[i]; b[i] = last[a[i]]; if (temp != b[i]) reset(pos[i]); last[a[i]] = i; }}int Query(int L, int R){ int d = 0, i; if (pos[L] == pos[R]) { for (i = L; i <= R; i++) { if (b[i]<L) d++; } } else { for (i = L; i <= pos[L] * block; i++) if (b[i]<L) d++; for (i = (pos[R]-1) * block + 1; i <= R; i++) if (b[i]<L) d++; } for (i = pos[L] + 1; i < pos[R]; i++) d += find(i, L); return d;}int main(int argc, char *argv[]){ int i, j, x, y, z, T; char op; scanf("%d%d", &n, &T); block = int(sqrt(n) + log(2 * n) / log(2)); //block = (int)sqrt(n); for (i = 1; i <= n; i++) { scanf("%d", &a[i]); b[i] = last[a[i]]; last[a[i]] = i; pos[i] = (i - 1) / block + 1; } if (n%block) m = n / block + 1; else m = n / block; for (i = 1; i <= m; i++) reset(i); while (T--) { scanf("\n%c%d%d", &op, &x, &y); if (op == ‘R‘) Modify(x, y); else printf("%d\n", Query(x, y)); } return 0;}
【BZOJ】2453: 维护队列&&【BZOJ】2120: 数颜色 二分+分块 双倍经验
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。