CF961E Solution

题目链接

题解

下文将符合题意的数对成为“逆数对”。

可以发现，\(x=a_i\)的逆数对个数为满足\(i<j\le a_i,a_j\ge i\)的\(j\)个数，因为\(j\)的季数需\(\le i\)的最大集数，而其最大集数需\(\ge i\)的季数。对于第一个条件，可以将\(j\)存入树状数组，每次取区间\([i+1,a_i]\)和即可。因为由\(1\)到\(n\)遍历\(a\)数组时\(i\)单调递增，可以设数组\(b\)为增序排序后的\(a\)，当\(b\)数组当前左端点元素\(\le i\)时便将该元素从树状数组中删除，并将左端点右移。

#include<bits/stdc++.h>
#define int long long
#define lowb(x) x&(-x) 
using namespace std;
const int N=2e5+10;
struct node {int v,id;} b[N];//v:a数组增序排序的值,id:v在a数组中下标
int t[N],a[N],n; 
bool cmp(node a,node b) {return a.v<b.v;}
void add(int x,int d)
{
	while(x<=n) {t[x]+=d; x+=lowb(x);}
}
int query(int x)
{
	int ans=0;
	while(x) {ans+=t[x]; x-=lowb(x);}
	return ans;
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) 
	{
		scanf("%lld",&a[i]); add(i,1);//将j加入树状数组
		b[i].v=a[i]; b[i].id=i;
	}
	sort(b+1,b+n+1,cmp);
	int pos=0,ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=max(0ll,query(min(a[i],n))-query(i));//统计答案
		while(b[++pos].v<=i && pos<=n) add(b[pos].id,-1);//删除不合法a[j]
		pos--;//当前pos为合法下标，需-1
	}
	printf("%lld",ans);
	return 0;
}