带修主席树（树状数组套主席树）

绝地灬酷狼 2024-04-18 21:36 68阅读 0赞

今天上课，，很是无聊，所以，手写了一个模板题，但是常数有点大，，

可能结构体都是这个样子吧，，虽然简单，但是常数大。

### 题目描述 ###

对于序列A，它的逆序对数定义为满足i<j，且Ai>Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

### 输入格式 ###

输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行一个正整数，依次为每次删除的元素。

### 输出格式 ###

输出包含m行，依次为删除每个元素之前，逆序对的个数。

### 输入输出样例 ###

**输入 \#1**复制

5 4
    1
    5
    3
    4
    2
    5
    1
    4
    2

**输出 \#1**复制

5
    2
    2
    1
    
    样例解释
    (1,5,3,4,2)(1,3,4,2)(3,4,2)(3,2)(3)。

### 说明/提示 ###

N<=100000 M<=50000

#include<bits/stdc++.h>
    using namespace std;
    const int M=1e5+50;
    struct Node{int l,r,sum;}t[M*210];
    int pos[M],n,m,rt[M],d[M],cnt,t0[M];
    long long res;
    void add(int &now,int l,int r,int pos,int v){
        if(!now)now=++cnt;
        t[now].sum+=v;
        if(l==r)return ;
        int mid=(l+r)>>1;
        if(pos<=mid)add(t[now].l,l,mid,pos,v);
        if(mid<pos)add(t[now].r,mid+1,r,pos,v);
    }
    void Add(int x,int pos,int v){
        while(x<=n){
            add(rt[x],1,n,pos,v);
            x+=(x&-x);
        }
    }
    long long ask(int x,int ll,int rr,int l,int r){
        if(l>r||!x)return 0;
        if(l<=ll&&rr<=r)return t[x].sum;
        int mid=(ll+rr)>>1;
        long long ans=0;
        if(l<=mid)ans+=ask(t[x].l,ll,mid,l,r);
        if(mid<r)ans+=ask(t[x].r,mid+1,rr,l,r);
        return ans;
    }
    long long Ask(int x,int l,int r){
        long long ans=0;
        while(x>0){
            ans+=ask(rt[x],1,n,l,r);
            x-=(x&-x);
        }
        return ans;
    }
    void query(int x){
        res-=Ask(pos[x]-1,x+1,n);
        res-=Ask(n,1,x-1)-Ask(pos[x],1,x-1);
    }
    void add0(int x){  while(x<=n) t0[x]++,x+=(x&-x);}
    long long sum0(int x){long long ans=0; while(x){ ans+=t0[x]; x-=(x&-x);} return ans;}
    
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%d",&d[i]),Add(i,d[i],1),pos[d[i]]=i;
    
        for(int i=1;i<=n;i++) res+=i-1-sum0(d[i]),add0(d[i]);
    
        for(int x,i=1;i<=m;i++){
            printf("%lld\n",res);
            scanf("%d",&x);
            query(x);
            Add(pos[x],x,-1);
        }
        return 0;
    }