萌新刚学oi求助
查看原帖
萌新刚学oi求助
289573
wtxy2006楼主2020/8/16 22:26

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;
}
2020/8/16 22:26
加载中...