Pudding Monsters

wjh15101051's space

卧薪尝胆，厚积薄发。

Pudding Monsters

Date: Wed Oct 31 15:06:25 CST 2018

In Category: NoCategory

Description：

给一个棋盘，保证每行每列都有一个棋子，问有多少个子方阵也每行每列都有一个棋子。

$1\leqslant n\leqslant 10^6$

Solution：

把每列的棋子行数写成一个排列，就是求有多少个区间内部所有数排完序后两两相邻。

不难发现合法的区间满足 $max-min+1=r-l+1$ ，遇到区间统计问题不难想到分治的做法，但是这个题的分治容易想到但是细节很多，首先对于左边预处理后缀最大最小值，右边预处理前缀最大最小值，然后就可以得出 $[i,j]$ 满足条件当且仅当 $\max(maxv[i],maxv[j])-\min(minv[i],minv[j])=j-i$ ，分两种情况讨论一下，如果最大最小值都在同一侧，那么就可以枚举 $i$ 直接计算出 $j$ 判断是否满足条件即可，如果最大最小值在两侧，如果最大值在左边，那么 $maxv[i]-minv[j]=j-i$ ，即 $maxv[i]+i=minv[j]+j$ ，发现 $i$ 一定在一个区间中，即 $minv[i]\geqslant minv[j]$ ，这一定是一个后缀，随着 $j$ 变大左端点逐渐左移， $maxv[i]\geqslant maxv[j]$ ，这一定是一个前缀，随着 $j$ 变大右端点逐渐左移，那就可以用双指针维护这个区间，同时用一个桶记录区间中每个值的出现次数，随着左右端点的移动不断变化，就可以统计出对于每个 $j$ 有多少个合法的 $i$ 了，另一个方向的同理。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cctype>

#include<cstring>

using namespace std;

#define R register

inline int rd()

{

	R int res = 0,f = 1;

	R char c = getchar();

	while(!isdigit(c))

	{

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

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n;

#define MAXN 1000010

int a[MAXN];

long long ans = 0;

int mxl[MAXN],mxr[MAXN],mnl[MAXN],mnr[MAXN];

map<int,int> basket;

void solve(int l,int r)

{

	if(l == r)

	{

		++ans;

		return;

	}

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

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

	mxl[mid + 1] = mxr[mid] = 0xc0c0c0c0;

	mnl[mid + 1] = mnr[mid] = 0x3f3f3f3f;

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

	{

		mxl[i] = max(a[i],mxl[i + 1]);

		mnl[i] = min(a[i],mnl[i + 1]);

	}

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

	{

		mxr[i] = max(a[i],mxr[i - 1]);

		mnr[i] = min(a[i],mnr[i - 1]);

	}

	//max = maxv[i],min = minv[i] : maxv[i] - minv[i] = i - j

	long long sum = 0;

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

	{

		int j = i - (mxr[i] - mnr[i]);

		if(l <= j && j <= mid && max(mxr[i],mxl[j]) == mxr[i] && min(mnr[i],mnl[j]) == mnr[i])++sum;

	}

	//max = maxv[j],min = minv[j] : maxv[j] - minv[j] = i - j;

	for(int j = mid;j >= l;--j)

	{

		int i = (mxl[j] - mnl[j]) + j;

		if(mid + 1 <= i && i <= r && max(mxr[i],mxl[j]) == mxl[j] && min(mnr[i],mnl[j]) == mnl[j])++sum;

	}

	basket.clear();

	//max = maxv[i],min = minv[j] : maxv[j] < maxv[i] && minv[j] < minv[i]  maxv[i] - minv[j] = i - j

	for(int i = mid + 1,j1 = mid + 1,j2 = mid;i <= r;++i)

	{

		while(mxl[j1 - 1] < mxr[i] && j1 > l)--j1,++basket[j1 - mnl[j1]];

		while(mnl[j2] > mnr[i] && j2 >= j1)--basket[j2 - mnl[j2]],--j2;

		sum += basket[i - mxr[i]];

	}

	basket.clear();

	//max = maxv[j],min = minv[i] : maxv[i] < maxv[j] && minv[i] < minv[j] maxv[j] - minv[i] = i - j

	for(int i = mid + 1,j1 = mid + 1,j2 = mid;i <= r;++i)

	{

		while(mnl[j1 - 1] > mnr[i] && j1 > l)--j1,++basket[mxl[j1] + j1];

		while(mxl[j2] < mxr[i] && j2 >= j1)--basket[mxl[j2] + j2],--j2;

		sum += basket[i + mnr[i]];

	}

	ans += sum;

	return;

} 

int main()

{

	scanf("%d",&n);

	int x,y;

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

	{

		x = rd();y = rd();

		a[x] = y;

	}

	solve(1,n);

	cout << ans << endl;

	return 0;

}

In tag: 算法-分治

wjh15101051