CF961E Tufurama 题解

二维数点做法

题意

  给定长度为 \(n\) 的序列 \(a\)，统计二元组 \((i,j)\) 的个数，使得该二元组满足 \(1 \leq i < j \leq n, a_i \geq j, a_j \geq i\)。\(n\) 在 \(2 \times 10^{5}\) 级别，\(a_i\) 在 \(1 \times 10^{9}\) 级别。

思路分析

  我们考虑把序列中 \(n\) 个元素看成 \((i,a_i)\) 坐标的点，至于平面直角坐标系中。我们先忽略“\(1 \leq i < j \leq n\)”的条件。可以发现，对于某一个 \(i\)，我们要统计的是所有的 \(j\) 中满足 \(j \leq a_i, a_j \geq i\) 的点的个数，也就是横坐标小于等于当前点、纵坐标大于等于当前点的点的个数。画出图就是下面的样子：

  至于具体怎么处理数点过程，我们按照先横坐标再纵坐标的方式对于点排序。然后我们可以把每个询问 \((a_i,i)\) 做排序，代表查询横坐标小于等于 \(a_i\)，纵坐标大于等于 \(i\) 的点的个数。我们横坐标从小到大一列一列地统计点（即一根扫描线在 x 轴上从小往大扫），用树状数组维护纵坐标上离散化过后的每个位置的已统计点的点数前缀和，统计纵坐标大于等于 \(i\) 的区间内的点数，就可以知道对应的答案了。

  那么我们怎么处理 \(1 \leq i < j \leq n\) 的条件呢？首先我们考虑在的统计中，出现的 \(i = j\) 的情况，可以发现，如果这样的情况被统计到了，（代入条件可得）就会满足 \(a_i \geq i, a_i \geq i\)，于是我们直接在序列上遍历统计 \(a_i \geq i\) 的个数，在总统计答案中减掉就行。

  然后就是 \(i < j\) 的条件如何处理，我们发现 \(a_i \geq j, a_j \geq i\) 和 \(a_j \geq i, a_i \geq j\)(即交换 \(i,j\) 后)是等效的，也就是说每一个满足条件的点对被统计了两遍。于是我们在刚刚的基础上，把统计答案除以二，就得到了正确结果。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 5e5 + 5;
const int M = 5e5 + 5;

int n,m;
int a[N];
int ycnt;

int qcnt;
int yrk[N];

struct quest
{
	int x,y;
}que[N*2];

int ans[N];

bool cmp1(quest xx,quest yy)
{
	return xx.x < yy.x;
}

int t[N];

int lowbit(int xx)
{
	return xx & (-xx);
}

void add(int pos,int k)
{
	for(int i = pos;i <= ycnt;i += lowbit(i))
		t[i] += k;
}

int ask(int pos)
{
	int ans = 0;
	for(int i = pos;i >= 1;i -= lowbit(i))
		ans += t[i];
	return ans;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	LL samecnt = 0;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
		if(a[i] >= i)
			samecnt++;
		yrk[i] = a[i];
		que[++qcnt] = {a[i],i};
	}
	sort(que+1,que+1+n,cmp1);
	sort(yrk+1,yrk+1+n);
	ycnt = unique(yrk+1,yrk+1+n)-1-yrk;
	int idx = 1;
	LL ans = 0;
	for(int i = 1;i <= n;i++)
	{
		while(idx <= que[i].x && idx <= n)
		{
			int tmpidx = lower_bound(yrk+1,yrk+1+ycnt,a[idx])-yrk;
			add(tmpidx,+1);
			idx++;
		}
		int tmpfd = lower_bound(yrk+1,yrk+1+ycnt,que[i].y)-yrk-1;
		ans += (LL)(ask(ycnt)-ask(tmpfd));
	}
	ans -= samecnt;
	ans /= 2;
	cout << ans << "\n";
	return 0;
}