51Nod 1555 布丁怪

题目描述:

布丁怪这一款游戏是在一个n×n 的矩形网格中进行的，里面有n个网格有布丁怪，其它的一些格子有一些其它的游戏对象。游戏的过程中是要在网格中移动这些怪物。如果两个怪物碰到了一起，那么他们就会变成一个更大的怪物。（谁叫他们是布丁呢？）

据统计，如果每一行每一列都只有一个布丁怪，那么这样的布局是比较吸引玩家的。

所以为了产生多种多样的有趣布局，我们会从一个 n×n 的有趣的地图中选取一个k×k (1≤k≤n)子矩形作为地图，而且这个子地图中恰好有k个布丁怪。

现在请你计算一下一个n×n 的有趣布局中，有多少种子地图是有趣的。

解题报告:

用时3h,2WA

这一题开始想着优化\(O(n^2)\)的暴力，并没有成功，然后请教大佬，得知是分治,然后花了3h才弄出这个分治，分治函数里必须数线性的，所以考虑怎么算贡献，发现只需要讨论最大值和最小值分别再\((l,mid)\)还是\((mid+1,r)\)

首先是全部在左边的，那么就可以确定右端点的位置，全在右边的同理

难点在于分别在左右两端的:

我们考虑左边是最小值，右边是最大值

那么对于\(R-L=Max-Min\)这个式子我们可以拆成：\(R-Max=L-Min\)就可以把\(R-Max\)放进桶里，然后统计\(L-Min\)即可，然后我就傻逼的放进了桶里，并没有维护左边最小值小于右边最小值，左边最大值小于右边最大值这两个条件，然后答案大了许多,所以要开两个单调指针维护左边最小值小于右边最小值，左边最大值小于右边最大值这两个条件，注意数组要偏移

对于左边是最大值，右边是最小值的情况同理:

维护\(R+Min=L+Max\)即可

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

const int N=4e5+5;

struct node{

	int x,y;

	bool operator <(const node &r)const{

		return x<r.x;

	}

}a[N];

int n,L[N],R[N],t[N*3],mov=N;long long ans=0;

void solve(int l,int r){

	if(l==r){

		ans++;

		return ;

	}

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

	solve(l,mid);solve(mid+1,r);

	L[mid]=a[mid].y,R[mid]=a[mid].y;

	for(int i=mid-1;i>=l;i--){

		L[i]=Min(L[i+1],a[i].y);

		R[i]=Max(R[i+1],a[i].y);

	}

	L[mid+1]=a[mid+1].y;R[mid+1]=a[mid+1].y;

	for(int i=mid+2;i<=r;i++){

		L[i]=Min(L[i-1],a[i].y);

		R[i]=Max(R[i-1],a[i].y);

	}

	int j,k;

	for(int i=mid;i>=l;i--){

		k=R[i]-L[i]+1;

		j=mid+(k-(mid-i+1));

		if(j<=mid || j>r)continue;

		if(R[j]>=L[i] && R[j]<=R[i] && L[j]>=L[i] && L[j]<=R[i])

                       ans++;

	}

	for(int i=mid+1;i<=r;i++){

		k=R[i]-L[i]+1;

		j=mid-(k-(i-mid+1));

		if(j>=mid+1 || j<l)continue;

		if(R[j]>=L[i] && R[j]<=R[i] && L[j]>=L[i] && L[j]<=R[i])

                       ans++;

	}

	int pr=mid+1,pl=mid+1;

	for(int i=mid;i>=l;i--){

		while(pr<=r && L[i]<L[pr])t[R[pr]-pr+mov]++,pr++;

		while(pl<pr && R[i]>R[pl])t[R[pl]-pl+mov]--,pl++;

		ans+=t[L[i]-i+mov];

	}

	for(int i=pl;i<pr;i++)t[R[i]-i+mov]--;

	pr=mid;pl=mid;

	for(int i=mid+1;i<=r;i++){

		while(pr>=l && L[i]<L[pr])t[R[pr]+pr]++,pr--;

		while(pl>pr && R[i]>R[pl])t[R[pl]+pl]--,pl--;

		ans+=t[L[i]+i];

	}

	for(int i=pl;i>pr;i--)t[R[i]+i]--;

}

void work()

{

	scanf("%d",&n);

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

		scanf("%d%d",&a[i].x,&a[i].y);

	}

	sort(a+1,a+n+1);

	solve(1,n);

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

}

int main()

{

	work();

	return 0;

}

巴特西

51Nod 1555 布丁怪

最新文章

热门文章