RT,真的调不出来了,剩下6个点WA。
// P5816 [CQOI2010]内部白点
#include <cstdio>
#include <algorithm>
#include <iostream>
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define getMid(l, r) ((l + r) >> 1)
#define ll long long
#define MN 200105
using namespace std;
inline ll read() {
ll x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x * f;
}
struct point {
ll x, y;
} a[MN], ps[MN]; // 点集
inline bool cmp(point p1, point p2) { return p1.y == p2.y ? p1.x < p2.x : p1.y < p2.y; }
struct tree {
ll l, r, v, tag;
} trees[MN << 3]; // 线段树
void build(ll o, ll l, ll r) {
trees[o].l = l, trees[o].r = r;
if(l == r) return;
ll mid = getMid(l, r);
build(lson(o), l, mid), build(rson(o), mid + 1, r);
}
inline void pushDown(ll o) {
ll l = trees[o].l, r = trees[o].r, mid = getMid(l, r);
trees[lson(o)].tag += trees[o].tag, trees[lson(o)].v += trees[o].tag * (mid - l + 1);
trees[rson(o)].tag += trees[o].tag, trees[rson(o)].v += trees[o].tag * (r - mid);
trees[o].tag = 0;
}
void addSum(ll o, ll v, ll ql, ll qr) {
ll l = trees[o].l, r = trees[o].r, mid = getMid(l, r);
if(ql <= l && r <= qr) {
// printf("%lld %lld\n", ql, qr);
trees[o].tag += v, trees[o].v += (r - l + 1) * v;
return;
}
pushDown(o);
if(ql <= mid) addSum(lson(o), v, ql, qr);
if(qr > mid) addSum(rson(o), v, ql, qr);
trees[o].v = trees[lson(o)].v + trees[rson(o)].v;
}
void change(ll o, ll q, ll v) {
ll l = trees[o].l, r = trees[o].r, mid = getMid(l, r);
if(l == r && q == l) {
trees[o].v = trees[o].tag = v;
return;
}
pushDown(o);
if(q <= mid) change(lson(o), q, v);
else change(rson(o), q, v);
trees[o].v = trees[lson(o)].v + trees[rson(o)].v;
}
ll query(ll o, ll q) {
ll l = trees[o].l, r = trees[o].r, mid = getMid(l, r);
if(l == r && r == q) {
// printf("%lld %lld %lld\n", o, q, trees[o].v);
return trees[o].v;
}
pushDown(o);
if(q <= mid) return query(lson(o), q);
else return query(rson(o), q);
}
ll n, m[MN], len, cnt = -1, f[MN], ans;
int main() {
ans = n = read();
for(ll i = 1; i <= n; i++) m[++cnt] = a[i].x = read(), m[++cnt] = a[i].y = read();
sort(m, m + cnt), len = unique(m, m + cnt) - m;
for(ll i = 1; i <= n; i++) ps[i] = point{lower_bound(m, m + len, a[i].x) - m + 1, lower_bound(m, m + len, a[i].y) - m + 1};
// for(ll i = 1; i <= n; i++) printf("%lld %lld\n", ps[i].x, ps[i].y);
build(1, 1, len), sort(ps + 1, ps + 1 + n, cmp);
// printf("%lld\n", len);
// ll p;
for(ll h = 1, t = 1; t <= n; h = t) {
while(ps[h].y == ps[t].y) t++;
// 统计答案
for(ll i = h; i < t; i++)
if(f[ps[i].x]) ans += query(1, ps[i].x), change(1, ps[i].x, 0); // printf("i:%lld p:%lld x:%lld y:%lld\n", i, p, ps[i].x, ps[i].y);
else f[ps[i].x] = 1, change(1, ps[i].x, 0);
if(t - h > 1) {
// 增加线段
for(ll i = h + 1; i < t; i++) addSum(1, 1, ps[i - 1].x + 1, ps[i].x - 1); // printf("%lld %lld\n", ps[i - 1].x + 1, ps[i].x - 1);
}
}
printf("%lld", ans);
return 0;
}