【BZOJ 4418】 扇形面积并

考虑对于每个分出来的区域算合法的半径长度,答案即所有半径长度的平方和


考虑差分,线段树上二分,复杂度O(NlgN+M)


代码:


#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <memory.h>
#include <iostream>
using namespace std;


int n, m, k;


const int MAXN = 100010;


struct Opt {
  int p,v,s;
  Opt (int a_ = 0,int b_ = 0,int c_ = 0) {v = a_,p = b_,s = c_;}
  bool operator < (const Opt ano) const {
    return p < ano.p;
  }
} opt[MAXN << 2];


int cnt = 0;


struct Node {
  int l,r,sum;
} seg[MAXN << 2];


void Build(int x,int l,int r) {
  seg[x].l = l,seg[x].r = r;
  if (l == r) return ;
  int mid = (l + r) >> 1;
  Build(x << 1,l,mid);
  Build((x << 1) + 1,mid + 1,r);
}


void Modify(int x,int p,int v) {
  if (seg[x].l == seg[x].r) {seg[x].sum += v;return;}
  int mid = (seg[x].l + seg[x].r) >> 1;
  if (p <= mid) Modify(x << 1,p,v);
  else Modify((x << 1) + 1,p,v);
  seg[x].sum = seg[x << 1].sum + seg[(x << 1) + 1].sum;
}


int Query(int x,int k) {
  if (seg[x].sum < k ) return 0;
  if (seg[x].l == seg[x].r) return seg[x].l;
  if (seg[(x << 1) + 1].sum >= k) return Query((x << 1) + 1,k);
  else return Query(x << 1,k - seg[(x << 1) + 1].sum);
}


typedef long long LL;
void Solve() {
  LL ans = 0 ;
  int l = 0,lastans = 0;
  Build(1,1,MAXN - 10);
  for (int i = 0;i < (m << 1);i ++) {
    if (l < cnt && opt[l + 1].p == i) {
      while (l < cnt && opt[l + 1].p == i) l ++,Modify(1,opt[l].v,opt[l].s);
      lastans = Query(1,k);
    }
    ans += 1LL * lastans * lastans;
  }
  cout<<ans<<endl;
}
int main() {
#ifdef YJQ_LOCAL
  freopen(".in","r",stdin);
#endif
  scanf("%d%d%d",&n,&m,&k);
  for (int i = 1;i <= n;i ++) {
    int R ,l ,r;
    scanf("%d%d%d",&R,&l,&r);
    l += m,r += m;
    if (l < r) opt[++cnt] = Opt(R,l,1),opt[++cnt] = Opt(R,r,-1);
    else opt[++cnt] = Opt(R,0,1),opt[++cnt] = Opt(R,r,-1),opt[++cnt] = Opt(R,l,1);
  }
  sort(opt + 1,opt + cnt + 1);
  Solve();
}


评论

© yjq_1999 | Powered by LOFTER