2 条题解
-
0
好懂做法
#include <bits/stdc++.h> using namespace std; struct Line { int l, r, id; } t[1000006]; int n, q, a[30005], cnt[1000006], now, ans[1000006], SIZE; bool cmp(Line a, Line b) { if (a.l / SIZE == b.l / SIZE) return a.r < b.r; return a.l < b.l; } //当前问题的答案是 now，每个数出现次数在 cnt[] 中 //把 now 更新为添加了 x 这个数后的答案，并维护 cnt[] 数组 //在某些位置影响答案的问题中会传入 pos，然后实现对 a[pos] 操作 void add(int x) { cnt[x]++; if(cnt[x] == 1) now++; } //把 now 更新为删除了 x 这个数后的答案，并维护 cnt[] 数组 void del(int x) { cnt[x]--; if(cnt[x] == 0) now--; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; SIZE = sqrt(n); for (int i = 1; i <= n; i++) cin >> a[i]; cin >> q; for (int i = 1; i <= q; i++) { cin >> t[i].l >> t[i].r; t[i].id = i; } //对询问排序 sort(t + 1, t + q + 1, cmp); //初始询问：空区间 int L = 1; int R = 0; now = 0; for (int i = 1; i <= q; i++) { //调整[L,R]，到 t[i] 这个询问的区间 //先扩大区间 while (L > t[i].l) { L--; add(a[L]); } while (R < t[i].r) { R++; add(a[R]); } //再缩小区间 while (L < t[i].l) { del(a[L]); L++; } while (R > t[i].r) { del(a[R]); R--; } //记录答案 ans[t[i].id] = now; } for (int i = 1; i <= q; i++) cout << ans[i] << "\n"; return 0; } -
0
33DAI LV 5 (1/1) @ 2023-2-3 9:40:06
优雅做法
#include <bits/stdc++.h> using namespace std; struct Line { int l, r, id; } t[1000006]; int n, q, a[30005], cnt[1000006], now, ans[1000006], SIZE; bool cmp(Line a, Line b) { if (a.l / SIZE == b.l / SIZE) return a.r < b.r; return a.l < b.l; } //多了flag个a[pos] void move(int pos, int flag) { if (flag == 1 && cnt[a[pos]] == 0) now++; if (flag == -1 && cnt[a[pos]] == 1) now--; cnt[a[pos]] += flag; } int main() { scanf("%d", &n); SIZE = sqrt(n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); scanf("%d", &q); for (int i = 1; i <= q; i++) { scanf("%d %d", &t[i].l, &t[i].r); t[i].id = i; } sort(t + 1, t + q + 1, cmp); int L = 1; int R = 0; now = 0; for (int i = 1; i <= q; i++) { //一般更建议做完区间延伸后再做区间缩减 while (L < t[i].l) move(L++, -1); while (L > t[i].l) move(--L, 1); while (R < t[i].r) move(++R, 1); while (R > t[i].r) move(R--, -1); ans[t[i].id] = now; } for (int i = 1; i <= q; i++) printf("%d\n", ans[i]); return 0; }
- 1