题解：P3997 [SHOI2013] 扇形面积并

· · 题解

思路

它这里给我们了一些扇形，叫我们求大于 k 层的面积（实际上是 \frac{\pi(a_1-a_2+1)r^2}{2m}\times\frac{2m}{\pi}），我们把它给的这坨东西化简一下就是 (a_1-a_2+1)\times r^2，现在式子化简好了，我们来考虑一下比较难处理的圆圈这个问题，大家都知道，一般一个问题在圆圈上一般都是很难处理的，但是这里我们可以算出每一个格子的值再加起来，所以可以把他当作一个直线来处理，具体怎么处理我们在来看 (不知道怎么用数组存储看下图)。

方法

我们可以考虑一下扫描线，我们把每个扇形的 a_1 当作入边存储，把 a_2 当作出边存储，当我们遍历到入边时就在你所用的数据结构中加一，表示这个扇形在这时存在；当我们遍历到出边时就在你所用的数据结构中减一，表示这个扇形现在不在了。在每一个格子时，我们要找到所拥有扇形中的第 k 大，找这个数有很多种方法，我最倾向于用树状数组加倍增，关于树状数组加倍增，先看代码吧。

code

#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define low (x&(-x))
ll const N=2e6+5;
ll n,m,k,tree[N],a,b,r,t,ans,pp;
vector<ll> p[N];
void update(ll x,ll d){while(x<=2e6+4)tree[x]+=d,x+=low;return;}
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){//输入并把圆圈化为直线数组
        cin>>r>>a>>b;
        if(a>b) p[0].push_back(r);
        p[a+m].push_back(r);
        p[b+m].push_back(-r);
    }
    for(int i=0;i<2*m;i++){
        for(int j=0;j<p[i].size();j++) update(abs(p[i][j]),p[i][j]/abs(p[i][j])),pp+=p[i][j]/abs(p[i][j]);
        ll u=0,s=0;
        if(pp>=k){//树状数组加倍增主要代码
            for(int l=21;l>=0;l--)
                if(u+(1<<l)<N&&s+tree[u+(1<<l)]<pp-k+1) s+=tree[u+=(1<<l)];             
            ans+=(u+1)*(u+1);           
        }   
    }
    cout<<ans<<endl;
    return 0;
}

细节

但相信大家对一些细节还有疑问，比如说如果 a_1 大于 a_2 怎么办，在这个时候，我们不能单纯交换他们，我们要在第一个位置再放一条边，这样子就把这个扇形分成了两个部分，在后面就不用另外考虑了。还有为什么我们要把把倍增 s 的边界设为 pp-k+1，这很简单，就是因为我们要求的并不是第 k 小的而是第 k 大的。