首先发现答案与顺序无关,令 $ x_i $ 表示高度为 $ i $ 的那一行帆的个数,第 $ i $ 行对答案的贡献为 $ \frac{x_i * (x_i - 1)}{2} $
先把旗杆按照高度从小到大排序,有一个显然的贪心是每次选择能放的地方帆最少的一行放一个帆,最少的一行放一个帆对答案的贡献一定最小,而后面的旗杆高度更高,能选择放帆的地方更多,这样可以保证答案最小(可以感性理解一下
那么我们的做法就出来了,对于旗杆 $ i $ 选择当前能放帆的最少的 $ k_i $ 行,放上帆,这个操作用平衡树实现,将原序列前 $ k $ 小拿出,加上 $ 1 $ 后放回去,这个时候可能会使平衡树的性质被打破,如 $ 0 $ $ 0 $ 将第一个数加 $ 1 $ 再放回去就变成了 $ 1 $ $ 0 $,所以对于分裂出来的前 $ k $ 小中的最大值还要再次分裂,如 $ 0 $ $ 1 $ $ 1 $ $ 1 $ $ 2 $ 前 $ 3 $ 小要加 $ 1 $,先分裂成 $ 0 $ $ 1 $ $ 1 $ 和 $ 1 $ $ 2 $,然后分裂成 $ 0 $ ,$ 1 $ $ 1 $ 和 $ 1 $ $ 2 $,区间加后放回原序列,先变成 $ 1 $ {这里放原来的 $ 1 $ $ 1 $ } $ 2 $,然后变成 {这里放原来的 $ 0 $} $ 1 $ {这里放原来的 $ 1 $ $ 1 $ } $ 2 $,即 $ 0 $ $ 1 $ $ 1 $ $ 1 $ $ 2 $,可以使用 splay 实现
#include#define Fast_cin ios::sync_with_stdio(false), cin.tie(0);#define rep(i, a, b) for(register int i = a; i <= b; i++)#define per(i, a, b) for(register int i = a; i >= b; i--)#define DEBUG(x) cerr << "DEBUG" << x << " >>> " << endl;using namespace std;typedef unsigned long long ull;typedef pair pii;typedef long long ll;template inline void read(_T &f) { f = 0; _T fu = 1; char c = getchar(); while(c < '0' || c > '9') { if(c == '-') fu = -1; c = getchar(); } while(c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); } f *= fu;}template void print(T x) { if(x < 0) putchar('-'), x = -x; if(x < 10) putchar(x + 48); else print(x / 10), putchar(x % 10 + 48);}template void print(T x, char t) { print(x); putchar(t);}template struct hash_map_t { vector v, val, nxt; vector head; int mod, tot, lastv; T lastans; bool have_ans; hash_map_t (int md = 0) { head.clear(); v.clear(); val.clear(); nxt.clear(); tot = 0; mod = md; nxt.resize(1); v.resize(1); val.resize(1); head.resize(mod); have_ans = 0; } bool count(int x) { int u = x % mod; for(register int i = head[u]; i; i = nxt[i]) { if(v[i] == x) { have_ans = 1; lastv = x; lastans = val[i]; return 1; } } return 0; } void ins(int x, int y) { int u = x % mod; nxt.push_back(head[u]); head[u] = ++tot; v.push_back(x); val.push_back(y); } int qry(int x) { if(have_ans && lastv == x) return lastans; count(x); return lastans; }};const int N = 1e5 + 5;struct ele { int h, gs; bool operator < (const ele A) const { return h < A.h; }} a[N];int ch[N][2], val[N], tag[N], siz[N], n, root;inline void update(int u) { siz[u] = siz[ch[u][0]] + siz[ch[u][1]] + 1; }inline void add_tag(int u, int x) { if(u <= 100000) val[u] += x; tag[u] += x; }inline void pushdown(int u) { if(tag[u]) { if(ch[u][0]) add_tag(ch[u][0], tag[u]); if(ch[u][1]) add_tag(ch[u][1], tag[u]); tag[u] = 0; }}inline void rotate(int &u, int d) { int tmp = ch[u][d]; ch[u][d] = ch[tmp][d ^ 1]; ch[tmp][d ^ 1] = u; update(u); update(tmp); u = tmp;}void splay(int &u, int k) { pushdown(u); int ltree = siz[ch[u][0]]; if(ltree + 1 == k) return; int d = k > ltree; pushdown(ch[u][d]); int k2 = d ? k - ltree - 1 : k; int ltree2 = siz[ch[ch[u][d]][0]]; if(ltree2 + 1 != k2) { int d2 = k2 > ltree2; splay(ch[ch[u][d]][d2], d2 ? k2 - ltree2 - 1 : k2); if(d == d2) rotate(u, d); else rotate(ch[u][d], d2); } rotate(u, d);}int find(int u, int x) { pushdown(u); if(!u) return 0; if(x > val[u]) return siz[ch[u][0]] + 1 + find(ch[u][1], x); return find(ch[u][0], x);}void insert(int &u, int x, int y) { splay(u, x + 1); splay(ch[u][0], x); ch[ch[u][0]][1] = y; update(ch[u][0]); update(u);}ll ans;void dfs(int u) { if(!u) return; pushdown(u); dfs(ch[u][0]); if(u <= 100000) ans += 1ll * val[u] * (val[u] - 1) / 2; dfs(ch[u][1]);}int main() { read(n); for(register int i = 1; i <= n; i++) read(a[i].h), read(a[i].gs); sort(a + 1, a + n + 1); int now = 1; root = 1; ch[root][0] = 100001; ch[root][1] = 100002; val[100001] = -1; val[100002] = 100002; update(100001); update(100002); update(root); for(register int i = 1; i <= n; i++) { while(now < a[i].h) { ++now; update(now); insert(root, 1, now); } splay(root, a[i].gs + 2); splay(ch[root][0], a[i].gs + 1); int left = find(ch[root][0], val[ch[root][0]]), v = val[ch[root][0]], l = ch[root][0]; ch[root][0] = 0; update(root); int right = find(root, v + 1); if(!right) { add_tag(l, 1); ch[root][0] = l; update(root); } else { // fprintf(stderr, "left = %d\n", left); splay(l, left + 1); int ll = ch[l][0]; ch[l][0] = 0; update(l); add_tag(ll, 1); add_tag(l, 1); insert(root, right, l); splay(root, 1); ch[root][0] = ll; update(root); } } dfs(root); cout << ans << endl; return 0;}