「ZJOI2012」小蓝的好友-Treap

简单版题意:

给定一个 $R \times C$ 的矩形,在其中 $N$ 个位置有资源点。现在请你求出在所有的子矩形中,至少包含一个资源点的矩形数量。


完整版题意:

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

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

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

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

数据范围:对于$100\%$的数据,$R,C \leq 40000$, $N \leq 100000$,资源点的位置两两不同,且位置为 随机生成

链接

Luogu P2611

题解

神题orz

首先把问题转化成不包含一个资源点的子矩形数目。

简直不可做好吗!枚举矩形都gg,简直很不可做…

所以说,我们需要用一些东西来加速这个过程。我也不知道,怎么就想到了笛卡尔树…

笛卡尔树是一棵二叉树,树的每个节点有两个值,一个为 $\text{key}$,一个为 $\text{val}$。光看 $\text{key}$ 的话,笛卡尔树是一棵二叉搜索树,每个节点的左子树的 $\text{key}$ 都比它小,右子树都比它大;光看 $\text{val}$ 的话,笛卡尔树有点类似堆,根节点的 $\text{val}$ 是最小(或者最大)的,每个节点的 $\text{val}$ 都比它的子树要大。

From: SengXian’s Blog

我们用扫描线,从上往下扫描,然后我们的笛卡尔树维护的是每一列,中序遍历就是列从左到右的顺序,每一个节点的 $\text{val}$ 就是这条扫描线到这一列最低的资源点的高度。

这里的笛卡尔树,我们不维护 $\text{key}$ ,是以序列下标来建树,类似文艺平衡树的 Splay ;堆则是小根堆。

由于高度的随机性,我们可以发现,这棵笛卡尔树的期望高度是 $O(\log{n})$ 的。

所以我们可以维护一点东西,来加速我们的运算。

我们维护一个$sum$,代表下界在当前扫描线,上界在这个节点高度以下的子矩形的个数。我们可以发现,当前的节点的siz,就是上界高度在其下的宽度(列数),然后我们可以得出满足这个条件的子矩形。然后所有的下界在扫描线上的矩形,都可以在这个笛卡尔树的所有节点处被不重不漏的包含。

然后我们思考如何更新。扫描线往下的话就是所有的 $ht+1$,发现可以打标记 $O(1)$ 解决。出现一个点事实上就是单点修改优先值( $\text{val}$ ),然后往上转,也可以在 $O(\log {n})$ 内解决。

然后计算就好了。有不少细节…怪难调的…要不是数据结构基础好估计就gg了…

最后的复杂度大约是$O(C + N \log R)$?

代码

点击切换显示状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <cstdio>
#include <algorithm>
#include <cctype>
#define ll long long
typedef int T;
using namespace std;
#define calc(x) (((ll)(x)*((x)+1))/2)

namespace fast_io{
//...
}using namespace fast_io;

const int MAXN = 110000;

namespace Treap{
//小根堆
#define ls c[x][0]
#define rs c[x][1]
ll ans[MAXN],addn[MAXN];
int ht[MAXN],siz[MAXN];
int c[MAXN][2],cnt = 0;
int root;
void maintain(int x){//确保合法才能maintain
siz[x] = siz[ls] + siz[rs] + 1;
ans[x] = ans[ls] + ans[rs];
ans[x] += (ll)(ht[ls] - ht[x])*calc(siz[ls]);
ans[x] += (ll)(ht[rs] - ht[x])*calc(siz[rs]);
}
int __build(int l,int r){
if(l > r) return 0;
int x = ++cnt,mid = (l+r)>>1;
siz[x] = 1;
ls = __build(l,mid-1),rs = __build(mid+1,r);
maintain(x);
return x;
}
void add(int x,int v){
addn[x] += v,ht[x] += v;
}
void push_down(int x){
if(addn[x]){
add(ls,addn[x]),add(rs,addn[x]);
addn[x] = 0;
}
}
void rotate(int &x,int t){
int y = c[x][t];
c[x][t] = c[y][1-t];
c[y][1-t] = x;
maintain(x),maintain(y);
x = y;
}
void modify(int &x,int r){
push_down(x);int t = siz[ls] + 1;
if(r == t){
ht[x] = 0;maintain(x);return;
}
else{
if(r < t){
modify(ls,r);
if(ht[ls]<ht[x]) rotate(x,0);
else maintain(x);
}
else{
modify(rs,r-t);
if(ht[rs]<ht[x]) rotate(x,1);
else maintain(x);
}
}
}
void add(){add(root,1);}
void modify(int r){modify(root,r);}
ll query(){return ans[root];}
int getheight(){return ht[root];}
void build(int n){root = __build(1,n);}
}

int n,m,k;

struct Point{
int x,y;
bool operator < (const Point & _a)const{
if(x != _a.x) return x < _a.x;
else return y < _a.y;
}
}p[MAXN];

void init(){
read(n),read(m),read(k);
for(int i = 1;i<=k;i++){
read(p[i].x),read(p[i].y);
}
}

void build(){
sort(p+1,p+k+1);
Treap::build(m);
}

void solve(){
static ll ans = calc(n)*calc(m);
for(int i = 1,j = 1;i<=n;i++){
Treap::add();
//printf("%d %d\n",p[j].x,p[j].y);
while(j <= k && p[j].x == i){
Treap::modify(p[j].y);j++;
}
ans -= Treap::query() + calc(Treap::siz[Treap::root]) * Treap::getheight();
}
printf("%lld\n",ans);
}

int main(){
init();
build();
solve();
return 0;
}