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

作者: wjyyy 分类: Treap,扫描线,补集转换,解题报告 发布时间: 2018-07-07 16:06

点击量:25

 

   只会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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */