【題目敘述】https://codeforces.com/problemset/problem/1288/E
【解題想法】BIT
【簡譯】
Polycarp經常使用Messenger和朋友聊天。他有 n 個朋友，編號從 1 到n。
【註】一個大小為 n 的排列是，從 1 到 n 的每個整數在該排列中恰好出現一次。比如，n = 5，{1, 2, 3, 4, 5} 或 {3, 5, 1, 4, 2} 都是可能的排列。
因此，Polycarp的聊天列表可以用大小為 n 的排列來表示。 p1 是Polycarp最近交談的朋友，p2是時間第二近交談的朋友，依此類推。
一開始，Polycarp的聊天列表是 {1, 2, 3, … , n}。在他收到 m 條訊息之後，第 j 條訊息來自朋友a_j。這會導致朋友a_j移到第一個位置，並使從第一個位置到「朋友a_j原來位置」之間的每個朋友都平移一個位置。如果朋友a_j原本就在第一個位置，則聊天列表保持不變。
例如，原本的聊天列表 = {4, 1, 5, 3, 2}，
如果Polycarp收到 3 號朋友的訊息，聊天列表變成{3, 4, 1, 5, 2}。
如果Polycarp收到 4 號朋友的訊息，聊天列表變成{4, 1, 5, 3, 2}。(不變)
如果Polycarp收到 2 號朋友的訊息，聊天列表變成{2, 4, 1, 5, 3}。
請考慮每個朋友在開始和接收每條消息後，在聊天列表所處的位置。 Polycarp想知道每個朋友在聊天過程中，在聊天列表中待過的最小和最大位置。
【做法】
- bit[ ]：長度 n + m 的BIT。（n 個朋友，前方預留 m 個空位）
- mn[i], mx[i]：紀錄第 i 個朋友在聊天列表所處的最小和最大位置，初始值為 i。
- pos[i]：BIT的節點編號，紀錄第 i 個朋友目前在聊天列表所處的位置，初始值為 i + m（前方預留 m 個空位）。
#include <iostream>
using namespace std;
const int maxn = 300005;
int n, m, num, bit[maxn*2], mx[maxn], mn[maxn], pos[maxn];
void update(int x, int d){
while (x < maxn*2){
bit[x] += d;
x += x & (-x);
}
}
int query(int x){
int ret = 0;
while (x){
ret += bit[x];
x -= x & (-x);
}
return ret;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++){
mn[i] = i;
mx[i] = i;
pos[i] = i+m;
update(pos[i], 1); //該位置加 1 人
}
for (int i = m; i > 0; i--){ //先進來的訊息，擺在後面
cin >> num;
mx[num] = max(mx[num], query(pos[num]));
mn[num] = 1; //傳訊息的朋友，最小位置變成 1
update(pos[num], -1); //該位置減 1 人
update(i, 1); //新位置加 1 人
pos[num] = i;
}
for (int i = 1; i <= n; i++){
mx[i] = max(mx[i], query(pos[i])); //mx值會受後續訊息影響，需更新
cout << mn[i] << " " << mx[i] << "\n";
}
}