本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-03-10 19:05:33

看题解里没有权值线段树的，就交上来了

众所周知

权值线段树可以做许多事，比如全局 kth，有多少比他大的等。

而我们要实现的操作就是有多少比他大的加上插入。

插入十分简单，只要判断在左边还是右边然后递归进去就好了；而查询有多少比它大的，其实就是查询 $a_{i}+1$ 到 $max_{a_i}$ 中有多少数就可以了。

下面给出代码，其实不用动态开点

#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <climits>
#define int long long
using namespace std;
int n,tree[40000005],lll[40000005],rrr[40000005],a[5*100005],rt=1,t;
int cnt=1;
int ans;
#define ls(x) lll[x]
#define rs(x) rrr[x]
int query(int l,int r,int root,int ll,int rr) {
	if(root==0)return 0;
	if(tree[root]==0)return 0;
	if(l>=ll&&r<=rr)
		return tree[root];\/\/运用到一个线段树的小技巧，如果完全包含就直接返回
	int mid=(l+r)>>1,ans=0;
	\/\/判断
	if(ll<=mid)
		ans+=query(l,mid,ls(root),ll,rr);
	if(rr>mid)
		ans+=query(mid+1,r,rs(root),ll,rr);
	return ans;
}
void insert(int l,int r,int &root,int k) {
	if(!root)root=++cnt;
	if(l==r) {
		++tree[root];\/\/插入
		return ;
	}
	int mid=(l+r)>>1;
   \/\/判断
	if(k<=mid)
		insert(l,mid,ls(root),k);
	else
		insert(mid+1,r,rs(root),k);
   \/\/回溯
	tree[root]=tree[ls(root)]+tree[rs(root)];
}
signed main() {
	cin>>t;
	while(t--) {
		memset(tree,0,sizeof(tree));
		memset(lll,0,sizeof(lll));
		memset(rrr,0,sizeof(rrr));
		ans=0;
		rt=cnt=1;
		cin>>n;
		for(int i=1; i<=n; ++i)
			cin>>a[i];
		for(int i=1; i<=n; ++i) {
			ans+=query(-1e7,1e7,rt,a[i]+1,1e7);\/\/查询
			insert(-1e7,1e7,rt,a[i]);\/\/插入
		}
		cout<<ans<<endl;
	}

	return 0;
}