CF85D Sum of Medians
前言
碼完之後去看題解，程式碼都好短……
終於沒有用快讀啦~
題意
對於一個初始為空的集合，有三種操作：
- add：向集合里加入數 \(x\) ，保證加入前集合中沒有數 \(x\) ；
- del：從集合中刪除數 \(x\) ，保證刪除前集合中有 \(x\) ；
- sum：詢問將集合里的數從小到大排序後，求下標 \(i\) 滿足 \(5\) 余 \(3\) 的數的和。
現有 \(n\) 次操作，對於每個查詢操作，輸出答案。
思路
看到插入、刪除、區間操作而且不考慮序列的順序，首先就想到了平衡樹（splay）。
先來說 splay 中節點包含的資訊：
- \(wei[5]\) ：當前節點排序後的下標對於 \(5\) 取模後為 \(wei\) 的下標，並存入該點的權值。簡單來說， \(wei[j]\) 就是當前節點對於下標 \(i\) 滿足 \(5\) 余 \(j\) 的數的和的單點貢獻。
- \(sum[5]\) ：當前節點排序後，子樹中的 \(wei\) 的和。
- 其他的就是平常的 splay 了，能打懶標記就行。
在向上 update 重塑節點資訊的時候 ：
\(sum_{pos}=sum_{ls} + sum_{rs} + wei_{pos}\)
首先對於 \(1\) 操作，二話不說首先 insert 。
應當考慮當前節點的貢獻 \(wei\) 。貢獻的大小 \(x\) 已知，只需要弄清楚權值對 \(1\) ~ \(5\) 哪一個 \(wei\) 做貢獻的問題了。只需要查詢 \(x\) 前驅的排名加 \(1\) 即可。
再是考慮插入 \(x\) 對於其他點的影響。可以發現，插入 \(x\) 對於大於 \(x\) 的數有影響，會使得這些點的 \(sum[i]\) 和 \(wei[i]\) 變為 \(sum[(i+1)\%5]\) 和 \(wei[(i+1)\%5]\) 。將權值為 \(x\) 的點 splay 到根節點，大於 \(x\) 的數全都在其右子樹中了。然後只用修改右兒子的 \(wei\) 和 \(sum\) ，對於右兒子美美地打上懶標記就行了。
然後是刪除操作，現將他 splay 到根節點，把他的所有有關權值的資訊清空了，避免對於之後的刪除操作造成毀滅性的影響。
可以發現，刪除 \(x\) 對於大於 \(x\) 的數有影響，會使得這些點的 \(sum[i]\) 和 \(wei[i]\) 變為 \(sum[(i-1)\%5]\) 和 \(wei[(i-1)\%5]\) 。接下來的操作就類似於操作1裡面的操作了。
最後，就是最簡單的查詢操作了，直接訪問根節點的資訊就行了。
Code
時間複雜度為 \(O(5n\log n)\) ，最慢的點 \(1372ms\) 。
#include <cstdio>
#define INF 1e15
#define int long long
const int MAXN = 1e5 + 5;
struct Splay_Node {
int fa, cnt, siz, val, tag, son[2], wei[5], sum[5];
#define ls t[pos].son[0]
#define rs t[pos].son[1]
};
struct Splay_Tree {
Splay_Node t[MAXN];
int root, tot, Top, stk[MAXN];
bool Ident(int pos) {
return t[t[pos].fa].son[1] == pos;
}
void New(int val, int fa) {
t[++tot].fa = fa;
t[tot].val = val;
t[tot].cnt = t[tot].siz = 1;
}
void Build() {
New(-INF, 0);
root = tot;
New(INF, root);
t[root].son[1] = tot;
}
void Update(int pos) {
for(int i = 0; i < 5; i++) t[pos].sum[i] = t[ls].sum[i] + t[rs].sum[i] + t[pos].wei[i];
t[pos].siz = t[ls].siz + t[rs].siz + t[pos].cnt;
}
void Connect(int pos, int fa, int how) {
t[pos].fa = fa;
t[fa].son[how] = pos;
}
void Push_Down(int pos) {
if(!t[pos].tag) return;
int tmp[5];
if(ls) {
for(int i = 0; i < 5; i++) tmp[(i + t[pos].tag + 5) % 5] = t[ls].sum[i];
for(int i = 0; i < 5; i++) t[ls].sum[i] = tmp[i];
for(int i = 0; i < 5; i++) tmp[(i + t[pos].tag + 5) % 5] = t[ls].wei[i];
for(int i = 0; i < 5; i++) t[ls].wei[i] = tmp[i];
t[ls].tag = (t[ls].tag + t[pos].tag + 5) % 5;
}
if(rs) {
for(int i = 0; i < 5; i++) tmp[(i + t[pos].tag + 5) % 5] = t[rs].sum[i];
for(int i = 0; i < 5; i++) t[rs].sum[i] = tmp[i];
for(int i = 0; i < 5; i++) tmp[(i + t[pos].tag + 5) % 5] = t[rs].wei[i];
for(int i = 0; i < 5; i++) t[rs].wei[i] = tmp[i];
t[rs].tag = (t[rs].tag + t[pos].tag + 5) % 5;
}
t[pos].tag = 0;
}
void Rotate(int pos) {
int fa = t[pos].fa, grand = t[fa].fa;
int how1 = Ident(pos), how2 = Ident(fa);
Connect(pos, grand, how2);
Connect(t[pos].son[how1 ^ 1], fa, how1);
Connect(fa, pos, how1 ^ 1);
Update(fa);
Update(pos);
}
void Splay(int pos, int to) {
int tmp = pos;
Top = 0;
stk[++Top] = tmp;
while(tmp) stk[++Top] = tmp = t[tmp].fa;
while(Top) Push_Down(stk[Top--]);
for(int fa = t[pos].fa; t[pos].fa != to; Rotate(pos), fa = t[pos].fa)
if(t[fa].fa != to) Ident(pos) == Ident(fa) ? Rotate(fa) : Rotate(pos);
if(!to) root = pos;
}
int Find(int pos, int val) {
if(!pos) return 0;
Push_Down(pos);
if(val == t[pos].val) return pos;
else if(val < t[pos].val) return Find(ls, val);
return Find(rs, val);
}
void Insert(int &pos, int val, int fa) {
if(!pos) {
New(val, fa);
Splay(pos = tot, 0);
return;
}
Push_Down(pos);
if(val == t[pos].val) {
t[pos].cnt++;
Splay(pos, 0);
}
else if(val < t[pos].val) Insert(ls, val, pos);
else Insert(rs, val, pos);
}
void Erase(int val) {
int pos = Find(root, val);
if(!pos) return;
if(t[pos].cnt > 1) {
t[pos].cnt--;
Splay(pos, 0);
return;
}
Splay(pos, 0);
int l = ls, r = rs;
while(t[l].son[1]) l = t[l].son[1];
while(t[r].son[0]) r = t[r].son[0];
Splay(l, 0);
Splay(r, l);
t[r].son[0] = 0;
}
int Query_Rank(int pos, int val) {
if(!pos) return 0;
if(val == t[pos].val) {
int res = t[ls].siz + 1;
Splay(pos, 0);
return res;
}
else if(val < t[pos].val) return Query_Rank(ls, val);
int res = t[ls].siz + t[pos].cnt;
return Query_Rank(rs, val) + res;
}
int Query_Pre(int val) {
int pos, res, newroot;
pos = newroot = root;
while(pos) {
Push_Down(pos);
if(t[pos].val < val) {
res = t[pos].val;
pos = rs;
}
else pos = ls;
}
Splay(newroot, 0);
return res;
}
};
Splay_Tree tree;
int n;
signed main() {
tree.Build();
scanf("%lld", &n);
char opt[3];
for(int i = 1, x; i <= n; i++) {
scanf("%s", opt);
if(opt[0] == 'a') {
scanf("%lld", &x);
tree.Insert(tree.root, x, 0);
int pre = tree.Query_Pre(x);
int pos = tree.Find(tree.root, x);
int prerk = tree.Query_Rank(tree.root, pre);
prerk %= 5;
tree.Splay(pos, 0);
tree.t[pos].wei[prerk] = tree.t[pos].sum[prerk] = x;
int tmp[5];
if(tree.rs) {
for(int i = 0; i < 5; i++) tmp[(i + 1) % 5] = tree.t[tree.rs].sum[i];
for(int i = 0; i < 5; i++) tree.t[tree.rs].sum[i] = tmp[i];
for(int i = 0; i < 5; i++) tmp[(i + 1) % 5] = tree.t[tree.rs].wei[i];
for(int i = 0; i < 5; i++) tree.t[tree.rs].wei[i] = tmp[i];
tree.t[tree.rs].tag += tree.t[pos].tag;
}
tree.t[tree.rs].tag++;
tree.Update(pos);
}
else if(opt[0] == 'd') {
scanf("%lld", &x);
int pos = tree.Find(tree.root, x);
tree.Splay(pos, 0);
int tmp[5];
for(int i = 0; i < 5; i++) tree.t[pos].wei[i] = tree.t[pos].sum[i] = 0;
if(tree.rs) {
for(int i = 0; i < 5; i++) tmp[(i + 4) % 5] = tree.t[tree.rs].sum[i];
for(int i = 0; i < 5; i++) tree.t[tree.rs].sum[i] = tmp[i];
for(int i = 0; i < 5; i++) tmp[(i + 4) % 5] = tree.t[tree.rs].wei[i];
for(int i = 0; i < 5; i++) tree.t[tree.rs].wei[i] = tmp[i];
tree.t[tree.rs].tag += tree.t[pos].tag;
}
tree.t[tree.rs].tag--;
tree.Erase(x);
}
else printf("%lld\n", tree.t[tree.root].sum[3]);
}
return 0;
}