1 条题解
-
0
简单的分块题目
贴一下代码吧,具体思路都不说了,应该都能想到的。
已将调试的时候遇到的问题标注出来。
Code
/* Code by Rosmarinus */ #include<algorithm> #include<iostream> #include<cmath> using namespace std; const int N = 1e5 + 10; const int Max_kuai = 101; const int Max_num = 3 * N; const int t = 1000; // 注意调整分块大小,如果单纯使用 sqrt(n) 的话会 MLE int num[N * 2], num_cnt[N * 2], cnt, n, m, len, sum[Max_kuai][Max_num], a[N]; struct Node { int l, r, k; char opt; }node[N]; int Find(int u) { int l = 1, r = len, mid; while(l <= r) { mid = (l + r) >> 1; if(num[mid] > u) r = mid - 1; else if(num[mid] < u) l = mid + 1; else return num_cnt[mid]; } return -1; } void get_lsh() // 离散化 { sort(num + 1, num + 1 + len); for(int i = 1; i <= len; i ++) { if(num[i] != num[i - 1]) cnt ++; num_cnt[i] = cnt; } // 离散化使用二分而不使用 map 的原因单纯是……我也不知道为什么,害怕爆空间或者时间? // 虽然好像既不会爆时间也不会爆空间…… for(int i = 1; i <= n; i ++) a[i] = Find(a[i]); for(int i = 1; i <= m; i ++) { // 分类讨论处理 if(node[i].opt == 'Q') node[i].k = Find(node[i].k); else node[i].r = Find(node[i].r); } } int kuai(int u) { return (u - 1) / t + 1; } int L(int u) { return (u - 1) * t + 1; } int R(int u) { return u * t; } int main() { scanf("%d %d", &n, &m); for(int i = 1; i <= n; i ++) scanf("%d", &a[i]), num[++ len] = a[i]; for(int i = 1; i <= m; i ++) { scanf(" %c %d %d", &node[i].opt, &node[i].l, &node[i].r); if(node[i].opt == 'Q') scanf("%d", &node[i].k), num[++ len] = node[i].k; else num[++ len] = node[i].r; // 重点,千万不要忘了对这个进行离散化 } get_lsh(); for(int i = 1; i <= n; i ++) sum[kuai(i)][a[i]] ++; for(int i = 1; i <= m; i ++) { int l = node[i].l, r = node[i].r, ans = 0; if(node[i].opt == 'Q') // 标准分块代码 { int k = node[i].k; if(kuai(l) != kuai(r)) { for(int p = l; p <= R(kuai(l)); p ++) ans += (a[p] == k); for(int p = L(kuai(r)); p <= r; p ++) ans += (a[p] == k); for(int p = kuai(l) + 1; p <= kuai(r) - 1; p ++) ans += sum[p][k]; } else for(int p = l; p <= r; p ++) ans += (a[p] == k); printf("%d\n", ans); } else { sum[kuai(l)][a[l]] --; a[l] = r; sum[kuai(l)][a[l]] ++; } } return 0; }
- 1
信息
- ID
- 1412
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 5
- 标签
- 递交数
- 22
- 已通过
- 3
- 上传者