首页 > 代码库 > [BZOJ 4418][Shoi2013]扇形面积并（树状数组+二分）
[BZOJ 4418][Shoi2013]扇形面积并（树状数组+二分）
Description
给定N个同心的扇形，求有多少面积，被至少K个扇形所覆盖。
Solution
打开发现是计算几何还以为是看错题号了QwQ
其实就是遇到一条开始的边+1，遇到一条结束的边-1，a1>a2的话就再加上一个完整的圆
计算每一部分只需要找到第cnt-k+1大的半径，在树状数组上二分就好了
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#define MAXN 100005using namespace std;typedef long long LL;int n,m,k,tot=0,c[MAXN];int read(){ int x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){ if(c==‘-‘)f=-1;c=getchar(); } while(c>=‘0‘&&c<=‘9‘){ x=x*10+c-‘0‘;c=getchar(); } return x*f;}struct Node{ int r,a,f; Node(int r=0,int a=0,int f=0):r(r),a(a),f(f){} bool operator < (const Node& x) const {return a<x.a;}}data[400005];int lowbit(int x){return x&-x;}void add(int pos,int x){ while(pos<=MAXN) { c[pos]+=x; pos+=lowbit(pos); }}int solve(int sum){ int x=0,now=0; for(int i=(1<<20);i;i>>=1) if(x+i<=MAXN&&now+c[x+i]<sum) now+=c[x+i],x+=i; return x+1;}int main(){ n=read(),m=read(),k=read(); for(int i=1;i<=n;i++) { int r=read(),a1=read(),a2=read(); data[++tot]=Node(r,a1,1); data[++tot]=Node(r,a2,-1); if(a1>a2) { data[++tot]=Node(r,-m,1); data[++tot]=Node(r,m,-1); } } sort(data+1,data+1+tot); LL ans=0;int cnt=0; for(int i=1;i<tot;i++) { add(data[i].r,data[i].f); cnt+=data[i].f; if(cnt-k+1<=0)continue; int t=solve(cnt-k+1); ans+=1LL*t*t*(data[i+1].a-data[i].a); } printf("%lld\n",ans); return 0;}
[BZOJ 4418][Shoi2013]扇形面积并（树状数组+二分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。