题解：P3997 [SHOI2013] 扇形面积并
CQOIer
·
·
题解
（本 ru 第一篇）算法：树状数组+二分
step1：
将一个圆分成 2 \times m 个小扇形，小扇形面积为 \pi \times r^2 \times \frac{1}{2 \times m} \times \frac{2 \times m}{\pi} = r^2。
step2:
那么就可以把这个圆看成一个数轴，小扇形看成数轴上一个点，输入中的扇形的半径当作被覆盖的点的高。现在要求每个点最高的 x，需要 \ge x 的高的个数大于等于 k。
显而易见，如果得到 高（也就是覆盖它的扇形半径），就能二分求 k。
step3:
我们要怎么得到每个点拥有那些高（也就是覆盖它的扇形半径）？
扇形的 s \leq i（当前点），t \ge i 就可以覆盖。
所以把每个扇形按起点 s 从小到大排序，将点从 -m 到 m （逆时针）枚举。到一个点，把 s = i 的扇形扔进优先队列里，把 t < i 的扇形踢出优先队列里。
注意：s > t 要将扇形分两瓣 [-m,t] 和 [s,m]。
高怎么维护？
用树状数组把扇形的 r 处理就 ok 了，也就是求 \ge r 的扇形个数。
终于可以二分了。
## Code
```cpp
#include<bits/stdc++.h>
#define int long long
#define se second
using namespace std;
const int N=1e5+5;
struct S{int r,s,t;}a[2*N];
int n,nn,m,k,t[N],ans;
void add(int x,int z){while(x) t[x]+=z,x-=x&(-x);}
bool cmp(S x,S y){return x.s<y.s;}
signed main(){
cin>>nn>>m>>k;
for(int i=1;i<=nn;++i){
int r,s,t;cin>>r>>s>>t;a[++n].r=r;
if(s>t) a[n].s=s,a[n].t=m,a[++n].r=r,a[n].s=-m,a[n].t=t;
else a[n].s=s,a[n].t=t;
}
sort(a+1,a+n+1,cmp);
priority_queue<pair<int,int> > q;
for(int i=-m,j=1;i<=m;++i){
while(j<=n&&a[j].s==i) q.push({-a[j].t,j}),add(a[j].r,1),++j;
while(!q.empty()&&-q.top().first<=i) add(a[q.top().se].r,-1),q.pop();
int l=0,r=1e5;
while(l<r){
int m=l+r+1>>1,c=0;
for(int ii=m;ii<N;ii+=ii&(-ii)) c+=t[ii];
if(c>=k) l=m;
else r=m-1;
}
ans+=l*l;
}
cout<<ans;
return 0;
}
```
都还好。