(Zj) b373: [福州19中]车厢重组 [逆序數對] [BIT]

http://zerojudge.tw/ShowProblem?problemid=b373

題目大意：求用bubble_sort需要交換的次數

其實就是逆序數對的數量(文章底部有challenge喔)

解法一：用分治法輕鬆 O(n lg n) 解決XDDD

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

typedef long long ll;

ll num[1000001];
ll tmp[1000001];
bool used[1000001];
ll sum;
int n;

void print_array(int l,int r) {
    for (int x=l;r>x;x++) cout << num[x] <<' ';
    cout <<endl;
}

void get_ans(int l,int r) {
    if (l+1==r) return;
    int mid=(l+r)/2;
    get_ans(l,mid);
    get_ans(mid,r);
    int L=l,R=mid,k=l;
    int times=0;
    long long tmpsum=0;
    /*cout << "In l = " << l << " ; r = " << r << endl;
    cout <<"Array : ";*/
    //print_array(l,r);
    while (L < mid || R < r) {

        if (L==mid) tmp[k++] = num[R++];
        else if (R==r) {
            if (used[L]!=true) sum+= num[L]*times + tmpsum;
            tmp[k++]=num[L++];
        }
        else if (num[L] <= num[R]) {
            if (used[L] == false) sum+= num[L]*times + tmpsum;
            tmp[k++]=num[L++];
        }
        else if (num[L] > num[R]) {
            times++;
            tmpsum+=num[R];
            if (used[L]==false) {
                sum+= num[L]*times + tmpsum;
                used[L]=true;
            }
            else {
                sum += num[L]+num[R];
            }
            tmp[k++]=num[R++];
        }
        //cout << "Sum = " <<  sum << endl;
        sum%=10000019;
    }
    for (int x=l;r>x;x++) {
        num[x]=tmp[x];
        used[x]=false;
    }
    
}



int main () {
    while (scanf("%d",&n) != EOF) {
        sum=0;
        for (int x=0;n>x;x++) {
            scanf("%d",&num[x]);
        }
        for (int x=0;1000001>x;x++) used[x]=false;
        get_ans(0,n);
        cout << sum <<endl;
    }
}

解法二：數值線段樹

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;

struct Node {
    Node* lc;
    Node* rc;
    int val;
    Node () {
        lc=rc=NULL;
        val=0;
    }
    void pull() {
        val=lc->val+rc->val;
    }
};

const int MAX_N = 100003;
int num[MAX_N];

Node* Build(int L,int R) {
    Node* node = new Node();
    if (L==R) {
        node->val=0;
        return node;
    }
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    node->pull();
    return node;
}

void modify(Node* node,int L,int R,int pos,int val) {
    if (L==R) {
        node->val+=val;
        return;
    }
    int mid=(L+R)>>1;
    if (pos<=mid) modify(node->lc,L,mid,pos,val);
    else modify(node->rc,mid+1,R,pos,val);
    node->pull();
    return;
}

int query(Node* node,int L,int R,int l,int r) {
    if (l>R || L>r )return 0;
    else if (l<=L && R<=r) return node->val;
    int mid=(L+R)>>1;
    return query(node->lc,L,mid,l,r) + query(node->rc,mid+1,R,l,r);
}

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        vector<int> v;
        for (int x=0;n>x;x++) {
            scanf("%d",&num[x]);
            v.push_back(num[x]);
        }
        sort(v.begin(),v.end());
        v.resize(unique(v.begin(),v.end()) - v.begin());
        int len=v.size();
        for (int x=0;n>x;x++) {
//            cout<<"x="<<x<<endl;
            num[x]=lower_bound(v.begin(),v.end(),num[x]) - v.begin();
        }
        Node* root=Build(0,len);
        int ans=0;
        for (int x=0;n>x;x++) {
//            cout<<"num["<<x<<"] = "<<num[x]<<endl;
            if (num[x]==len-1) {
                modify(root,0,len,num[x],1);
            }
            else {
                ans+=query(root,0,len,num[x]+1,len);
                modify(root,0,len,num[x],1);
            }
        }
        printf("%d\n",ans);
    }
}

解法三：BIT

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

struct BIT {
    vector<int> data;
    int n;
    void init(int _n) {
        n=_n;
        data.resize(n+1);
        fill(data.begin(),data.end(),0);
    }
    void update(int id,int val) {
        for(int i=id;n>=i; i += i&(-i)) {
            data[i] += val;
        }
    }
    int query(int id) {
        int ret=0;
        for (int i=id;i>0; i-=i&(-i)) {
            ret += data[i];
        }
        return ret;
    }
} bit;

const int MAX_N = 10006;

int a[MAX_N];

int main () {
    int n;
    while (scanf("%d",&n) != EOF) {
        bit.init(n);
        int ans=0;
        for (int i=1;n>=i;i++) {
            scanf("%d",&a[i]);
            ans += (bit.query(n) - bit.query(a[i]));
            bit.update(a[i],1);
        }
        printf("%d\n",ans);
    }
}

Challenge : 如果現在是問有多少數對，只得q <= ai-aj <= p 呢？

例如：http://sprout.tw/oj/pro/245/

這個時候，我們可以寫棵treap去揍他

#include <iostream>
#include <stdio.h>
#include <ctime>
#include <cstdlib>
using namespace std;

struct Treap {
    Treap* lc;
    Treap* rc;
    int key,pri,size;
    Treap(int _key) {
        lc=rc=NULL;
        key=_key;
        pri=rand();
        size=1;
    }
};

int Size(Treap* t) {
    return t ? t->size : 0;
}

void pull(Treap* t) {
    t->size = 1 + Size(t->lc) + Size(t->rc);
}

Treap* merge(Treap* a,Treap* b) {
    if (!a||!b) return a?a:b;
    else if (a->pri > b->pri) {
        a->rc=merge(a->rc,b);
        pull(a);
        return a;
    }
    else {
        b->lc=merge(a,b->lc);
        pull(b);
        return b;
    }
}

void split(Treap* t,int k,Treap* &a,Treap* &b) {
    if (!t) a=b=NULL;
    else if (t->key <= k) {
        a=t;
        split(t->rc,k,a->rc,b);
        pull(a);
    }
    else {
        b=t;
        split(t->lc,k,a,b->lc);
        pull(b);
    }
}

//p<=aj-ai<=q
//-q+aj<=ai<=-p+aj

int query(Treap* root,int val,int p,int q) {
    Treap* tl;
    Treap* tr;
//    cout<<-q+val-1<<" ~ "<<-p+val <<endl;
    split(root,-q+val-1,tl,root);
    split(root,-p+val,root,tr);
    if (root!=NULL) {
//        cout<<"root->key = "<<root->key<<endl;
        pull(root);
    }
    else {
//        cout<<"empty\n";
    }
    int ret=Size(root);
    root=merge(merge(tl,root),tr);
    return ret;
}

void dfs(Treap* t) {
    cout<<t->key<<' ';
    if (t->lc) dfs(t->lc);
    if (t->rc) dfs(t->rc);
}

int main () {
    srand(time(NULL));
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,p,q;
        scanf("%d %d %d",&n,&p,&q);
        long long ans=0;
        Treap* root=NULL;
        for (int x=0;n>x;x++) {
//            cout<<"x="<<x<<endl;
            int i;
            scanf("%d",&i);
            ans+=query(root,i,p,q);
            //root=merge(root,new Treap(i)); ==> 錯的 
            Treap* tl;
            Treap* tr;
            split(root,i-1,tl,root);
            split(root,i,root,tr);
            root=merge(root,new Treap(i));
            root=merge(merge(tl,root),tr);
        }
        
        printf("%lld\n",ans);
    }
}