题解：P3997 [SHOI2013] 扇形面积并
Ybll_
·
·
题解
卡常过了！！！
思路：
有点类似差分哈。
首先我们先把这一个被平均分成 2m 份扇形的圆转换成 2m 棵线段树，但是，空间肯定会超，
所以我们可以每一份单独处理。
先准备一个长度为 2m，类型为 pair<int,int> 的二维动态数组 v，先让扇形的起始位置 a 和结束位置 b 加 m 使它们非负，然后再像下面这样：
v[a+m].push_back({r,1});
v[b+m].push_back({r,-1});
第一行表示从 a+m 的位置开始放入一个半径为 r 的扇形，同时他可以造成价值为 1 的厚度贡献；
第二行表示在 b+m 的位置撤销 a+m 处放入的半径为 r 的扇形的厚度贡献；
但是由于输入的特殊性，可能会出现 a>b 的情况，此时只需在 0 的位置放入一个半径为 r 的扇形即可。
然后我们遍历这 2m 份扇形，对于第 i 个扇形 v_i 中的第 j 个元素的半径 v[i][j].first 和贡献 v[i][j].second，
我们使用线段树进行区间加的操作，加的范围就是 [1,v[i][j].first]，加的贡献就是 v[i][j].second。
然后对于这份扇形，我们去二分找出最后一个大于等于 k 的位置，设这个位置为 R，
那这份扇形的面积的贡献就为：
由于最后要乘上 $\frac{2m}{π}$，化简后即为 $R^2$。
接着，就有以下代码：
```cpp
#include<bits/stdc++.h>
#define int long long
#define up(id) tree[id].sum=tree[id*2].sum+tree[id*2+1].sum
using namespace std;
struct node
{
int l,r,sum,lazy;
}tree[8000005];
int n,m,k,ans;
vector<pair<int,int>>v[2000005];
void build(int id,int l,int r)
{
tree[id].l=l;
tree[id].r=r;
if(l==r)return;
int mid=l+r>>1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
void down(int id)
{
tree[id*2].sum+=(tree[id*2].r-tree[id*2].l+1)*tree[id].lazy;
tree[id*2+1].sum+=(tree[id*2+1].r-tree[id*2+1].l+1)*tree[id].lazy;
tree[id*2].lazy+=tree[id].lazy;
tree[id*2+1].lazy+=tree[id].lazy;
tree[id].lazy=0;
}
void update(int id,int l,int r,int sum)
{
if(tree[id].l>r||tree[id].r<l)return;
if(tree[id].l>=l&&tree[id].r<=r)
{
tree[id].lazy+=sum;
tree[id].sum+=(tree[id].r-tree[id].l+1)*sum;
return;
}
down(id);
update(id*2,l,r,sum);
update(id*2+1,l,r,sum);
up(id);
}
int query(int id,int l,int r)
{
if(tree[id].l>r||tree[id].r<l)return 0;
if(tree[id].l>=l&&tree[id].r<=r)return tree[id].sum;
down(id);
return query(id*2,l,r)+query(id*2+1,l,r);
}
signed main()
{
cin>>n>>m>>k;
build(1,1,2*m);
for(int i=0,r,a,b;i<n;i++)
{
cin>>r>>a>>b;
v[a+m].push_back({r,1});
v[b+m].push_back({r,-1});
if(b<a)v[0].push_back({r,1});
}
for(int i=0;i<2*m;i++)
{
for(auto j:v[i])
{
update(1,1,j.first,j.second);
}
int l=1,r=100000,mid,res=0;
while(l<=r)
{
mid=l+r>>1;
if(query(1,mid,mid)>=k)
{
l=mid+1;
res=mid;
}
else r=mid-1;
}
ans+=res*res;
}
cout<<ans;
return 0;
}
```
但是，你这样写会 TLE 一个点。
为了减少常数，先把一部分 `long long` 类型的数据改为 `int` 类型，再加上**快读快写**，
是的没错，仍然会 TLE，因为**普通线段树常数太大**了。
所以，这边给到一个 **zkw 线段树**，zkw 线段树的**常数、空间**要比普通线段树**少**。
至于 zkw 线段树，请参考[这篇](https://www.luogu.com.cn/article/zyplvygx)文章。
时间复杂度为 $O(m\log_2^2n)$。
# AC 代码：
```cpp
#include<bits/stdc++.h>
#define il inline
#define re register
using namespace std;
il int read()
{
re int x=0,f=1;
char c;
while(!isdigit(c=getchar()))
{
if(c=='-')f=-1;
}
while(isdigit(c))
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
struct node
{
int sum,lazy;
}tree[8000005];
int n=read(),m=read(),k=read(),P=1;
long long ans;
vector<pair<int,int>>v[2000005];
il void update(int l,int r,int v)
{
long long ln=0,rn=0,nn=1;
for(l=P+l-1,r=P+r+1;l^r^1;l/=2,r/=2,nn*=2)
{
tree[l].sum+=v*ln;
tree[r].sum+=v*rn;
if(~l&1)
{
tree[l^1].lazy+=v;
tree[l^1].sum+=v*nn;
ln+=nn;
}
if(r&1)
{
tree[r^1].lazy+=v;
tree[r^1].sum+=v*nn;
rn+=nn;
}
}
for(;l;l/=2,r/=2)
{
tree[l].sum+=v*ln;
tree[r].sum+=v*rn;
}
}
il long long query(int l,int r)
{
long long ln=0,rn=0,nn=1,sum=0;
for(l=P+l-1,r=P+r+1;l^r^1;l/=2,r/=2,nn*=2)
{
if(tree[l].lazy)sum+=tree[l].lazy*ln;
if(tree[r].lazy)sum+=tree[r].lazy*rn;
if(~l&1)
{
sum+=tree[l^1].sum;
ln+=nn;
}
if(r&1)
{
sum+=tree[r^1].sum;
rn+=nn;
}
}
for(;l;l/=2,r/=2)
{
sum+=tree[l].lazy*ln;
sum+=tree[r].lazy*rn;
}
return sum;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(;P<=100001;P*=2);
for(int i=0,r,a,b;i<n;i++)
{
r=read();
a=read();
b=read();
v[a+m].push_back({r,1});
v[b+m].push_back({r,-1});
if(b<a)v[0].push_back({r,1});
}
for(int i=0;i<2*m;i++)
{
int l=1,r=100000,mid;
long long res=0;
for(auto j:v[i])
{
update(1,j.first,j.second);
}
while(l<=r)
{
mid=l+r>>1;
if(query(mid,mid)>=k)
{
l=mid+1;
res=mid;
}
else r=mid-1;
}
ans+=res*res;
}
cout<<ans;
return 0;
}
```