题解 P3997 【[SHOI2013]扇形面积并】
zhengrunzhe · · 题解
平衡树+扫描线
用平衡树维护kth
一个角度上覆盖k次所能取到的最大半径便是该角度上覆盖的所有半径中的第k大
比如角度2上覆盖着半径为1926,817,666的扇形，则当k=2时，角度2最大能取到817
维护第k大，想到平衡树
扇形转线段
把每个扇形看作2/4条线段，每条线段的长度是它的半径
用三元组(len,pos,tag)表示一条线段，len就是线段的长度也就是它所对应的扇形的半径，pos表示该线段所处的角度,tag=0表示该线段要被插入，tag=1表示要从平衡树中删除一条长度为len的线段
把len当作平衡树的排序原则，把pos作为线段排序的原则，把所有的线段存下来后，按照极坐标角度从小到大排序
负角度转正
那么有负角度，转成正角度更好做，如图所示是当m=8时的极坐标系
0同时又可以是2m，一个角度p(p<0)，转成正后便是2m+p，比如p=-3，对应m=8时2*8-3=13
考虑怎么把扇形分解成线段
对于一个以len为半径，从角度l覆盖到r的扇形，题目并没有保证l<r，所以要进行一波分类讨论
1.l==r (好像数据没有这种情况)
这种情况便是一个圆，转为(len,0,0)和(len,2m,1)即可，表示一个圆
2.l<r，且l≠0,r≠0
1)l>0,r>0
直接转为(len,l,0),(len,r,1)即可
2)l>0,r<0
不满足l<r的前提，舍去
3)l<0,r>0
此时该扇形会覆盖到角度0，也就是l对应的正数是是一个>m的数，r则<m，直接塞(len,l,0),(len,r,1)则会出现问题，因为扫描线是按极坐标角度从小到大扫的，而这样塞l会被排在r后面
所以考虑以0角度为基准，把该扇形分割为[0,l],[0,r]两部分
对于0到l的这一块，分解为(len,2m+l,0),(len,2m,1)
对于0到r的这一块，分解为(len,0,0),(len,r,1)
4)l<0,r<0
l,r同为负，转成2m+l,2m+r即可
转为(len,2m+l,0),(len,2m+r,1)
3.l>r
1)l>0,r>0
同样分割成两部分，转为(len,l,0),(len,2m,1),(len,0,0),(len,r,1)
2)l>0,r<0
r转正变成2m+r，转为(len,l,0),(len,2m+r,1)
3)l<0,r>0
不满足l>r的前提，舍去
4)l<0,r<0
同理分解为(len,2m+l,0),(len,2m,1),(len,0,0),(len,2m+r,1)
4.l==0,r≠0 (由于可能有0的存在导致在2.3.的时候懒得去想什么地方写>=0什么地方写>0，所以干脆把有0的列出来好了)
1)r<0 (len,0,0),(len,2m+r,1)
2)r>0 (len,0,0),(len,r,1)
5.l≠0,r==0
1)l<0 (len,2m+l,0),(len,2m,1)
2)l>0 (len,l,0),(len,2m,1)
如何扫描线
扇形分解成线段了之后，按照pos为关键字sort一下，从小到大遍历一遍
一个半径为r，圆心角为α的扇形的扇形对答案的贡献为*αr²**
循环中一开始先累计答案：*ans+=(当前平衡树中第k大长度)²(s[i].pos-s[i-1].pos)**，表示前一个位置到当前位置的区域的面积
然后看当前线段的标记tag
tag为0时往平衡树中插入线段长len
tag为1时在平衡树中删去一个len
代码：指针Splay(记得处理好long long)
#include<cstdio>
#include<algorithm>
using std::sort;
template<class type>inline void read(type &in)
{
in=0;char ch=getchar();short fh=1;
while (ch<48||ch>57)fh=ch=='-'?-1:fh,ch=getchar();
while (ch>47&&ch<58)in=(in<<3)+(in<<1)+ch-48,ch=getchar();
in*=fh;
}
typedef long long ll;
const int N=1e5+10;
class Splay
{
private:
struct tree
{
int size,value,cnt;
tree *son[2],*fa;
inline const void pushup()
{
size=son[0]->size+cnt+son[1]->size;
}
inline const bool identity()
{
return fa->son[1]==this;
}
}*null,*root,memory_pool[N<<2],*tail,*rec[N<<2];
int top;
inline const void init()
{
tail=memory_pool;
null=tail++;
null->size=null->cnt=null->value=0;
null->son[0]=null->son[1]=null->fa=null;
root=null;
}
inline tree *spawn(int key)
{
tree *p=top?rec[--top]:tail++;
p->value=key;
p->size=p->cnt=1;
p->fa=p->son[0]=p->son[1]=null;
return p;
}
inline const void erase(tree *&p)
{
rec[top++]=p;p=null;
}
inline const void connect(tree *p,tree *fa,bool which)
{
if (p!=null)p->fa=fa;
if (fa!=null)fa->son[which]=p,fa->pushup();
}
protected:
inline const void rotate(tree *p)
{
tree *fa=p->fa;
bool id=p->identity();
connect(p,fa->fa,fa->identity());
connect(p->son[id^1],fa,id);
connect(fa,p,id^1);
}
inline const void splay(tree *p)
{
for (tree *fa;(fa=p->fa)!=null;rotate(p))
if (fa->fa!=null)
rotate(p->identity()^fa->identity()?p:fa);
root=p;
}
inline const void find(int key)
{
tree *now=root;
while (now->son[key<now->value]!=null&&now->value!=key)
now=now->son[key<now->value];
splay(now);
}
inline tree *precursor(tree *p)
{
splay(p);
tree *now=p->son[0];
while (now->son[1]!=null)now=now->son[1];
return now;
}
public:
inline Splay(){init();}
inline const void insert(int key)
{
if (root==null)return (void)(root=spawn(key));
tree *now=root;
while (1)
{
if (now->value==key)
return now->cnt++,now->pushup(),splay(now);
tree *fa=now;
bool which=key<fa->value;
now=fa->son[which];
if (now==null)
return now=spawn(key),connect(now,fa,which),splay(now);
}
}
inline const void Delete(int key)
{
find(key);tree *p=root;
if (p->cnt>1)return p->cnt--,p->pushup();
if (p->son[0]==null&&p->son[1]==null)return root=null,erase(p);
if (p->son[0]==null)return (root=p->son[1])->fa=null,erase(p);
if (p->son[1]==null)return (root=p->son[0])->fa=null,erase(p);
tree *pre=precursor(p);splay(pre);connect(p->son[1],pre,1);erase(p);
}
inline const int findrank(int k)
{
tree *now=root;
while (1)
if (k<=now->son[0]->size)now=now->son[0];
else
if ((k-=now->son[0]->size+now->cnt)<=0)
return now->value;
else now=now->son[1];
}
inline const int size()
{
return root->size;
}
}S;
int n,m,k,cnt;
ll ans;
struct segment
{
int len,pos;bool tag;
inline const bool operator<(const segment &p)const
{
return pos<p.pos;
}
}s[N<<2];
inline const void addseg(int len,int pos,bool tag)
{
s[++cnt].len=len;s[cnt].pos=pos;s[cnt].tag=tag;
}
inline const ll square(int x)
{
return (ll)((ll)(x)*(ll)(x));
}
int main()
{
read(n);read(m);read(k);
for (int len,l,r,i=1;i<=n;i++)
if (read(len),read(l),read(r),l==r)
addseg(len,0,0),addseg(len,2*m,1);
else
if (!l||!r)
if (!l)addseg(len,0,0),addseg(len,r<0?r+2*m:r,1);
else addseg(len,l>0?l:2*m+l,0),addseg(len,2*m,1);
else
if (l<r)
{
if (l<0&&r>0)addseg(len,0,0),addseg(len,r,1),addseg(len,2*m+l,0),addseg(len,2*m,1);
if (l>0&&r>0)addseg(len,l,0),addseg(len,r,1);
if (l<0&&r<0)addseg(len,2*m+l,0),addseg(len,2*m+r,1);
}
else
{
if (l<0&&r<0)addseg(len,2*m+l,0),addseg(len,2*m,1),addseg(len,0,0),addseg(len,2*m+r,1);
if (l>0&&r<0)addseg(len,l,0),addseg(len,2*m+r,1);
if (l>0&&r>0)addseg(len,l,0),addseg(len,2*m,1),addseg(len,0,0),addseg(len,r,1);
}
sort(s+1,s+cnt+1);
for (int i=1;i<=cnt;i++)
{
if (S.size()>=k)ans+=square(S.findrank(k))*(s[i].pos-s[i-1].pos);
if (!s[i].tag)S.insert(s[i].len);
else S.Delete(s[i].len);
}
if (S.size()>=k)ans+=square(S.findrank(k))*(s[cnt].pos-s[cnt-1].pos);
printf("%lld\n",ans);
return 0;
}