扇形面积并

这道题比矩形面积并友好多了。

题意：给定 n 个同心扇形，放置在一个被半径 2m 等分的圆中（圆是假想的），求被扇形覆盖了 k 次以上的关于面积的代数式 $\frac{\pi}{2m}\times ans=S$, 其中 S 为面积，输出 ans;

输入：第一行是三个整数 n，m，k。n 代表同心扇形的个数，m 用来等分 $[-π,π]$的弧度。

从第二行开始的 n 行，每行三个整数 r，a1，a2。描述了一个圆心在原点的扇形，半径为 r，圆心角是从弧度 $πa1/m$到 $πa2/m$，a1 可能大于 a2，逆时针扫过的区域为该扇形面积。

思路：对于每个扇形，将其抽象为前端边和后端边。前端边的权值为 1, 后端边的权值为-1，逆时针转一周，依次将边的权值加入权值线段树中，对于每两条边之间，求面积, 最后, 求面积和即可。时间复杂度 O(nlogn)(比不离散化的 mlogn 优)

数据结构：

typedef struct oprtor       //抽象后的扇形两边
{
    int l,d,sl,sd,c;        //分别为离散化后的边，半径。离散化前的边，半径，权值
}oprt;
typedef struct tnode        //线段树的节点
{
    int l,r,pos,tot;        //节点左端点（离散化后的位置），右端点（离散化后的位置），右端点对应的原位置，节点被覆盖的最多的部分被覆盖的次数
}trnd;

问题一：离散化。离散化是 OI 中极其重要而且常用的手段。本人手上常用的离散化方式为 stl map 离散化。这种方法对于每一类型的数据离散化只需 3 行。

void lsh(pair<int,int> a[100])
{
    map<int,int>mp,md;
    map<int,int>::iterator itr;
    int now;

    for(int i=1;i<=n;i++)mp[a[i].first]=1;
    for(itr=mp.begin(),now=1;itr!=mp.end();itr++,now++)itr->second=now;
    for(int i=1;i<=n;i++)a[i].second=mp[a[i].first];
}

这一段代码可以把 a 离散化，其中 a[i].first 为原数，a[i].second 为离散化后的值。

问题而：线段树。其实本题可以用树状数组，但是我觉得线段树方便一些，于是用了线段树。离散化后，整个圆形被分为了若干个部分。按照弧度从小到大把半径对应的点加上权值。由于扇形是同心的，所以线段树中每个节点保存的值就是当前节点对应的区间中被覆盖最多的部分被覆盖的次数。这样在寻找超过 k 次覆盖的部分时，就可以进行二分查找。

举个例子：

设e(i,j,c)表示每一条边对应的弧度, 半径和权值。如果对于三条边(1,3,1),(2,5,1),(3,3,-1); 那么在加入了第一条边时，线段树的状态就是{0,0,1,0,0,0,…}, 加入第二条边后就是{0,0,1,0,1,0,…}, 接着是{0,0,0,0,1,0,…}。如果我们设find(a,k)表示寻找节点a中最右端被覆盖了至少一次的地方，那么find(a,k)={find(a.lson,k-a.rson.tot)(a.rson.tot$<$k),find(a,rson,k)(a.rson.tot$>$=k)} , 这就有点划分树的意思了。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>

#define MX 800001
#define ls (node*2)
#define rs (node*2+1)
#define mid ((l+r)/2)

using namespace std;

typedef long long ll;
typedef struct oprtor
{
    int l,d,sl,sd,c;
}oprt;
typedef struct tnode
{
    int l,r,pos,tot;
}trnd;

trnd tree[MX];
oprt opr[MX];
int grnd[MX],spos[MX],srad[MX],n,m,k,pnum,dnum;

int cmp(oprt a,oprt b){
    return a.sl<b.sl;
}

void l_add(int lft,int rad,int cnt){
    opr[++n].sl=lft,opr[n].sd=rad,opr[n].c=cnt;
}

void input(){
    int a,b,d,n2;
    scanf("%d%d%d",&n2,&m,&k);
    for(int i=1;i<=n2;i++){
        scanf("%d%d%d",&d,&a,&b);
        if(a<=b)l_add(a,d,1),l_add(b,d,-1);
        else l_add(a,d,1),l_add(m,d,-1),l_add(-m,d,1),l_add(b,d,-1);
    }
}

void lsh(){
    sort(opr+1,opr+n+1,cmp);
    map<int,int>mp,md;
    map<int,int>::iterator itr;
    int now;
    for(int i=1;i<=n;i++)mp[opr[i].sl]=1;
    for(itr=mp.begin(),now=1;itr!=mp.end();itr++,now++)itr->second=now,spos[now]=itr->first;pnum=now-1;
    for(int i=1;i<=n;i++)opr[i].l=mp[opr[i].sl];
    for(int i=1;i<=n;i++)md[opr[i].sd]=1;
    for(itr=md.begin(),now=1;itr!=md.end();itr++,now++)itr->second=now,srad[now]=itr->first;dnum=now-1;
    for(int i=1;i<=n;i++)opr[i].d=md[opr[i].sd];
}

void build(int node,int l,int r){
    tree[node].l=l,tree[node].r=r,tree[node].tot=0;
    tree[node].pos=srad[r];
    if(l!=r)build(ls,l,mid),build(rs,mid+1,r);
    else grnd[l]=node;
}

void add(int pos,int c){
    int node=grnd[pos];
    while(node>0){
        tree[node].tot+=c;
        node/=2;
    }
}

int query(int node,int need){
    int l=tree[node].l,r=tree[node].r;
    if(l==r)return tree[node].pos;
    if(tree[node].tot<need)return 0;
    if(tree[rs].tot>=need)return query(rs,need);
    else return query(ls,need-tree[rs].tot);
}

void work(){
    ll area=0,now;
    build(1,1,dnum);
    opr[0].l=-m;
    for(int i=1;i<=n;i++){
        if(opr[i].l!=opr[i-1].l){
            now=query(1,k);
            area+=now*now*(ll)(spos[opr[i].l]-spos[opr[i-1].l]);
        }
        add(opr[i].d,opr[i].c);
    }
    cout<<area;
}

int main(){
    input();
    lsh();
    work();
    return 0;
}