题解 P6278 【[USACO20OPEN]Haircut G】

LlLlCc · 2020-09-26 13:14:03 · 题解

看到神仙PanH写了主席树题解，也来看看这题

把所有大于j的数降为j再求全局逆序对就等于先求出全局逆序对再减去两个大于等于j的数之间的逆序对即可

所有只要求逆序对时记一下逆序对的差分数组就行，代码很短

code

#include<bits/stdc++.h>
#define maxn 2000005
#define ll long long
using namespace std;
const int N=2e5;
int n,a[maxn],c[maxn];
ll Ans,g[maxn];
inline int read(){
    int ret=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
    return ret;
}
inline void add(int x){for (;x<=N;x+=x&-x) c[x]++;}
inline int Get(int x){int sum=0;for (;x;x-=x&-x) sum+=c[x];return sum;}
int main(){
    n=read();
    for (int i=1;i<=n;i++) a[i]=read()+1;
    for (int i=1,x;i<=n;i++) x=i-1-Get(a[i]),g[a[i]]+=x,add(a[i]);
    for (int i=0;i<n;i++) Ans+=g[i],printf("%lld\n",Ans);
    return 0;
}