题解 P2611 【[ZJOI2012]小蓝的好友】【Treap】【扫描线】
wjyyy
2018-07-07 16:17:11
## 前言：
上来一看，这不是要先$C\times R$处理一下吗，于是看到了数据范围
遍历一遍都不让怎么瞎搞。。。不过N是100000+随机数据emmm
感谢写出让我看得懂得题解的[xyz32768](https://blog.csdn.net/xyz32768/article/details/80457425)
以及我的博客[传送门](http://www.wjyyy.top/763.html)
## 题解：
统计有一个资源点的矩形个数，感觉一时半会推不出公式。于是了解了**补集转换**，就是用所有矩形个数减去没有资源点的个数，貌似有点像[**Vijos 1225 月饼盒**](https://vijos.org/p/1255)，不过还是不好想。**先看怎么统计所有矩形的个数**：因为矩形是由线段×线段得到的，所以用横线段个数乘上纵线段个数，就是矩形个数。长度为1的横线段有$C$条，长度为2的横线段有$C-1$条，……，长度为$C$的线段有1条，同理长度为1的纵线段有$R$条等等。因此横线段的个数为$\frac{C(C+1)}2$，纵线段的个数为$\frac{R(R+1)}2$，相乘就得到了$\frac{C(C+1)R(R+1)}4$个矩形，乘开之后，发现要开**long long**（不开long long 是有10分的）。
这个题要推导的数学公式很多，因为我们仍然要计算**空矩形**个数。
接着看怎么统计空矩形个数，根据样例，第一行是这样的（O表示空点，X表示有资源）
```cpp
OXOOO
```
图中共有7个空矩形，左边的一个O贡献了1个，右边的3个O贡献了6个。计算方式就是对每一个**纵向连续最长的O**，用它及它左边**连续纵向 _不比它短_ 的O**的个数乘上它及它右边**连续纵向比它长的O**的个数，就不会冲突了。也就是1×1+1×1+2×1+3×1=7。那如果矩形的宽大于1怎么处理？一样地，我们仍然可以这样计算，举个例子：
```cpp
OXOOO
OOXOO
```
对于第二行最左边一个O，如果我们同样计算，它**所贡献**的矩形有2(高度)×1(左边)×1(右边)=2个（以此类推纵向高度为k的矩形**新**贡献的矩形有k个），第二个O贡献了1×2×1=2个，第四个O贡献了2×1×1=2个，第五个贡献了2×2×1=4个。则第二行一共有8个空矩形。
如何维护并尽快计算这个结果呢？因为**数据随机**，对于第i列到此连续O的个数，用t[i]来表示，把i的序号用Treap维护（随机时Treap的深度有保证），再用t[i]来维护Treap。在Treap上，有BST的性质，所以与某个位置相邻的且比它短的点，都在它的左右孩子处；因为每向下扩展一行就会使很多个t[i]自增1，所以我们维护t[i]保存的是第i列以当前行位置从下往上数第一个X在哪一行，每次处理用当前行数减去t[i]就是**新贡献**矩形个数。那么这样我们按t[i]维护一个大根堆，这样一来，上面的**连续纵向比它长**的就分别是左右孩子的数量+1了。新增矩形个数$=(sz[ls]+1)(sz[rs]+1)$，Treap每次旋转也要维护这个值。
**构建Treap：**一开始所有点的权值都为0，我们直接按照BST构建就可以了，每次取中点，左右区间作为左右孩子，递归建树。
Treap里要存$t[i]×(sz[i_{ls}]+1)(sz[i_{rs}]+1)$、子树中这个数据的和以及基础的BST信息。因为没学过Treap，我的Treap是按splay风格写的，不要太介意。
#### 平衡树多maintain总没有错。
时间复杂度：$O(C+R+N\log C)$
## Code：
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mid (l+r>>1)
int r,c,n;
struct node
{
int key,v;//关键字 维护值
long long sz,ans,anstt;//子树大小 乘积(v与sz) 乘积之和 v之和
long long sztt;
node *s[2];
node(int key,int v)
{
this->key=key;
this->v=v;
sz=1;
sztt=1;
ans=0;
anstt=0;
s[0]=NULL;
s[1]=NULL;
}
node()
{
v=0;
sz=1;
sztt=1;
ans=1;
anstt=0;
s[0]=NULL;
s[1]=NULL;
}
long long getsz()//访问节点大小
{
if(!this)
return 0;
return sz;
}
long long getsztt()
{
if(!this)
return 0;
return sztt;
}
long long getanstt()
{
if(!this)
return 0;
return anstt;
}
long long getd(int x)//询问方向
{
if(x==key)
return -1;
return x>key;
}
long long getv()//访问维护值
{
if(!this)
return -1;
return v;
}
void maintain()
{
sz=s[0]->getsz()+s[1]->getsz()+1;
sztt=(s[0]->getsz()+1)*(s[1]->getsz()+1)+s[0]->getsztt()+s[1]->getsztt();
ans=v*(s[0]->getsz()+1)*(s[1]->getsz()+1);
anstt=ans+s[0]->getanstt()+s[1]->getanstt();
}
}*root=NULL;
void build(node *&rt,int l,int r)
{
rt=new node(mid,0);
if(l==r)
return;
if(mid>l)
build(rt->s[0],l,mid-1);
if(mid<r)
build(rt->s[1],mid+1,r);
rt->maintain();
return;
}
void Rotate(node *&rt,int d)
{
node *tmp=rt->s[d];
rt->s[d]=tmp->s[d^1];
tmp->s[d^1]=rt;
rt->maintain();
rt=tmp;
rt->maintain();
return;
}
void treap(node *&rt)
{
//大根堆
if(rt->v>rt->s[0]->getv()&&rt->v>rt->s[1]->getv())
return;
if(rt->s[0]->getv()>rt->s[1]->getv())//把左孩子拉上来
{
Rotate(rt,0);
treap(rt->s[1]);
}
else
{
Rotate(rt,1);
treap(rt->s[0]);
}
rt->maintain();
}
void change(node *&rt,int t,int x)//把t改为x
{
int d=rt->getd(t);
if(d==-1)
{
rt->v=x;//可能有问题
rt->maintain();
treap(rt);
rt->maintain();
return;
}
change(rt->s[d],t,x);
treap(rt);
rt->maintain();
}
struct pnt
{
int x,y;//行 列数
friend bool operator <(pnt a,pnt b)
{
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
}p[101000];
int main()
{
scanf("%d%d%d",&r,&c,&n);//r行c列
build(root,1,c);
for(int i=1;i<=n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
std::sort(p+1,p+1+n);
int cur=1;
long long sum=(long long)((r+1)*r/2)*((c+1)*c/2);
for(int i=1;i<=r;i++)
{
while(p[cur].x==i)
{
change(root,p[cur].y,i);
cur++;
}
sum-=i*(root->sztt)-root->anstt;
}
printf("%lld\n",sum);
return 0;
}
```