Pudding Monsters CodeForces - 526F (分治, 双指针)

大意: n*n棋盘, n个点有怪兽, 求有多少边长为k的正方形内恰好有k只怪兽, 输出k=1,...,n时的答案和.

等价于给定n排列, 对于任意一个长为$k$的区间, 若最大值最小值的差恰好为k, 则产生1贡献, 求贡献和.考虑分治, 问题就转化为如何$O(n)$求出跨越$mid$的贡献, 可以讨论最大值最小值的位置, 双指针求出.

#include <iostream>

#include <algorithm>

#include <cstdio>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

using namespace std;

typedef long long ll;

const int N = 1e6+10;

int n, a[N], mx[N], mi[N];

int ff[N<<1], *f=ff+N;

ll ans;

void solve(int l, int r) {

	if (l==r) return ++ans,void();

	int mid = l+r>>1;

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

	mx[mid]=mi[mid]=a[mid];

	mx[mid+1]=mi[mid+1]=a[mid+1];

	REP(i,mid+2,r) mx[i]=max(mx[i-1],a[i]),mi[i]=min(mi[i-1],a[i]);

	PER(i,l,mid-1) mx[i]=max(mx[i+1],a[i]),mi[i]=min(mi[i+1],a[i]);

	int L = mid, R = mid;

	REP(i,mid+1,r) {

		int j=i-mx[i]+mi[i];

		if (l<=j&&j<=mid&&mx[j]<mx[i]&&mi[j]>mi[i]) ++ans;

		while (L>=l&&mx[L]<mx[i]) ++f[mi[L]-L],--L;

		while (R>L&&mi[R]>mi[i]) --f[mi[R]-R],--R;

		ans += f[mx[i]-i];

	}

	while (R!=L) --f[mi[R]-R],--R;

	L = R = mid+1;

	PER(i,l,mid) {

		int j=mx[i]-mi[i]+i;

		if (mid+1<=j&&j<=r&&mx[j]<mx[i]&&mi[j]>mi[i]) ++ans;

		while (R<=r&&mx[R]<mx[i]) ++f[mi[R]+R],++R;

		while (L<R&&mi[L]>mi[i]) --f[mi[L]+L],++L;

		ans += f[mx[i]+i];

	}

	while (L!=R) --f[mi[L]+L],++L;

}

int main() {

	scanf("%d", &n);

	REP(i,1,n) {

		int x, y;

		scanf("%d%d", &x, &y);

		a[x] = y;

	}

	solve(1,n);

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

}