思路

它这里给我们了一些扇形，叫我们求大于

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

CPP

#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

大的。

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

文章操作

思路

方法

code

细节

相关推荐

评论

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