每周五篇博客：（5/5） 我做到了！

https://atcoder.jp/contests/abc242/tasks/abc242_g

這題主要是想給大家提供一份莫隊的板子，很多莫隊題基本上填空就差不多了（

板子

void solve() {int n;std::cin >> n;std::vector<int> a(n + 1);for (int i = 1; i <= n; i++) std::cin >> a[i];int q;std::cin >> q;std::vector<std::array<int, 3>> que(q);for (int i = 0; i < q; i ++) {std::cin >> que[i][0] >> que[i][1];que[i][2] = i;}const int M = 300;std::sort(que.begin(), que.end(), [](std::array<int, 3> a, std::array<int, 3> b) {if (a[0] / M == b[0] / M) return a[1] < b[1];return a[0] / M < b[0] / M;});std::vector<int> ans(q);i64 res = 0;auto add = [&](int i) {};auto del = [&](int i) {};int L = 1, R = 0;for (auto [l, r, id] : que) {if (l == r) {continue;}while (L > l) L --, add(L);while (R < r) R ++, add(R);while (L < l) del(L), L ++;while (R > r) del(R), R --;ans[id] = res;}for (auto i : ans) std::cout << i << '\n';std::cout << '\n';
}

題意

$N$ 人編號 $1,2,\dots ,N$ 連續站立。人 $i$ 穿顏色 $A_i$ 。

回答以下格式的查詢 $Q$ 。

• 給您整數 $l$ 和 $r$ 。考慮到只有一個人 $l,l+1,\dots ,r$ ，最多可以形成幾對穿著相同顏色的人？

思路

事實上這就是莫隊板子題，簡單說一下莫隊

莫隊可以把可離線詢問的題目轉化為一個 $O(n\sqrt{n})$ 時間復雜度

值得注意的是在移動左右端點時，我們應該先擴展區間再縮小區間

具體一點的可以看oiwiki-普通莫隊算法

了解莫隊后，我們只需要在上面的板子進行一些魔改/填空

我們維護一個數組$cn{t}_i$，表示當前莫隊代表的區間的衣服顏色為 $i$ 的衣服數量

定義 $res$ 表示當前莫隊代表的區間的答案

對于增加區間的元素時，如果加上這個元素后，$cn{t}_i$ 變成了偶數，說明我們又湊出來了一對相同的顏色衣服，所以此時 $res\leftarrow res+1$，同時維護 $re{s}_i$

對于增加區間的元素時，如果減去這個元素之前，$cn{t}_i$ 是偶數，說明我們要拆散一對相同的顏色衣服，所以此時 $res\leftarrow res?1$，同時維護 $re{s}_i$

那么這題就解決了，真是一道典典又板板的題目呢

代碼

void solve() {int n;std::cin >> n;std::vector<int> a(n + 1);for (int i = 1; i <= n; i++) std::cin >> a[i];int q;std::cin >> q;std::vector<std::array<int, 3>> que(q);for (int i = 0; i < q; i ++) {std::cin >> que[i][0] >> que[i][1];que[i][2] = i;}const int M = 300;std::sort(que.begin(), que.end(), [](std::array<int, 3> a, std::array<int, 3> b) {if (a[0] / M == b[0] / M) return a[1] < b[1];return a[0] / M < b[0] / M;});std::vector<int> ans(q);std::vector<int> cnt(N);i64 res = 0;auto add = [&](int i) {cnt[a[i]] ++;if (cnt[a[i]] % 2 == 0) res ++;};auto del = [&](int i) {if (cnt[a[i]] % 2 == 0) res --;;cnt[a[i]] --;};int L = 1, R = 0;for (auto [l, r, id] : que) {if (l == r) {continue;}while (L > l) L --, add(L);while (R < r) R ++, add(R);while (L < l) del(L), L ++;while (R > r) del(R), R --;ans[id] = res;}for (auto i : ans) std::cout << i << '\n';std::cout << '\n';
}