BIT 응용 역순 대 POJ 2299

3712 단어 데이터 구조 
/*
    POJ2299 BIT+   
    by sbn
    2018-1-12

*/
/*  
    5
9
1
0
5
4
3
1
2
3
0
*/
#include
#include
#include
#include
#include
#include
#define pb push_back
using namespace std;
typedef vector<int> vi;
vi Hash;
const int MAXN=5e5+10;
int C[MAXN],n,m,a[MAXN],b[MAXN];
int lowbit(int x){
 return x & -x;
}
void add(int x,int num){
 for (int i1=x;i1<=n;i1+=lowbit(i1))
 C[i1]+=num;
}
int getsum(int x){
 int ans1=0;
 for(int j=x;j>0;j-=lowbit(j))
 ans1+=C[j];
 return ans1;
}
inline void hash_init(){
    Hash.clear();
    for (int i=1;i<=n;i++)
        Hash.pb(a[i]);
    sort(Hash.begin(),Hash.end());
    Hash.erase(unique(Hash.begin(),Hash.end()),Hash.end());
}
inline void hash_main(){
hash_init();
for (int i=1;i<=n;i++)
b[i]=lower_bound(Hash.begin(),Hash.end(),a[i])-Hash.begin()+1;
}
int main(){
    while(cin>>n){
    if (n==0)   break;
    for (int i=1;i<=n;i++)
        cin>>a[i]; 
    hash_main();
    long long ans=0;
    memset(C,0,sizeof(C));
    for (int i=1;i<=n;i++)
        {
            add(b[i],1);
            ans+=i-getsum(b[i]);
        }
    cout<return 0;
}
CF369E Valera and Queries kdtree
균형 이 진 트 리 의 실현

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage