题目
题目链接：https://www.luogu.com.cn/problem/P2611
“国家的战争其本质是抢夺资源的战争”是整款游戏的核心理念，这个小游戏也不例外。
简单来说，用户需要在一块 \(R\times C\) 的长方形土地上选出一块子矩形。
而系统随机生成了 \(N\) 个资源点，第 \(i\) 个资源点的坐标为 \((x_i,y_i)\)。
位于用户所选的长方形土地上的资源点越多，给予用户的奖励也越多。
悲剧的是，小蓝的好友虽然拥有着极其优秀的能力，但同时也有着极差的 RP，小蓝的好友所选的区域总是没有一个资源点。
终于有一天，小蓝的好友决定投诉这款游戏的制造厂商，为了搜集证据，小蓝的好友想算出至少包含一个资源点的区域的数量。
具体的说，你需要计算有多少个四元组 \((LB,DB,RB,UB)\) 满足 \(1\le LB\le RB\le R,1\le DB\le UB\le C\) ，且存在一个 \(i\) 使得 \(LB\le xi\le RB,DB\le yi\le UB\) 均成立。
作为小蓝的好友，这自然是你分内之事。
思路
下文设矩形为 \(n\times m\) 的。
考虑用总点数减去不包含任意资源点的方案数。
那么假设我们枚举一个矩形的下边、左边、右边的位置，那么上边最多能取的高度取决于左右边之间包含资源点的最小高度。
考虑从上往下枚举下边，建立一棵 \([1,n]\) 的 Treap。这棵 Treap 的前序遍历就是 \(1\sim n\)，一个点 \(x\) 的 \(dat\)（小根堆的权值） 等于在这条线上方，横坐标为 \(x\) 的资源点最小纵坐标。
由于数据随机，所以这棵 Treap 的期望高度是 \(O(\log m)\) 的。
那么一个点 \(x\) 的左子树内的点就是横坐标小于 \(x\) 且资源点最小高度大于 \(x\) 的资源点最小高度的连续的点，也就是一个点 \(x\)，最左可以扩张到 \(size[lc[x]]\)。同理最右可以扩张到 \(size[rc[x]]\)。
所以点 \(x\) 对答案的贡献为
Treap 维护子树和即可。修改操作修改 \(dat\)。
时间复杂度 \(O(n\log n)\)。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=150010;
int n,m,Q,rt;
ll ans;
vector<int> pos[N];
struct Treap
{
int tot,lc[N],rc[N],size[N],val[N],dat[N];
ll sum[N],cnt[N];
void pushup(int x)
{
size[x]=size[lc[x]]+size[rc[x]]+1;
cnt[x]=cnt[lc[x]]+cnt[rc[x]]+1LL*(size[lc[x]]+1)*(size[rc[x]]+1);
sum[x]=sum[lc[x]]+sum[rc[x]]+1LL*(size[lc[x]]+1)*(size[rc[x]]+1)*dat[x];
}
int zig(int &x)
{
int y=lc[x];
lc[x]=rc[y]; rc[y]=x; x=y;
pushup(rc[x]); pushup(x);
return x;
}
int zag(int &x)
{
int y=rc[x];
rc[x]=lc[y]; lc[y]=x; x=y;
pushup(lc[x]); pushup(x);
return x;
}
int build(int ql,int qr)
{
int mid=(ql+qr)>>1,x=++tot;
val[x]=mid; size[x]=cnt[x]=1; dat[x]=sum[x]=n+1;
if (ql==qr) return x;
if (ql<mid) lc[x]=build(ql,mid-1);
if (qr>mid) rc[x]=build(mid+1,qr);
pushup(x);
return x;
}
int del(int x,int p)
{
if (val[x]==p)
{
if (!lc[x] && !rc[x]) return 0;
if (!rc[x] || dat[lc[x]]<dat[rc[x]])
zig(x),rc[x]=del(rc[x],p);
else
zag(x),lc[x]=del(lc[x],p);
pushup(x);
return x;
}
if (p<val[x]) lc[x]=del(lc[x],p);
else rc[x]=del(rc[x],p);
pushup(x);
return x;
}
int ins(int x,int p,int v)
{
if (!x)
{
val[++tot]=p; size[tot]=cnt[tot]=1; dat[tot]=sum[tot]=v;
return tot;
}
if (p<val[x])
{
lc[x]=ins(lc[x],p,v);
if (dat[x]>dat[lc[x]]) zig(x);
}
else
{
rc[x]=ins(rc[x],p,v);
if (dat[x]>dat[rc[x]]) zag(x);
}
pushup(x);
return x;
}
}treap;
int main()
{
scanf("%d%d%d",&n,&m,&Q);
for (int i=1,x,y;i<=Q;i++)
{
scanf("%d%d",&x,&y);
pos[x].push_back(y);
}
rt=treap.build(1,m);
treap.dat[0]=19260817;
for (int i=n;i>=1;i--)
{
for (int j=0;j<pos[i].size();j++)
{
rt=treap.del(rt,pos[i][j]);
rt=treap.ins(rt,pos[i][j],i);
}
ans+=treap.sum[rt]-treap.cnt[rt]*i;
}
printf("%lld",1LL*n*(n+1)/2LL*m*(m+1)/2LL-ans);
return 0;
}