bzoj 2658

首先考虑容斥

我们计算出所有没有点在其中的矩形，然后用所有矩形减去这些矩形即可

然后考虑如何计算没有点在其中的矩形

采用扫描线的思想，从上向下一行一行扫，假设我们扫到的行编号是$a$，然后考虑如果左右的列端点是$[l,r]$，那么这一行向上至多能扩展几个矩形呢？

显然，我们要找到区间$[l,r]$中位置最下面的那个点，设其行编号为$w[i]$，那么矩形数量即为$a-w[i]$

画个图理解一下：

很清楚的就能看到，现在扫到的是红色的$a$，左右区间是蓝色的$[l,r]$，那么上界会被限制在$w[i]$这条黄线处，能向上延伸的矩形数量也就是$a-w[i]$

由于$a$是定值，因此我们考虑每个$w[i]$会对多少个区间$[l,r]$产生贡献

显然，$w[i]$必须是区间$[l,r]$中的最大值！

因此扫到每一个$a$，答案就变成了$\frac{c(c+1)}{2}a-\sum_{i=1}^{c}\sum_{j=i}^{c}max(i,j)$，其中$max(i,j)$表示区间$[i,j]$中最大的$w$

这个看着可以用单调栈维护维护嘛...

可是我们每次向下扫描的时候，$w$都会改变！

因此我们需要一个能够支持修改的数据结构，显然是一种二叉树

这个二叉树需要支持修改，最好能保证是一个大根堆，而且还要保证中序遍历得到的是原序列

这个...有点难？

treap嘛！

把序列的下标扔进二叉搜索树里，再把$w$作为权值体现堆的性质就可以了嘛

（其实就是把原来随机的一个权值变成了一个$w$）

由于数据随机，所以可以通过

这样每个点的贡献就是$(siz[lson]+1)(siz[rson]+1)w$

注意在修改时如果先删除再重新插入会T，考虑到每次修改权值只增不减，因此每个节点只会向上转，因此我们直接修改即可

代码：

#include <cstdio>

#include <algorithm>

#define ll unsigned long long

#define ls tree[rt].lson

#define rs tree[rt].rson

using namespace std;

struct Treap

{

    int lson,rson;

    int size,val;

    int rank;

    ll sum;

}tree[];

struct POS

{

    int x,y;

    friend bool operator < (POS a,POS b)

    {

        return a.x<b.x;

    }

}p[];

int tot=;

int rot;

ll sum=;

int r,c,n;

inline void update(const int &rt)

{

    tree[rt].size=tree[ls].size+tree[rs].size+;

    tree[rt].sum=1ll*(tree[ls].size+)*1ll*(tree[rs].size+)*tree[rt].rank+tree[ls].sum+tree[rs].sum;

}

inline void lturn(int &rt)

{

    int temp=rs;

    rs=tree[temp].lson;

    tree[temp].lson=rt;

    tree[temp].size=tree[rt].size;

    update(rt);

    rt=temp;

}

inline void rturn(int &rt)

{

    int temp=ls;

    ls=tree[temp].rson;

    tree[temp].rson=rt;

    tree[temp].size=tree[rt].size;

    update(rt);

    rt=temp;

}

void buildtree(int &rt,int l,int r)

{

    rt=++tot;

    if(l==r){tree[rt].val=l,tree[rt].size=;return;}

    int mid=(l+r)>>;

    tree[rt].val=mid;

    if(l<mid)buildtree(ls,l,mid-);

    if(r>mid)buildtree(rs,mid+,r);

    update(rt);

}

void ins(int &rt,int v,int w)

{

    if(!rt)return;

    if(tree[rt].val==v)

    {

        tree[rt].rank=w;

        update(rt);

        return;

    }

    if(v<tree[rt].val)

    {

        ins(ls,v,w);

        if(tree[ls].rank>tree[rt].rank)rturn(rt);

    }else

    {

        ins(rs,v,w);

        if(tree[rs].rank>tree[rt].rank)lturn(rt);

    }

    update(rt);

}

inline int read()

{

    int f=,x=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int main()

{

    r=read(),c=read(),n=read();

    for(register int i=;i<=n;++i)p[i].x=read(),p[i].y=read();

    buildtree(rot,,c);

    ll ans=;

    sort(p+,p+n+);

    int las=;

    for(register int i=;i<=r;++i)//枚举每一行

    {

        while(p[las].x==i&&las<=n)ins(rot,p[las].y,i),las++;

        ans+=c*(c+)/*1ll*i-tree[rot].sum;

    }

    printf("%llu\n",c*(c+)/2ll*1ll*r*(r+)/2ll-ans);

    return ;

}

巴特西

bzoj 2658

最新文章

热门文章