题面

终于到达了这次选拔赛的最后一题，想必你已经厌倦了小蓝和小白的故事，为了回馈各位比赛选手，此题的主角是贯穿这次比赛的关键人物——小蓝的好友。
在帮小蓝确定了旅游路线后，小蓝的好友也不会浪费这个难得的暑假。与小蓝不同，小蓝的好友并不想将时间花在旅游上，而是盯上了最近发行的即时战略游戏——SangoCraft。但在前往通关之路的道路上，一个小游戏挡住了小蓝的好友的步伐。
“国家的战争其本质是抢夺资源的战争”是整款游戏的核心理念，这个小游戏也不例外。简单来说，用户需要在给定的长方形土地上选出一块子矩形，而系统随机生成了N个资源点，位于用户所选的长方形土地上的资源点越多，给予用户的奖励也越多。悲剧的是，小蓝的好友虽然拥有着极其优秀的能力，但同时也有着极差的RP，小蓝的好友所选的区域总是没有一个资源点。
终于有一天，小蓝的好友决定投诉这款游戏的制造厂商，为了搜集证据，小蓝的好友想算出至少包含一个资源点的区域的数量。作为小蓝的好友，这自然是你分内之事。

Input

每个输入文件中仅包含一个测试数据。
第一行包含两个由空格隔开的正整数R,C,N，表示游戏在一块[1,R]X[1,C]的地图上生成了N个资源点。
接下来有N行，每行包含两个整数 x,y，表示这个资源点的坐标
(1<=x<=R,1<=Y<=c)。

Output

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

HINT：资源的位置随机生成

题解

把题目要求转化为总矩形数 - 不包含资源的矩形数。

整个图刷白，把存在z资源的格子染黑（这里把坐标系当成表格，因为题目中其实是允许点和线作为矩形存在的），那么就是求全白子矩形数量。

这是个笛卡尔树或单调栈的经典问题，一般是每行都扫一遍，考虑到这题的数据范围，我们采用扫描线+动态维护。

我们从上往下扫，维护向上的矩形，那么动态维护就只需要支持两种操作：整体向上抬升、单点清零。如果基于笛卡尔树的话，就很方便计算贡献了。于是，我们用 fhq Treap 维护笛卡尔树，整体抬升加个标记就是了，单点清零就把整棵树裂成两半，然后直接加在新点的左右儿子处。由于是随机分布，所以不需要用 heap ，本身笛卡尔树就是平衡的了。

于是这题

O

(

n

log

⁡

n

)

O(n\log n)

O(nlogn) 无旋 Treap 解决，常数较大，上百毫秒。

但是考虑到我们最后解出问题的核心，其实利用了随机分布。

如果你在刚想到单调栈后就留意到随机分布会怎样呢？你会想：一个位置往一个方向跳，每次跳到第一个小于等于先前位置的地方，最多会跳 log 次。

于是，除了用 Treap 以外，我们可以直接模拟，维护每个位置往左第一个小于等于他的位置

l

d

ld

ld，以及往右第一个小于等于他的位置

r

d

rd

rd。整体抬升，我们就记录一下当前与底部接壤的矩形个数

x

x

x，抬升时将

x

x

x 加上

(

R

+

1

)

⋅

R

/

2

(R+1)\cdot R/2

(R+1)⋅R/2，并将最终答案加上

x

x

x 。单点清零的时候，我们可以直接跳

l

d

ld

ld 和

r

d

rd

rd 往下，计算清零对

x

x

x 以及最终答案的减少量（由于抬升后假设的是该位置无资源，加点后这个地方是有资源的，因此最终答案也有影响），最重要的是，再顺便把沿途的

l

d

ld

ld、

r

d

rd

rd 更新。你会发现，假使一开始定义的是小于而不是小于等于，那么这步没法做。

于是这题模拟

O

(

n

log

⁡

n

)

O(n\log n)

O(nlogn) 做，快如指针，常数极小，几十毫秒。

CODE

几十毫秒的代码

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<ctime>

#include<queue>

#include<bitset>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 100005

#define LL long long

#define DB double

#define ENDL putchar('\n')

#define lowbit(x) (-(x) & (x))

#define FI first

#define SE second

#define SI(x) multiset<x>::iterator

#define MI map<int,int>::iterator

#define PR pair<int,int>

#define BI(x) bitset<x>

LL read() {

	LL f=1,x=0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}

	return f*x;

}

void putpos(LL x) {

	if(!x) return ;

	putpos(x/10); putchar('0'+(x%10));

}

void putnum(LL x) {

	if(!x) putchar('0');

	else if(x < 0) putchar('-'),putpos(-x);

	else putpos(x);

}

void AIput(LL x,char c) {putnum(x);putchar(c);}

int n,m,s,o,k;

int R,C;

vector<int> bu[MAXN];

int a[MAXN],ld[MAXN],rd[MAXN],bt;

LL as1,ans;

LL d1(int l,int r,int m,int h) {return (m-l+1) *1ll* (r-m+1) * h;}

void add(int x,int y) {

	int yy = a[x];

	int ll = x,rr = x,A = ld[x],B = rd[x];

	while(yy > y) {

		int ny;

		if(a[A] >= y) rd[A] = min(rd[A],x);

		if(a[B] >= y) ld[B] = max(ld[B],x);

		if(a[A] > a[B]) ny = a[A],A = ld[A];

		else ny = a[B],B = rd[B];

		while(a[ll] > max(y,ny)) ll = ld[ll];

		while(a[rr] > max(y,ny)) rr = rd[rr];

		int le = yy-max(y,ny);

		LL d = d1(ll+1,rr-1,x,le);

		as1 -= d; ans -= d;

		yy = ny;

	}

	ld[x] = ll; rd[x] = rr;

	a[x] = y;

	return ;

}

int main() {

	freopen("fish.in","r",stdin);

	freopen("fish.out","w",stdout);

	R = read();C = read();

	n = read();

	rd[0] = n+1;ld[R+1] = 0;

	a[0] = a[R+1] = -1;

	for(int i = 1;i <= R;i ++) {

		a[i] = C;

		ld[i] = i-1; rd[i] = i+1;

	}

	for(int i = 1;i <= n;i ++) {

		s = read();o = read();

		bu[o-1].push_back(s);

	}

	for(int Y = C-1;Y >= 0;Y --) {

		as1 += (R+1)*1ll*R/2ll;

		ans += as1;

		for(int i = 0;i < (int)bu[Y].size();i ++) {

			add(bu[Y][i],Y);

		}

	}

	LL ful = (R+1)*1ll*R/2ll * (C+1)*1ll*C/2ll;

	printf("%lld\n",ful-ans);

	return 0;

}

【BZOJ2658】[Zjoi2012]小蓝的好友(mrx) （扫描线，平衡树，模拟）的相关教程结束。