SP6256

崔化博 · 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;
}