P1908 逆序对

P1908 逆序对

跟用树状数组求如出一辙，但是它可以不离散化直接求解，因为它可以直接把区间传到函数里，正负无所谓，反正是动态开点，此题作为动态开点的演示。

这种线段树十分耗费空间。

#include<iostream>
using namespace std;
const int M=15000010,INF=1e9;//M是理论值，远远达不到
int n,v[M],rt,l[M],r[M],idx;
typedef long long ll;
ll ans;
void pushup(int p){
	v[p]=v[l[p]]+v[r[p]];
}
int query(int &p,int ql,int qr,int L,int R){
	if(!p)p=++idx;
	if(ql<=L&&R<=qr)return v[p];
	int mid=L+R>>1,res=0;
	if(ql<=mid)res=query(l[p],ql,qr,L,mid);
	if(qr>mid)res+=query(r[p],ql,qr,mid+1,R);
	return res;
}
void modify(int &p,int L,int R,int x){
	if(!p)p=++idx;
	if(L==R){
		++v[p];
		return;
	}
	int mid=L+R>>1;
	if(x<=mid)modify(l[p],L,mid,x);
	else modify(r[p],mid+1,R,x);
	pushup(p);
}
int main(){
	#ifdef LOCAL
	freopen("1.txt","r",stdin);
	#endif
	#ifndef LOCAL
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	#endif
	cin>>n;
	for(int i=1;i<=n;++i){
		int a;
		cin>>a;
		ans+=query(rt,a+1,INF,1,INF);
		modify(rt,1,INF,a);
	}
	cout<<ans;
	return 0;
}