【codevs4163】 hzwer与逆序对(树状数组+离散化)

xiaoxiao2021-02-28  124

Description

    hzwer在研究逆序对。对于数列{a},如果有序数对(I,j)满足:i < j,a[i] > a[j],则(i,j)是一对逆序对。给定一个数列{a},求逆序对个数。     输入数据较大,请使用scanf代替cin读入。     *为防卡评测,时限调低至1s

Input

    第一行一个数n,表示{a}有n个元素。接下来n个数,描述{a}。

Output

    一个数,表示逆序对个数。

Sample Input

5 3 1 5 2 4

Sample Output

4

Data

对于10%数据,1<=n<=100. 对于20%数据,1<=n<=10000. 对于30%数据,1<=n<=100000. 对于100%数据,1<=n<=1000000,1<=a[i]<=10^8.

I think

    本意是权值线段树求逆序对的模板,然而线段树TLE六个点相较之下树状数组跑得飞起。

Code

#include<cstdio> #include<algorithm> #define lowbit(x) x&(-x) using namespace std; typedef long long ll; const int sm = 1e6+50; int n,t; ll s,ans,tot[sm]; struct lsh { ll val;int a,b; }x[sm]; char ch; template <typename T> void read(T &x) { x=0,ch=getchar(); while(ch>'9'||ch<'0') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } bool ca(lsh x,lsh y) { return x.val<y.val; } bool cb(lsh x,lsh y) { return x.a<y.a; } ll query(int x) { s=0; for(int i=x;i;i-=lowbit(i)) s+=tot[i]; return s; } void add(int x,int y) { for(int i=x;i<=n;i+=lowbit(i)) tot[i]=1ll*(tot[i]+y); } int main() { read(n); for(int i=1;i<=n;++i) read(x[i].val),x[i].a=i; sort(x+1,x+n+1,ca); for(int i=1;i<=n;) { while(x[i].val==x[i-1].val) x[i].b=x[i-1].b,++i; x[i++].b=++t; }//处理元素相同的情况 sort(x+1,x+n+1,cb); for(int i=1;i<=n;++i) { //树状数组单点修改区间查询 ans+=query(t)-query(x[i].b); add(x[i].b,1); } printf("%lld\n",ans); return 0; }
转载请注明原文地址: https://www.6miu.com/read-38346.html

最新回复(0)