洛谷P2611/bzoj2658 [ZJOI2012]小蓝的好友 题解【Treap】【补集转换】

点击量：221

   只会splay的选手过来打Treap

目录

题目描述

终于到达了这次选拔赛的最后一题，想必你已经厌倦了小蓝和小白的故事，为了回馈各位比赛选手，此题的主角是贯穿这次比赛的关键人物——小蓝的好友。

 

在帮小蓝确定了旅游路线后，小蓝的好友也不会浪费这个难得的暑假。与小蓝不同，小蓝的好友并不想将时间花在旅游上，而是盯上了最近发行的即时战略游戏——SangoCraft。但在前往通关之路的道路上，一个小游戏挡住了小蓝的好友的步伐。

 

“国家的战争其本质是抢夺资源的战争”是整款游戏的核心理念，这个小游戏也不例外。简单来说，用户需要在给定的长方形土地上选出一块子矩形，而系统随机生成了N个资源点，位于用户所选的长方形土地上的资源点越多，给予用户的奖励也越多。悲剧的是，小蓝的好友虽然拥有着极其优秀的能力，但同时也有着极差的RP，小蓝的好友所选的区域总是没有一个资源点。

 

终于有一天，小蓝的好友决定投诉这款游戏的制造厂商，为了搜集证据，小蓝的好友想算出至少包含一个资源点的区域的数量。作为小蓝的好友，这自然是你分内之事。

 

输入输出格式

输入格式：

每个输入文件中仅包含一个测试数据。

 

第一行包含由两个空格隔开的正整数R,C,N，表示游戏在一块[1,R]X[1,C]的地图上生成了N个资源点。

 

接下来有N行，每行包含两个整数 x,y，表示这个资源点的坐标(1<=x<=r,1<=y<=C)

 

输出格式：

输出文件应仅包含一个整数，表示至少包含一个资源点的区域的数量。具体的说，设N个资源点的坐标为 (i=1..n),你需要计算有多少个四元组(LB,DB,RB,UB)满足1<=LB<=RB<=R,1<=DB<=UB<=C ，且存在一个i使得LB<=xi<=RB,DB<=yi<=UB均成立。

输入输出样例

输入样例#1：

5 5 4

1 2

2 3

3 5

4 1

输出样例#1：

139

说明

对于20%的数据，N<=50。

 

对于40%的数据，N<=2000。

 

对于100%的数据，R,C<=40000,N<=100000，资源点的位置两两不同，且位置为随机生成。

 

前言：

   上来一看，这不是要先$ C\times R$处理一下吗，于是看到了数据范围

   遍历一遍都不让怎么瞎搞。。。不过N是100000+随机数据emmm

   感谢写出让我看得懂得题解的xyz32768

题解：

   统计有一个资源点的矩形个数，感觉一时半会推不出公式。于是了解了补集转换，就是用所有矩形个数减去没有资源点的个数，貌似有点像Vijos 1225 月饼盒，不过还是不好想。先看怎么统计所有矩形的个数：因为矩形是由线段×线段得到的，所以用横线段个数乘上纵线段个数，就是矩形个数。长度为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表示有资源）

OXOOO

   图中共有7个空矩形，左边的一个O贡献了1个，右边的3个O贡献了6个。计算方式就是对每一个纵向连续最长的O，用它及它左边连续纵向不比它短的O的个数乘上它及它右边连续纵向比它长的O的个数，就不会冲突了。也就是1×1+1×1+2×1+3×1=7。那如果矩形的宽大于1怎么处理？一样地，我们仍然可以这样计算，举个例子：

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：

#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) 乘积之和
    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;
}