最接近神的人_NOI導刊2010提高（02）

用類似于桶的方法，樹狀數組記錄原序列的某位置之前已經插入了多少個數，

插入時樹狀數組單點加1即可

先排一遍序，從大到小插入所有數在原序列的位置，

統計每次插入時，在該元素前面元素的個數，

前面的元素是先插入的，比該元素大，而在序列中的位置靠前，

所以這個前綴和是逆序對數

#include<iostream> #include<algorithm> #include<cstdio> using namespace std; #define int long long #define lowbit(x) ((x)&(-(x))) #define MAXN 500020 inline int read(){int x=0,f=1; char c=getchar();while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); }while('0'<=c&&c<='9') { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }return x*f; } int n,tree[MAXN<<2]; struct NODE{int pos,value; } x[MAXN]; inline bool cmp(NODE x,NODE y){return x.value==y.value?x.pos<y.pos:x.value<y.value; } void update(int x){for(;x<=n;x+=lowbit(x))tree[x]++; } int query(int x){int ans=0;for(;x;x-=lowbit(x))ans+=tree[x];return ans; } #undef int int main() #define int long long {scanf("%lld",&n);for(int i=1;i<=n;i++){x[i].value=read();x[i].pos=i;}sort(x+1,x+1+n,cmp);int ans=0;for(int i=n;i>=1;i--){ans+=query(x[i].pos);update(x[i].pos);}printf("%lld\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/yjkhhh/p/9261629.html

總結

以上是生活随笔為你收集整理的【洛谷P1774】最接近神的人的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。