非确定性有穷状态决策自动机练习题Vol.2 C. 奇袭

题目描述

由于各种原因，桐人现在被困在\(Under World\)（以下简称\(UW\)）中，而\(UW\)马上要迎来最终的压力测试——魔界入侵。

唯一一个神一般存在的\(Administrator\)被消灭了，靠原本的整合骑士的力量是远远不够的。所以爱丽丝动员了\(UW\)全体人民，与整合骑士一起抗击魔族。

在\(UW\)的驻地可以隐约看见魔族军队的大本营。整合骑士们打算在魔族入侵前发动一次奇袭，袭击魔族大本营！为了降低风险，爱丽丝找到了你，一名优秀斥候，希望你能在奇袭前对魔族大本营进行侦查，并计算出袭击的难度。

经过侦查，你绘制出了魔族大本营的地图，然后发现，魔族大本营是一个\(N \times N\)的网格图，一共有\(N\)支军队驻扎在一些网格中（不会有两只军队驻扎在一起）。

在大本营中，每有一个\(k×k(1≤k≤N)\)的子网格图包含恰好\(k\)支军队，我们袭击的难度就会增加\(1\)点。

现在请你根据绘制出的地图，告诉爱丽丝这次的袭击行动难度有多大。

输入格式

第一行，一个正整数\(N\)，表示网格图的大小以及军队数量。

接下来N行，每行两个整数,\(Xi\),\(Yi\)，表示第\(i\)支军队的坐标。

保证每一行和每一列都恰有一只军队,即每一个\(Xi\)和每一个\(Yi\)都是不一样的。

输出格式

一行，一个整数表示袭击的难度。

样例

样例输入

5

1 1

3 2

2 4

5 5

4 3

样例输出

10

样例解释

显然，分别以\((2,2)\)和\((4,4)\)为左上,右下顶点的一个子网格图中有\(3\)支军队，

这为我们的难度贡献了\(1\)点。

类似的子网格图在原图中能找出\(10\)个。

数据范围与提示

对于\(30\%\)的数据，\(N ≤ 100\)

对于\(60\%\)的数据，\(N ≤ 5000\)

对于\(100\%\)的数据，\(N ≤ 50000\)

分析

用线段树即可解决

首先，我们发现，如果要满足 \(k×k(1≤k≤N)\) 的子网格图包含恰好 \(k\) 支军队

那么这 \(k\) 只军队的最大横坐标减去最小横坐标恰好等于这 \(k\) 只军队的最大纵坐标减最小纵坐标

两维不好处理，因此我们把横坐标作为下标，纵坐标作为权值

这样原问题就变成了在一个排列中有多少区间内的数是连续的

我们发现这可以用线段树去维护

我们把线段树的节点定义为以某个点为左端点，以扫到的点为右端点的区间中连续区间的个数

线段树要维护的信息有连续区间个数的最小值，该最小值的个数，以及区间加和操作中的 \(lazy\) 标记

每次从右边新加入一个点 \(i\) 时，我们把区间 \([1,i]\) 整体加 \(1\)

代表此时又多了一个不连续的区间

此时我们去找 \(a[i]+1\) 和 \(a[i]-1\) 的位置，如果它们的位置在 \(i\) 的左边，我们就把 \([1,a[i]-1]\) 或者 \([1,a[i]+1]\) 整体减一，代表包含 \(a[i]+1\) 或者 \(a[i]-1\) 的区间可以与 \(a[i]\) 合并形成一个大区间

每次枚举一个右端点时就单独计算一下价值

代码

#include<cstdio>

#include<algorithm>

#include<cmath>

const int maxn=1e6+5;

inline int read(){

	int x=0,f=1;

	char ch=getchar();

	while(ch<'0' || ch>'9'){

		if(ch=='-') f=-1;

		ch=getchar();

	}

	while(ch>='0' && ch<='9'){

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return x*f;

}

int a[maxn],n,wz[maxn];

struct asd{

	int l,r,min,cnt,laz;

}tr[maxn<<1];

void push_up(int da){

	if(tr[da<<1].min==tr[da<<1|1].min){

		tr[da].min=tr[da<<1].min;

		tr[da].cnt=tr[da<<1].cnt+tr[da<<1|1].cnt;

	} else if(tr[da<<1].min<tr[da<<1|1].min){

		tr[da].min=tr[da<<1].min;

		tr[da].cnt=tr[da<<1].cnt;

	} else {

		tr[da].min=tr[da<<1|1].min;

		tr[da].cnt=tr[da<<1|1].cnt;

	}

}

void push_down(int da){

	if(tr[da].laz==0) return;

	tr[da<<1].min+=tr[da].laz;

	tr[da<<1|1].min+=tr[da].laz;

	tr[da<<1].laz+=tr[da].laz;

	tr[da<<1|1].laz+=tr[da].laz;

	tr[da].laz=0;

}

void build(int da,int l,int r){

	tr[da].l=l,tr[da].r=r;

	if(l==r){

		tr[da].min=1;

		tr[da].cnt=1;

		return;

	}

	int mids=(l+r)>>1;

	build(da<<1,l,mids);

	build(da<<1|1,mids+1,r);

	push_up(da);

}

int cx(int da,int l,int r){

	if(tr[da].l>=l && tr[da].r<=r){

		if(tr[da].min==1) return tr[da].cnt;

		return 0;

	}

	push_down(da);

	int mids=(tr[da].l+tr[da].r)>>1;

	int ans=0;

	if(l<=mids) ans+=cx(da<<1,l,r);

	if(r>mids) ans+=cx(da<<1|1,l,r);

	return ans;

}

void xg(int da,int l,int r,int val){

	if(tr[da].l>=l && tr[da].r<=r){

		tr[da].min+=val;

		tr[da].laz+=val;

		return;

	}

	push_down(da);

	int mids=(tr[da].l+tr[da].r)>>1;

	if(l<=mids) xg(da<<1,l,r,val);

	if(r>mids) xg(da<<1|1,l,r,val);

	push_up(da);

}

int main(){

	n=read();

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

		int aa,bb;

		aa=read(),bb=read();

		a[aa]=bb;

		wz[a[aa]]=aa;

	}

	build(1,1,n);

	long long ans=0;

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

		if(i>1) xg(1,1,i-1,1);

		if(wz[a[i]-1]<=i && wz[a[i]-1]){

			xg(1,1,wz[a[i]-1],-1);

		}

		if(wz[a[i]+1]<=i && wz[a[i]+1]){

			xg(1,1,wz[a[i]+1],-1);

		}

		ans+=(long long)cx(1,1,i);

	}

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

	return 0;

}

巴特西

非确定性有穷状态决策自动机练习题Vol.2 C. 奇袭

非确定性有穷状态决策自动机练习题Vol.2 C. 奇袭

题目描述

输入格式

输出格式

样例

样例输入

样例输出

样例解释

数据范围与提示

分析

代码

最新文章

热门文章