（火神：爺究竟交了些什么冤種……）
原題目鏈接：link
「我的做題歷程」：
step1：觀察題面，
??「他的好朋友風神給他一個有 N 個自然數的陣列，然后對他進行 Q 次查詢，每一次查詢包含兩個正整數 \(L,R\)，表示一個陣列中的一個區間 \([L,R]\)，火神需要回答在這個區間中有多少個值剛好出現 \(2\) 次」，對于這種單點修改區間查詢（但此處是對區間元素種類總數的查詢），自然是想到樹狀陣列，當然也有可能是莫隊，（對于目前所學而言，題型：樹狀陣列）
step2：思考解法，
??先從最簡單的想起，假如陣列元素全部相同的話（默認列舉指標為 \(i\)），
??（就像醬紫↓）
??隨著區域左指標不變，右指標從左往右遍歷，我們應該如何去維護呢，
??當區域為 \([1,1]\) 時，沒有值剛好出現 \(2\) 次的元素，恰好，我們什么都不需要操作，
??當區域為 \([1,2]\) 時，\(i\) 號元素 \(3\) 與 \(i - 1\) 號元素相同，\(i - 1\) 號元素的位置上加一（表示該位與該位的后一個數相同），在這一個區間里，\(3\) 剛好出現 \(2\) 次，所以區域 \([1,2]\) 的價值為 \(1\) ，維護成功，
??當區域為 \([1,3]\) 時，\(i\) 號元素 \(3\) 與 \(i - 1\) 號元素相同，\(i - 1\) 號元素的位置上加一，在這一個區間里，\(3\) 出現 \(3\) 次，沒有剛好出現兩次的值，所以區域 \([1,3]\) 的價值應該為 \(0\)，但此時卻是 \(2\)，
??于是，我們在當前 \(i - 2\) 號元素的位置上減 \(2\)（表示該元素后面還有兩個相鄰元素與它相同，\(3\) 個連續元素相同，其價值為零），此時區域 \([1,3]\) 的價值為 \(0\)，維護成功，
??當區域為 \([1,4]\) 時，\(i\) 號元素 \(3\) 與 \(i - 1\) 號元素相同，\(i - 1\) 號元素的位置上加一，在這一個區間里，\(3\) 出現 \(4\) 次，沒有剛好出現兩次的值，所以區域 \([1,4]\) 的價值應該為 \(0\)，但此時卻是 \(-1\)，
??于是，我們在當前 \(i - 3\) 號元素的位置上加 \(1\)（表示該元素后面有三個連續元素與它相同，加一來維護平衡，\(4\) 個連續元素相同，其價值仍為零），此時區域 \([1,4]\) 的價值為 \(0\)，維護成功，
??當區域為 \([1,5]\) 時，\(i\) 號元素 \(3\) 與 \(i - 1\) 號元素相同，\(i - 1\) 號元素的位置上加一，在 \(i - 2\) 號元素的位置上減 \(2\)，在 \(i - 3\) 號元素的位置上加 \(1\)，可以發現，此時我們維護成功了，以此類推，后面所有操作都是平衡的，（藍色的加一表示：該位與后一位數相同； 綠色的減二表示：該元素后面還有兩個相鄰元素與它相同，減去多算的兩對；紫色的加一表示：該元素后面有三個連續元素與它相同，補上多去的一對）
??看完后你可能會發出疑問，你是不是「dou」得呀？？？欸，還真不是，
??我們在計算的時候總是在 \(i - 1\) 號位上加一，是為了記錄當前有多少對滿足題意的元素（在圖中等價于記錄當前位置的左括號有多少，其前綴和即當前區間 \([1,i]\) 滿足題意的元素對數），但是遇到上圖這種情況，（連續三個元素相等，出現兩對相同元素）我們需要舍棄這兩對，于是乎在 \(i - 2\) 號位上減二，你可能又會問，那為啥不在 \(i - 1\) 號位上減呢？那如果在 \(i - 1\) 號位上減的話，區間 \([i - 1, i]\) 你又打算怎么算呢，
??遇到這種情況時，我們的操作是在\(i - 1\) 號元素的位置上加一，在 \(i - 2\) 號元素的位置上減 \(2\)，在 \(i - 3\) 號元素的位置上加 \(1\)，前面兩個操作已解釋過，不再贅述，如圖（四個相同元素同框），我們按前兩個操作記錄了滿足題意的對數，舍棄不符合題意的，這時候，我們會發現——我們實際舍棄了四對（\(i - 2\) 號減二，\(i - 3\) 號減二），實際只需舍棄三對，于是乎，在 \(i - 3\) 號位上加一，表示我多舍棄了一對，現補上（如果你要問為什么不在其他位加一，我只能告訴你是為了后面方便求答案，道理同前），
??前面光是講全是相同元素的情況了，可實際的資料不一定是這樣啊 （疑似偽證)，別急，我們將這種觀念放進資料，思考：是否可以將原資料改造成我們想要的樣子呢？
??（搞笑哦）
??確實可以，我們可以將相同的元素分別穿在同一條鏈上，分別計算，明顯的，我們這樣互不干擾的計算沒有問題，只需同類與同類進行比較，將答案累加即可（在實作中，累加等價于直接在同一個樹狀陣列中），
??特別的，我們需要邊維護邊出答案，如果維護完了再出答案的話，部分靠前的元素會記錄到一些該區間本沒有的資訊，譬如 \(3\ 3\ 3\ 3\ 3\ 3\ 3\ 3\)，若是維護完后再求區間 \([1,3]\) 的話，\(2\) 號位會記錄到資訊：「該元素后面還有兩個相鄰元素與它相同」，但實際該區間內并不存在這種情況，
step3：完成代碼，
代碼（抵制學術不端行為，拒絕 Ctrl + C）：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
int n, q, l, r, BIT[N], last[N], ans[N];
ll a[N];
map<ll, int> mp;
struct node {
int l, r, id;
} b[N];
bool cmp(node x, node y) { return x.r < y.r; }
int lowbit(int x) { return x & -x; }
void update(int x, int k) {
for (int i = x; i <= n; i += lowbit(i)) {
BIT[i] += k;
}
return;
}
int sum(int x) {
int ans = 0;
for (int i = x; i >= 1; i -= lowbit(i)) {
ans += BIT[i];
}
return ans;
}
int main() {
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%lld", a + i);
if (mp.find(a[i]) != mp.end()) {
last[i] = mp[a[i]];
} else {
last[i] = -1;
}
mp[a[i]] = i;
}
for (int i = 1; i <= q; i++) {
scanf("%d %d", &b[i].l, &b[i].r);
b[i].id = i;
}
sort(b + 1, b + q + 1, cmp);
int now = 1;
for (int i = 1; i <= q; i++) {
while (now <= b[i].r) {
if (last[now] != -1) {
update(last[now], 1);
if (last[last[now]] != -1) {
update(last[last[now]], -2);
if (last[last[last[now]]] != -1) {
update(last[last[last[now]]], 1);
}
}
}
now++;
}
ans[b[i].id] = sum(b[i].r) - sum(b[i].l - 1);
}
for (int i = 1; i <= q; i++) {
printf("%d\n", ans[i]);
}
return 0;
}
赫菲斯托斯：阿涅彌伊你完犢子了！！1（ 風神留下了 Accepted 揚長而去）
讓我們來解決 『火神之友』 叭~
Bye bye!!1 ????
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/499882.html
標籤：其他