80分 树状数组
查看原帖
80分 树状数组
1351126
General0826楼主2024/5/5 21:32
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
long long n;
long long cnt=0;
long long a[N],h[N],l=1;
struct node
{
	int x,id;
}b[N];
bool cmp(node q,node h)
{
	return q.x<h.x;
}
int lowbit(int x)
{
	return x&(-x);
}
void gai(int i,int x)
{
	if(i==0) return ;
	for(;i<=n;i+=lowbit(i))
	{h[i]+=x;} 
		//
}
int find(int x)
{
	int cnt=0;
	for(int i=x;i!=0;i-=lowbit(i)) 
		cnt+=h[i];
	return cnt;
}
int main()
{
//	freopen("T2.out","w",stdout);
//	freopen("T2.in","r",stdin);
	cin>>n;
	for(int i=1;i<=n;i++) 
	{
		cin>>a[i];
		b[i].x=a[i];
		b[i].id=i;
	}
	for(int i=1;i<=n;i++)
		h[i]=lowbit(i);
	sort(b+1,b+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		cnt+=1ll*(max(find(min(n,a[i]))-find(i),0));
		while(i>=b[l].id&&l<n)
			gai(b[l++].id,-1);
	}	
	cout<<cnt;
	return 0;
}

2024/5/5 21:32
加载中...