Educational Codeforces Round 41 (Rated for Div. 2) E. Tufurama（树状数组+偏序）

题目链接

题意：给定一个数组，要求你满足a【i】>=j&&a【j】>=i(i<j）的i，j对的数量。
思路：用我们用树状数组来维护a【j】>=i的数量，只要在【i+1，a【i】】这个区间查询就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(i)  (i)&(-i)
const int maxn=2e5+1; 
map<int,int>p;
vector<int>q[maxn];
int c[maxn];
pair<int,int>a[maxn],b[maxn];
void update(int x,int val)
{
	while(x<maxn) c[x]+=val,x+=lowbit(x);
}
ll query(int x)
{
	ll res=0;
	while(x>0) res+=c[x],x-=lowbit(x);
	return res;
}
int main()
{
	int n;
	ll ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i].first),a[i].second=i,b[i]=a[i]; 
	sort(b+1,b+1+n);
	int now=1;
	for(int i=1;i<n;++i)
	{
		a[i].first=min(a[i].first,n);
		b[i].first=min(b[i].first,n);
		if(a[i].first>a[i].second)
		{
			while(now<=n&&b[now].first>=i) 
		{
			if(b[now].second>i) 
			{
				update(b[now].second,1);
				p[b[now].first]=1;
				if(b[now].first<=n) q[b[now].first].push_back(b[now].second);
				//cout<<b[now].second<<" ";
			}
			now++;
		}
		//cout<<endl;
		//cout<<query(min(a[i].first,n))-query(i)<<endl;
		ans+=query(min(a[i].first,n))-query(i);
		}
		//cout<<"p[i]"<<p[i]<<endl;
			if(p[i]) 
			{
				for(auto it:q[i])
				update(it,-1);
				//update(i,-1),p[i]=0;
			}
	}
	printf("%lld\n",ans);
}