权值线段树

权值线段树应用

普通的线段树的节点维护代表区间中存储的数组和，而权值线段树的节点是维护数组中出现在代表区间内的元素的次数。

权值线段树基本作用：查找数组中第k大的元素

注意：权值线段树只是一个思想，一般需要根据题目对其意义加以改进

那么普通的线段树的叶节点 [x,x] 记录的就是数组中 a[x] 的大小，而权值线段树的叶节点 [x,x] 记录的就是数组中大小为 x 的元素个数

权值线段树模板

和线段树结构相同，只不过节点的权值记录的意义不相同而已。不过由于数组的值域，通常会采用现将数组离散化再建立对应的权值线段树来节省空间的白白浪费。当然还可以动态开点建树。

模板题1：在一个含有 1-n 的序列中，每次找到第 Ki 小的数，并把它删除。第一个数 T ，表示测试数据的组数。每组测试数据，第一行 2 个整数 n 和 m ， m 表示操作的轮数。接下来m行，每行一个整数 k ，表示要找出第 k 小的数，并把它删除。每组数据，输出一个整数，表示删除元素的总和。

//未离散化的查找第k大+区间求和
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;

int cnt=0;//统计样例次数
struct node{
    int l,r,sum;
}tree[maxn<<2];

void pushup(int rt){//更新父节点
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}

void build(int rt,int l,int r){//建立空树
    tree[rt].l=l,tree[rt].r=r;
    if(tree[rt].l==tree[rt].r){
        tree[rt].sum=0;
        return ;
    }
    int mid=l+r>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}

void update(int rt,int id,int score){//将大小为id的个数加上score权值
    if(tree[rt].l==tree[rt].r){
        tree[rt].sum+=score;
        return ;
    }
    if(id<=tree[rt<<1].r)update(rt<<1,id,score);
    else update(rt<<1|1,id,score);
    pushup(rt);
}

int query(int rt,int k){//查询第k大的数
    if(tree[rt].l==tree[rt].r)return tree[rt].l;
    int mid=tree[rt].l+tree[rt].r>>1;
    if(tree[rt<<1].sum>=k)return query(rt<<1,k);
    else return query(rt<<1|1,k-tree[rt<<1].sum);
    //转变为在右子树找第k-左子树元素个数的数
}

/*int query(int rt,int l,int r){//查询[l,r]区间内元素的个数
    if(l<=tree[rt].l&&r>=tree[rt].r)return tree[rt].sum;
    int lc=rt<<1,rc=rt<<1|1;
    int mid=tree[rt].l+tree[rt].r>>1;
    int ans=0;
    if(l<=mid)ans+=query(lc,l,r);
    if(r>mid)ans+=query(rc,l,r);
    return ans;
}*/

void solve(){
    int n,m;
    cin>>n>>m;

    build(1,1,n);

    for(int i=1;i<=n;i++)//初始1~n的个数都是1，其实这个步骤可以放在建树中
    update(1,i,1);

    ll ans=0;//记录删除的数
    while(m--){
        int k;cin>>k;
        int tot=query(1,k);//找到第k大的数
        ans+=tot;
        update(1,tot,-1);//将第k大的数个数-1
    }
    cout<<"Case "<<++cnt<<": "<<ans<<endl;
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

模板题2：给你一个序列对于每个 i ，你可以选择 1~i-1 中任意多的数并将它删去，剩余的数（包括 i ）和 ≤m ，问对于每个 i 最少删几个数可以达到要求

思路：可以转变思维即要求用在 1~i-1 的元素尽量多的个数去凑 m-a[i]（小于等于尽量靠近）。现将数组离散化然后存入权值线段树，权值线段树既要统计区间内元素的个数还要统计其元素总和

//离散化权值线段树
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;

struct Tree{
    int l,r,tot;//左右区间，元素个数
    ll sum;//区间内元素的和
}tree[maxn<<2];

int n,m;//n个数,边界数m
int len,p;//离散后数组长度,元素离散后的值
ll a[maxn],b[maxn];

void pushup(int rt){//更新父节点
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
    tree[rt].tot=tree[rt<<1].tot+tree[rt<<1|1].tot;
}

void build(int rt,int l,int r){//建立空树
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].tot=0;
    tree[rt].sum=0;
    if(l==r)return ;
    int mid=l+r>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    pushup(rt);
}

void update(int rt,int l,int r){//更新区间内信息
    if(l==r){
        tree[rt].tot++;
        tree[rt].sum+=b[p];
        return ;
    }
    int mid=l+r>>1;
    if(p<=mid)update(rt<<1,l,mid);
    else update(rt<<1|1,mid+1,r);
    pushup(rt);
}

int query(int rt,int l,int r,ll k){//查询元素和满足小于等于k的区间并返还最多用到的元素个数（优先用左区间内的数去凑）
    if(tree[rt].sum<=k)return tree[rt].tot;
    if(l==r)return min(tree[rt].tot,(int)(k/b[l]));//说明就要用当前的数来凑
    int mid=l+r>>1;
    if(k<=tree[rt<<1].sum)return query(rt<<1,l,mid,k);//说明用做区间内的元素去凑
    else return tree[rt<<1].tot+query(rt<<1|1,mid+1,r,k-tree[rt<<1].sum);//说明左区间的数全用,还要在用又区间的一些数凑
}

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i],b[i]=a[i];

    //离散化
    sort(b+1,b+1+n);
    len=unique(b+1,b+1+n)-b-1;
    build(1,1,len);//注意；离散化后区间不再是值域范围，而是离散化的数处于b区间内第l大的数和第r大的数

    for(int i=1;i<=n;i++){
        //现在之前的线段树中找1~i-1可以组成的最大数所用的最大数量
        if(i==1){
            cout<<0<<" ";
        }
        else cout<<i-1-query(1,1,len,m-a[i])<<" ";//获得至少需要减去的元素个数
        //然后在将现在的节点插入到线段树中为下次做准备
        p=lower_bound(b+1,b+1+n,a[i])-b;
        update(1,1,len);
    }
    cout<<endl;
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

权值线段树应用：求逆序对

树状数组都可以求逆序对，线段树作为另一种区间查询的数据结构当然也可以用来求逆序对

前言：逆序对是一个经典的问题，树状数组和权值线段树的求法都应该领悟

做法：和树状数组的方法类似，这里还是利用权值线段树区间统计个数的性质。思路是将离散化后的自然数序列中的数逐个插入（插入的数字所在的区间更新 +1 ）。设插入的数字是原序列的第 i 个数：

• 可以插入前使用线段树查询 [a[i],n] 和（也就是相当于查询该数前面比它大的逆序对），然后再将该数插入线段树（利用线段树的性质还可这样做），即 sum+=query(1,a[i],n),update(1,a[i],1)

先查询再插入，因为是查找之前的数和该数能组成逆序对的，插入再查询就把自己给算进去了

• 或者先将数插入线段树，然后查询 [1,a[n]]（也就是查询不满足逆序对的数），利用本身减去位置减去前面个数比它小的数和本身（树状数组的方法，线段树也可以实现），即 update(1,a[i],1),sum+=i-query(1,1,a[i])

先插入在查询，因为这里是找不能组成逆序对的数，所以要把自身算进去

//权值线段树求逆序数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e3+5;

int a[maxn],b[maxn];
struct Tree{
    int l,r,sum;
}tree[maxn<<2];

void pushup(int rt){
    int lc=rt<<1,rc=rt<<1|1;
    tree[rt].sum=tree[lc].sum+tree[rc].sum;
}

void build(int rt,int l,int r){
    tree[rt].l=l,tree[rt].r=r;
    if(l==r){
        tree[rt].sum=0;
        return ;
    }
    int mid=(l+r)>>1;
    int lc=rt<<1,rc=rt<<1|1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushup(rt);
}

void update(int rt,int id,int score){
    if(tree[rt].l==tree[rt].r){
        tree[rt].sum+=score;
        return ;
    }
    int lc=rt<<1,rc=rt<<1|1;
    int mid=tree[rt].l+tree[rt].r>>1;
    if(id<=mid)update(lc,id,score);
    else update(rc,id,score);
    pushup(rt);
}

int query(int rt,int l,int r){
    if(l<=tree[rt].l&&r>=tree[rt].r)return tree[rt].sum;
    int lc=rt<<1,rc=rt<<1|1;
    int mid=tree[rt].l+tree[rt].r>>1;
    int ans=0;
    if(l<=mid)ans+=query(lc,l,r);
    if(r>mid)ans+=query(rc,l,r);
    return ans;
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int n;
    while(cin>>n&&n){
        memset(tree,0,sizeof tree);
		for(int i=1;i<=n;i++)
		cin>>a[i],b[i]=a[i];

        sort(b+1,b+1+n);
        //获得离散后序列长度，其实这步没必要因为要求排列的逆序对已经默认无重复
		int len=unique(b+1,b+1+n)-b-1;

        for(int i=1;i<=n;i++){
            a[i]=lower_bound(b+1,b+1+len,a[i])-b;//获得离散的值
        }

        ll ans=0;//记录器
        build(1,1,len);
        for(int i=1;i<=len;i++){
            ans+=query(1,a[i],len);//求比它大的数的个数
            update(1,a[i],1);
        }
		cout<<ans<<endl;
    }
    return 0;
}
/*
5
5 3 2 4 1
输出：8
*/

模板题：输入一个整数 n ，接下来随意顺序输入 0 到 n-1 之间的数，然后你可以将每一串这样的数的第一个数移到最后一位去，形成新的数字串。要求你输出这样的操作得到的不同数字串中逆序数的最小个数

如 0 3 4 1 2 ，该序列逆序数为 n=2+2=4 。其根据题意移动产生的序列有(每次将数组第一个数移到末尾)

排列	逆序对
3 4 1 2 0	8
4 1 2 0 3	6
1 2 0 3 4	2
1 2 0 3 4	4

所以排列的最小逆序数为 2

思路：在寻找逆序对的基础上做了变式，要求求出 1~n 任意排列中的最小逆序对。这里有一个规律可以根据初始自然数排列列的逆序对找出最小逆序对：引用上面的例子

排列	逆序对
3 4 1 2 0	8
4 1 2 0 3	6

3 后面比 3 小的数有 1 2 0 ，所以逆序对为 t=3 ，比 3 大的数只有 4 ，所以顺序对为 1 ，即 顺序对=n-1-t(n表示序列中数字的总个数) ，当 3 移到末尾顺序对变为逆序对，逆序对变为顺序对，所以要在原来排列的逆序对 k 基础上减去该数原来的逆序对加上原来的顺序对，现在的逆序数=k+(n-1-t)-t=k+n-2t-1

//树状数组做法
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e3+5;

int n;
int a[maxn];//离散化后的数组
int c[maxn];//树状数组

int lowbit(int i){
	return i&(-i);
}

void update(int i,int k){
	while(i<=n){
		c[i]+=k;
		i+=lowbit(i);
	}
}

int getsum(int i){
	int res=0;
	while(i>0){
		res+=c[i];
		i-=lowbit(i);
	}
	return res;
}


signed main(){
	while(cin>>n&&n){
		//树状数组求逆序
        //不用离散化，题目保证0~n-1,可以直接利用上述规律
        for(int i=1;i<=n;i++){
            cin>>a[i];
            a[i]++;//树状数组只能从1开始，所以这里必须+1
        }
		memset(c,0,sizeof(c));
		long long tot=0;//要是处理很多数，即使离散化了也很可能超出int范围
        for(int i=1;i<=n;i++){
            update(a[i],1);//插入
            tot+=(i-getsum(a[i]));//求当前数的逆序数
        }
        long long ans=tot;
        for(int i=1;i<=n;i++){
            tot=tot+n-2*a[i]+1;//将a[i]扔到后面变化，因为排列从0开始，所以第i个数的逆序对就是本身的值a[i]
            ans=min(tot,ans);
        }
		cout<<ans<<endl; 
	}
	return 0;
}

//权值线段树做法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e3+5;

int n;
int a[maxn];
struct Tree{
    int l,r,sum;
}tree[maxn<<2];

void pushup(int rt){
    int lc=rt<<1,rc=rt<<1|1;
    tree[rt].sum=tree[lc].sum+tree[rc].sum;
}

void build(int rt,int l,int r){
    tree[rt].l=l,tree[rt].r=r;
    if(l==r){
        tree[rt].sum=0;
        return ;
    }
    int mid=(l+r)>>1;
    int lc=rt<<1,rc=rt<<1|1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushup(rt);
}

void update(int rt,int id,int score){
    if(tree[rt].l==tree[rt].r){
        tree[rt].sum+=score;
        return ;
    }
    int lc=rt<<1,rc=rt<<1|1;
    int mid=tree[rt].l+tree[rt].r>>1;
    if(id<=mid)update(lc,id,score);
    else update(rc,id,score);
    pushup(rt);
}

int query(int rt,int l,int r){
    if(l<=tree[rt].l&&r>=tree[rt].r)return tree[rt].sum;
    int lc=rt<<1,rc=rt<<1|1;
    int mid=tree[rt].l+tree[rt].r>>1;
    int ans=0;
    if(l<=mid)ans+=query(lc,l,r);
    if(r>mid)ans+=query(rc,l,r);
    return ans;
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    while(cin>>n&&n){
        memset(tree,0,sizeof tree);
        ll tot=0;
        build(1,1,n);
        for(int i=1;i<=n;i++){
            cin>>a[i];
            a[i]++;//这个随意:习惯从1开始
            tot+=query(1,a[i],n);//求比它大的数的个数
            update(1,a[i],1);
        }
        ll ans=tot;
        for(int i=1;i<=n;i++){
            tot=tot+n-2*a[i]+1;
            ans=min(ans,tot);
        }
        cout<<ans<<endl;
    }
    return 0;
}