【线段树】扇形面积并（P3997）

本文主要是介绍【线段树】扇形面积并（P3997），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

正题

P3997

---

题目大意

给若干扇形，问你叠了至少k次的面积

---

解题思路

把园展开，然后用线段树维护每个点的出现次数

当最大次数大于k，用log的时间查找该点，然后计算结果，因为最多只有2*n次查找，所以不会TLE

---

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define N 100010
using namespace std;
ll n,m,k,ans;
struct node
{ll r,s,t;
}a[N];
bool cmp(node a,node b)
{return a.r>b.r;
}
struct Tree
{#define ls x*2#define rs x*2+1ll mx[N*10<<3],lazy[N*10<<3];void push_up(ll x){mx[x]=max(mx[ls],mx[rs]);return;}void push_down(ll x){if(lazy[x]){lazy[ls]+=lazy[x];lazy[rs]+=lazy[x];mx[ls]+=lazy[x];mx[rs]+=lazy[x];lazy[x]=0;}return;}void get(ll x,ll l,ll r,ll rr){if(l==r){ans+=rr*rr;mx[x]=-1000000000;return;}push_down(x);ll mid=l+r>>1;if(mx[ls]>=k)get(ls,l,mid,rr);if(mx[rs]>=k)get(rs,mid+1,r,rr);push_up(x);return;}void add(ll x,ll L,ll R,ll l,ll r,ll rr){if (L==l&&R==r){lazy[x]++;mx[x]++;if(mx[x]>=k)get(x,L,R,rr);return;}push_down(x);ll mid=L+R>>1;if(r<=mid)add(ls,L,mid,l,r,rr);else if(l>mid)add(rs,mid+1,R,l,r,rr);else add(ls,L,mid,l,mid,rr),add(rs,mid+1,R,mid+1,r,rr);push_up(x);return;}
}T;
int main()
{scanf("%lld%lld%lld",&n,&m,&k);for(ll i=1;i<=n;++i){scanf("%lld%lld%lld",&a[i].r,&a[i].s,&a[i].t);if(a[i].t==-m)a[i].t=m-1;else a[i].t--;if(a[i].s==m)a[i].s=-m;if(a[i].s>=0)a[i].s=m-a[i].s;else a[i].s=m-a[i].s;if(a[i].t>=0)a[i].t=m-a[i].t;else a[i].t=m-a[i].t;swap(a[i].s,a[i].t);n++;n--;}sort(a+1,a+1+n,cmp);for(ll i=1;i<=n;++i){if(a[i].s>a[i].t){T.add(1,1,m*2,a[i].s,m*2,a[i].r);T.add(1,1,m*2,1,a[i].t,a[i].r);}else T.add(1,1,m*2,a[i].s,a[i].t,a[i].r);}printf("%lld",ans);return 0;
}

这篇关于【线段树】扇形面积并（P3997）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---