传说中的大结论题TAT

假设每个数的后面小于它的数的个数为[tex]f[i][/tex]（其位置为[tex]i[/tex]），那么逆序对数显然为[tex]\Sigma f[i][/tex]。

每次操作，只需要将涉及到的数的[tex]f[i][/tex]清为0即可。

为什么呢？任何数的后面比他小的数肯定也被一起拉出来排序了，所以这些数的[tex]f[i][/tex]要被清零。其他数为什么不收这个影响呢？因为这之后的比他小的位置，有的可能没被操作，有的可能被操作了。但是就算被操作了，放到后面位置的数照样会比这个数小（因为这个数如果在第一个选定位置的后面（在前面更是不受影响）还没被操作，肯定比那个第一个位置数还大）。

还有一个细节，一个被操作过的数不需要再被操作一遍，操作完了直接设为INF即可。

代码：

/**************************************************************
    Problem: 3333
    User: danihao123
    Language: C++
    Result: Accepted
    Time:7920 ms
    Memory:24264 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <utility>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=500005;
const int maxnode=maxn*4;
const int INF=0x7fffffff;
int A[maxn];
pii minv[maxnode];
inline void maintain(int o){
    minv[o]=min(minv[o<<1],minv[o<<1|1]);
}
void build_tree(int o,int L,int R){
    if(L==R){
        minv[o]=make_pair(A[L],L);
    }else{
        int M=L+(R-L)/2;
        build_tree(o<<1,L,M);
        build_tree(o<<1|1,M+1,R);
        maintain(o);
    }
}
int ql,qr;
pii query_min(int o,int L,int R){
    if(ql<=L && R<=qr){
        return minv[o];
    }else{
        int M=L+(R-L)/2;
        pii ans=make_pair(INF,INF);
        if(ql<=M)
            ans=min(ans,query_min(o<<1,L,M));
        if(qr>M)
            ans=min(ans,query_min(o<<1|1,M+1,R));
        return ans;
    }
}
int p;
void update(int o,int L,int R){
    if(L==R){
        minv[o].first=INF;
    }else{
        int M=L+(R-L)/2;
        if(p<=M)
            update(o<<1,L,M);
        else
            update(o<<1|1,M+1,R);
        maintain(o);
    }
}
 
int lsh_siz;
int C[maxn];
inline int lowbit(int x){
    return x&(-x);
}
inline void add(int p){
    while(p<=lsh_siz){
        C[p]++;
        p+=lowbit(p);
    }
}
inline int sum(int p){
    int ans=0;
    while(p>0){
        ans+=C[p];
        p-=lowbit(p);
    }
    return ans;
}
 
inline int readint(){
    register int x;
    register char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[21];
template<typename T>
inline void putint(T x){
    register int i,p=0;
    if(!x){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(i=p-1;i>=0;i--)
        putchar(bf[i]+'0');
    putchar('\n');
}
int n;
int A2[maxn],f[maxn];
int main(){
    register int i,m,pos;
    register ull ans=0;
    pii temp;
    n=readint();
    m=readint();
    for(i=1;i<=n;i++){
        A[i]=readint();
        A2[i]=A[i];
    }
    sort(A2+1,A2+1+n);
    lsh_siz=unique(A2+1,A2+1+n)-A2-1;
    for(i=n;i>=1;i--){
        pos=lower_bound(A2+1,A2+1+lsh_siz,A[i])-A2;
        f[i]=sum(pos-1);
        ans+=f[i];
        add(pos);
    }
    putint(ans);
    build_tree(1,1,n);
    while(m--){
        pos=readint();
        ql=pos;
        qr=n;
        while(true){
            temp=query_min(1,1,n);
            if(temp.first>A[pos])
                break;
            p=temp.second;
            ans-=f[p];
            f[p]=0;
            update(1,1,n);
        }
        putint(ans);
    }
    return 0;
}

• 相关文章
• 全局相关文章