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

Emplace · 2025-03-05 16:45:41 · 题解

题意

将一个圆形分成 2m 个小扇形，在给出 n 个大扇形，第 i 个扇形半径为 r_i。给上方的的扇形逆时针编号为正，下方顺时针编号为负，则大扇形就是覆盖了第 s_i 个小扇形转到到第 t_i 个扇形。求至少被 k 个大扇形覆盖的面积，设答案为 T。则输出 T \times \frac{\pi}{2m}。这里先给一张图。

解题

题意转换

首先，这里先看一下怎么算一个小扇形的覆盖面积。设半径为 r。则面积为 \pi \times r^2 \times \frac{1}{2m} \times \frac{2m}{\pi} = r^2。

我们可以将题目转换为每一个小扇形中，覆盖了这个小扇形的所有大扇形有 cnt 个。则这块小扇形的贡献就是其中半径第 cnt-k+1 大的大扇形在这块小扇形中的面积。也就是说因为需要求至少被 k 个大扇形覆盖的地方的面积，所以每块小扇形有了 k 个大扇形的覆盖之后就从半径最小的大扇形开始算。

思路

显然，每个大扇形都是连续的。那我们用一个树状数组，可以在某个地方把它加上，再在某个地方减去即可。因为要求第 cnt-k+1 大，所以对于每个大扇形，将它在它的半径的位置加或减 1，然后使用树状数组倍增就行。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,m,ans,luozhi;
int c[3000000]; 
vector<int> tree[3000000];
int lowbit(int x){
    return x&(-x);
}
void change(int k,int x){
    for(int i=x;i<=100000;i+=lowbit(i))c[i]+=k;
}
int sum(int id){
    int x=0,k=0,y=0,cnt=0;
    for(int i=21;~i;i--){
        x=k+(1<<i);if(x>100000) continue;
        y=cnt+c[x];
        if(y<id)k=x,cnt=y;
    }
    return k+1;
}
signed main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        int r,s,t;
        cin>>r>>s>>t,s+=m,t+=m;
        if(s<t){
            tree[s].push_back(-r);
            tree[t].push_back(r);
        }
        else{
            tree[m*2].push_back(r);
            tree[s].push_back(-r);
            tree[t].push_back(r);
        }
    }
    for(int i=2*m;i>=1;i--){
        for(int j=0;j<tree[i].size();j++){
            int e=tree[i][j];
            if(e>0)change(1,e),luozhi++;
            else change(-1,-e),luozhi--;
        }
        if(luozhi>=k)ans+=sum(luozhi-k+1)*sum(luozhi-k+1);
    }
    cout<<ans;
}