(uva 10305) topological sort

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

const int MAX_N = 103;
vector<int> edg[MAX_N];
bool visit[MAX_N];
int who_get_stamp[MAX_N];

void dfs_for_stamp(int now,int &cur_stamp) {
visit[now]=true;
int len=edg[now].size();
for (int x=0;len>x;x++) {
int j=edg[now][x];
if (visit[j]==false) dfs_for_stamp(j,cur_stamp);
}
who_get_stamp[cur_stamp++]=now;
}

int main () {
int n,m;
while (scanf("%d %d",&n,&m) != EOF) {
if (!n&&!m) return 0;
for (int x=0;n>=x;x++) edg[x].clear();
while (m--) {
int i,j;
scanf("%d %d",&i,&j);
edg[i].push_back(j);
}
for (int x=0;n>=x;x++) visit[x]=false;
int stamp=0;
for (int x=1;n>=x;x++) {
if (visit[x]==false) {
dfs_for_stamp(x,stamp);
}
}
for (int x=n-1;x>=0;x--) {
if (x!=n-1) printf(" ");
printf("%d",who_get_stamp[x]);
}
puts("");
}
}

Treap 模板(lazy tag)

http://poj.org/problem?id=3468

http://judge.ioicamp.org/problems/23

要小心的push部分XDDD

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

typedef long long LL;

struct Treap {
Treap *lc;
Treap *rc;
LL val,pri,key;
LL tag;
LL sum;
int son;  //include 自己
Treap(LL _val,LL _key) {
val=_val;
key=_key;
sum=_val;
pri=rand();
tag=0;
son=1;
lc = rc = NULL;
}
};

LL sm(Treap* t) {
return t? t->sum : 0;
}

int sn(Treap* t) {
return t? t->son : 0;
}

void pull(Treap* t) {
t->sum = sm(t->lc) + sm(t->rc) + t->val;
t->son = sn(t->lc) + sn(t->rc) + 1;
}

void push(Treap* t) {
if (t->tag==0) return;
t->val += t->tag;
t->sum += t->tag;
if (t->lc) {
t->lc->tag += t->tag;
t->lc->sum += t->tag * (sn(t->lc));
}
if (t->rc) {
t->rc->tag += t->tag;
t->rc->sum += t->tag * (sn(t->rc));
}
t->tag = 0;
}

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

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

LL query(Treap *t,int l,int r) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
LL ret=sm(t);
t=merge(merge(tl,t),tr);
return ret;
}

void modify(Treap* t,int l,int r,LL v) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
t->tag += v;
t->sum += v * sn(t); //沒加自己!!!
t=merge(merge(tl,t),tr);
}

int main () {
srand(time(NULL));
int T;
scanf("%d",&T);
while (T--) {
Treap* root;
root=NULL;
int n,q,i;
scanf("%d %d",&n,&q);
for (int x=1;n>=x;x++) {
scanf("%d",&i);
root=merge(root,new Treap(i,x));
// cout<<"sum = "<<root->sum<<endl;
// cout<<"val = "<<root->val<<endl;
}
while (q--) {
string d;
cin >> d;
if (d=="query") {
int i,j;
scanf("%d %d",&i,&j);
printf("%lld\n",query(root,i,j));
}
else if (d=="add"){
int i,j,k;
scanf("%d %d %d",&i,&j,&k);
modify(root,i,j,k);
}
}
// cout<<"List : ";
// for (int x=1;n>=x;x++) cout<<query(root,x,x)<<' ';
// cout<<endl;
}
}

Treap 模板 (一般)

目前是沒有LAZY TAG的

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

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

const int INF = 1000000000;

struct Treap {
Treap *lc;
Treap *rc;
int val,pri,key;
int add;
int mx;
Treap(int _val,int _key) {
val=_val;
key=_key;
mx=val;
pri=rand();
add=0;
lc = rc = NULL;
}
};

int mx(Treap* t) {
return t? t->mx + t->add : -INF;
}

void pull(Treap* t) {
t->mx= max(t->val, max(mx(t->lc), mx(t->rc)) );
}

void push(Treap* t) {
t->val += t->add;
if (t->lc) t->lc->add += t->add;
if (t->rc) t->rc->add += t->add;
t->add = 0;
}

Treap* merge(Treap *a,Treap *b) {
// puts("in0");
if (!a || !b) return a?a:b;
if (a->pri > b->pri) {
push(a);
// puts("in1");
// cout<<"a->val = "<<a->val<<endl;
a->rc=merge(a->rc,b);
pull(a);
return a;
}
else {
push(b);
// puts("in2");
// cout<<"b->val = "<<b->val<<endl;
b->lc=merge(a,b->lc);
pull(b);
return b;
}
}

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

int rmq(Treap *t,int l,int r) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
// puts("in");
int ret=mx(t);
t=merge(merge(tl,t),tr);
return ret;
}

void add(Treap* t,int l,int r,int v) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
t->add += v;
t=merge(merge(tl,t),tr);
}

int main () {
srand(time(NULL));
int n;
while (scanf("%d",&n) != EOF) {
Treap* root;
root=NULL;
for (int x=1;n>=x;x++) {
int i;
scanf("%d",&i);
root = merge(root,new Treap(i,x));
}
int q;
scanf("%d",&q);
while (q--) {
int i,j;
scanf("%d %d",&i,&j);
if (i>j) swap(i,j);
printf("%d\n",rmq(root,i,j));
}
}
}

(IOIcamp_Judge) 27. 骨牌 [SCC]

http://judge.ioicamp.org/problems/29
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2499
Zj上面也有

就是你要把SCC壓成一個點，然後不斷去找入度=0的點，就好了

求SCC：
1. 把圖反向
2. topological sort反向圖，紀錄time tag
3. 從time tag最大的開始dfs SCC

這裡 是另外一邊一模一樣的

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

const int MAX_N = 100003;

vector<int> edg[MAX_N];
vector<int> rev_edg[MAX_N];
bool visit[MAX_N];
int who_get_stamp[MAX_N];
int in_scc[MAX_N];

vector<int> sccedg[MAX_N];
int rudu[MAX_N];
int chudu[MAX_N];

void dfs_for_stamp(int now,int& cur_stamp) {
//    cout<<"in "<<now<<endl;
    visit[now]=true;
    int len=rev_edg[now].size();
    for (int x=0;len>x;x++) {
        int i=rev_edg[now][x];
        if (visit[i]==false) {
            dfs_for_stamp(i,cur_stamp);
        }
    }
    who_get_stamp[cur_stamp++] = now;
}

void dfs_for_scc(int now,int scc) {
    visit[now]=true;
    int len=edg[now].size();
    for (int x=0;len>x;x++) {
        int i=edg[now][x];
        if (visit[i]==false) {
            dfs_for_scc(i,scc);
        }
    }
    in_scc[now]=scc;
}

int get_scc(int n) {
    
    memset(who_get_stamp,-1,sizeof(who_get_stamp));
    for (int x=0;n>=x;x++) visit[x]=false;
    int cur_stamp=1;
    for (int x=1;n>=x;x++) {
        
        if (visit[x]==false) {
            dfs_for_stamp(x,cur_stamp);
        }
    }
    for (int x=0;n>=x;x++) visit[x]=false;
    int scc=0;
    for (int x=n;x>=1;x--) {
        if (visit[who_get_stamp[x]]==false) {
            dfs_for_scc(who_get_stamp[x],scc++);
        }
    }
//    for (int x=1;n>=x;x++) cout<<"scc["<<x<<"] = "<<in_scc[x]<<endl;
    for (int x=0;scc>x;x++) {
        sccedg[x].clear();
        rudu[x]=chudu[x]=0;
    }
//    puts("in");
//    cout<<"scc="<<scc<<endl;
    for (int i=1;n>=i;i++) { //restore edge
        int len=edg[i].size();
        for (int j=0;len>j;j++) {
            int x=edg[i][j];
            if (in_scc[i]==in_scc[x]) continue;
            sccedg[in_scc[i]].push_back(in_scc[x]);
            rudu[in_scc[x]]++;
            chudu[in_scc[i]]++;
        }
    }
    
    int ans=0;
    //topological sort
    for (int i=0;scc>i;i++) {
        if (rudu[i]==0) ans++;
    }
    return ans;
}

int main () {
    int T;
    scanf("%d",&T);
    for (int qq=1;T>=qq;qq++) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int x=1;n>=x;x++) edg[x].clear();
        for (int x=1;n>=x;x++) rev_edg[x].clear();
        for (int x=0;m>x;x++) {
            int i,j;
            scanf("%d %d",&i,&j);
            edg[i].push_back(j);
            rev_edg[j].push_back(i);
        }
        printf("%d\n",get_scc(n));
    }
}

(codeforces) 380C. Sereja and Brackets

http://codeforces.com/contest/380/problem/C

總共花了8hr，<(_ _)>

各種case要討論啊~~~

//XXXXXYYYYZZZZ ㄌㄟ

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

struct VAL {
int type;
int num;
void change(int b,int c) {
type=b;
num=c;
}
};

struct Val {
VAL pre;
VAL suf;
int ans;
void change_pre(int type,int num) {
pre.change(type,num);
}
void change_suf(int type,int num) {
suf.change(type,num);
}
void change_ans(int Ans) {
ans = Ans;
}
int pre_type() {
return pre.type;
}
int pre_num() {
return pre.num;
}
int suf_num() {
return suf.num;
}
int suf_type() {
return suf.type;
}
int get_ans() {
return ans;
}
};

Val empty;

bool EMPTY(Val val){
if (val.ans==2147483647) return true;
else return false;
}

Val PULL(Val a, Val b) {
if (EMPTY(a)) return b;
else if (EMPTY(b)) return a;
Val val;
int ans=a.get_ans() + b.get_ans();
int type;
int num;
if (a.suf_type() == b.pre_type()) {
if (a.pre_type() == a.suf_type() && b.pre_type()==b.suf_type()) { // >> + >> or << + << or 00+00
// puts("in-3");
assert(a.pre_num() == a.suf_num());
type=a.pre_type();
num=a.pre_num() + b.pre_num();
if (type==0) num=0;
val.change_ans(ans);
val.change_pre(type,num);
val.change_suf(type,num);
}
else if (b.pre_type()==b.suf_type()) {   // >><< + << !!!
// puts("in-2");
assert(a.pre_type() == -1);
val.change_pre(a.pre_type(),a.pre_num());
val.change_ans(ans);
assert(a.suf_type() == 1);
val.change_suf(a.suf_type(),a.suf_num() + b.pre_num());
}
else if (a.pre_type()==a.suf_type()) {  // > + ><
val.change_ans(ans);
val.change_pre(a.pre_type(),a.pre_num()+b.pre_num());
val.change_suf(b.suf_type(),b.suf_num());
}
}
else if (a.suf_type()==0) {
assert(a.pre_type() == 0);
val.change_ans(ans);
val.change_pre(b.pre_type(), b.pre_num());
val.change_suf(b.suf_type(), b.suf_num());
}
else if (b.pre_type()==0) {
assert(b.suf_type() == 0);
val.change_ans(ans);
val.change_pre(a.pre_type(), a.pre_num());
val.change_suf(a.suf_type(), a.suf_num());
}
else if (a.suf_type()==1) { //<< + >><< or << + >> or >><< + >> or >><< + >>><<
assert(b.pre_type()==-1);
if (b.suf_type()==1) {  //case (>>)<< + >><<
if (a.suf_num() > b.pre_num()) { //(>>)<< + ><<
ans+=b.pre_num();
val.change_ans(ans);
if (a.pre_type() == 1)val.change_pre(a.pre_type(),a.suf_num() - b.pre_num() + b.suf_num());
else val.change_pre(a.pre_type(),a.pre_num());
val.change_suf(b.suf_type(),a.suf_num() - b.pre_num() + b.suf_num());
}
else if (a.suf_num() < b.pre_num()) { //(>>)<< + >>><<
ans+=a.suf_num();
val.change_ans(ans);
if (a.pre_type()==1) val.change_pre(b.pre_type(),b.pre_num() - a.suf_num());
else if(a.pre_type()==-1) val.change_pre(a.pre_type(), a.pre_num() + b.pre_num() - a.suf_num());
val.change_suf(b.suf_type(),b.suf_num());
}
else if (a.suf_num() == b.pre_num()) {
ans+=a.suf_num();
val.change_ans(ans);
if (a.pre_type()==-1) val.change_pre(a.pre_type(),a.pre_num());
else if (a.pre_type()==1) val.change_pre(b.suf_type(),b.suf_num());
val.change_suf(b.suf_type(),b.suf_num());
}
}
else if (b.suf_type() == -1) { //(>>)<< + >>
if (a.suf_num() > b.pre_num()) { //(>>)<< + >
ans+=b.pre_num();
val.change_ans(ans);
if (a.pre_type() == 1)val.change_pre(a.pre_type(),a.suf_num() - b.pre_num());
else if (a.pre_type() == -1)val.change_pre(a.pre_type(),a.pre_num());
val.change_suf(a.suf_type(),a.suf_num()-b.pre_num());
}
else if (a.suf_num() < b.pre_num()) { //(>>)<< + >>>
ans+=a.suf_num();
val.change_ans(ans);
int num=b.pre_num() - a.suf_num();
if (a.pre_type()==1) ;
else if(a.pre_type()==-1) num+=a.pre_num();
val.change_pre(b.pre_type(),num);
val.change_suf(b.suf_type(),num);
}
else if (a.suf_num() == b.pre_num()) { // >< + >
ans += a.suf_num();
val.change_ans(ans);
if (a.pre_type()==-1) val.change_pre(a.pre_type(),a.pre_num());
else if (a.pre_type()==1) val.change_pre(0,0);
if (a.pre_type()==-1) val.change_suf(a.pre_type(),a.pre_num());
else if (a.pre_type()==1) val.change_suf(0,0);
}
}

}
else if (b.suf_type() == 1) {  //>>>+<<
val.change_pre(a.pre_type(),a.pre_num());
val.change_suf(b.suf_type(),b.suf_num());
val.change_ans(ans);
}
return val;
}

struct Node {
Node* lc;
Node* rc;
Val val;
Node() {
lc = rc=NULL;
val.change_pre(0,0);
val.change_suf(0,0);
val.change_ans(0);
}
void pull() {
val = PULL(lc->val,rc->val);
}
};


string s;

Node* Build(int L,int R) {
Node* node = new Node();
if (L==R) {
if (s[L]=='(') {
node->val.change_pre(1,1);
node->val.change_suf(1,1);
node->val.change_ans(0);
}
else {
node->val.change_pre(-1,1);
node->val.change_suf(-1,1);
node->val.change_ans(0);
}
return node;
}
int mid=(L+R)>>1;
node->lc=Build(L,mid);
node->rc=Build(mid+1,R);
node->pull();
// cout<<L<<"~"<<R<<" : "<<node->val.get_ans()<<endl;
// cout<<"pre_type = "<<node->val.pre_type() << " , num = "<<node->val.pre_num()<<endl;
// cout<<"suf_type = "<<node->val.suf_type() << " , num = "<<node->val.suf_num()<<endl;


return node;
}


Val query(Node* node,int L,int R,int l,int r) {
if (L>r || l>R) return empty;
else if (l<=L && R<=r) {
Val c = node->val;
// cout<<L<<"~"<<R<<" : ans = "<<c.get_ans()<<endl;
// cout<<"pre_type = "<<c.pre_type() << " , num = "<<c.pre_num()<<endl;
// cout<<"suf_type = "<<c.suf_type() << " , num = "<<c.suf_num()<<endl;
return node->val;
}
int mid=(L+R)>>1;
Val a=query(node->lc,L,mid,l,r);
Val b=query(node->rc,mid+1,R,l,r);
Val c=PULL(a,b);
// cout<<L<<"~"<<R<<" : ans = "<<c.get_ans()<<endl;
// cout<<"pre_type = "<<c.pre_type() << " , num = "<<c.pre_num()<<endl;
// cout<<"suf_type = "<<c.suf_type() << " , num = "<<c.suf_num()<<endl;

return c;
// return PULL(query(node->lc,L,mid,l,r),query(node->rc,mid+1,R,l,r));
}

int main () {
ios::sync_with_stdio(0);
cin.tie(0);
string tmp;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
while (cin >> tmp) {
empty.change_pre(0,0);
empty.change_suf(0,0);
empty.change_ans(2147483647);
s = " " + tmp;
int n=tmp.size();
Node* root = Build(1,n);
int m;
cin >> m;
for (int x=0;m>x;x++) {
int i,j;
cin >> i >> j;
cout << query(root,1,n,i,j).ans * 2<<endl;
}
}
}

(codeforces) 459D. Pashmak and Parmida's problem

http://codeforces.com/contest/459/problem/D

各種線段樹的應用！！！

快要瘋掉了XDDD

寫單純的copy on write還不夠，還有離散化！！！

//這題好複雜XDDD
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 1000003;
vector<int> b;
int a[MAX_N];
int dp[MAX_N];
int dp2[MAX_N];
int cnt[MAX_N];

typedef long long LL;

struct Node {
Node* lc;
Node* rc;
LL val;
Node() {
lc=rc=NULL;
val=-1;
}
};

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) {
if (node->lc==NULL) node->lc=new Node();
modify(node->lc,L,mid,pos,val);
}
else {
if (node->rc==NULL) node->rc=new Node();
modify(node->rc,mid+1,R,pos,val);
}

}

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

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

Query* Build(int L,int R) {
Query* queRy = new Query();
if (L==R) {
queRy->val = cnt[L];
return queRy;
}
int mid=(L+R)>>1;
queRy->lc=Build(L,mid);
queRy->rc=Build(mid+1,R);
queRy->pull();
return queRy;
}

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

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

const int MAX_A = 1e09 + 2;

int main () {
int n;
while (scanf("%d",&n) != EOF) {
memset(dp,0,sizeof(dp));
memset(dp2,0,sizeof(dp2));
Node* root = new Node();
for (int x=0;n>x;x++) {
scanf("%d",&a[x]);
b.push_back(a[x]);
}
sort(b.begin(),b.end());
b.resize(unique(b.begin(),b.end()) - b.begin());
for (int x=0;n>x;x++) {
a[x] = lower_bound(b.begin(),b.end(),a[x]) - b.begin();
a[x]+=1;
int val=a[x];
int pos=query(root,1,MAX_A,val);
// cout<<"pos="<<pos<<endl;
if (pos==-1) {
dp[x]=1;
modify(root,1,MAX_A,val,x);
}
else {
dp[x]=dp[pos]+1;
modify(root,1,MAX_A,val,x);
}
}
for (int x=n-1;x>=0;x--) {
int val=a[x];
int pos=query(root,1,MAX_A,val);
if (pos==-1) {
dp2[x]=1;
modify(root,1,MAX_A,val,x);
}
else {
dp2[x]=dp2[pos]+1;
modify(root,1,MAX_A,val,x);
}
}
memset(cnt,0,sizeof(cnt));
// for (int x=0;n>x;x++) cout<<dp[x]<<endl;
// for (int x=0;n>x;x++) cout <<dp2[x]<<endl;
long long ans=0;
for (int x=0;n>x;x++) cnt[dp2[x]]++;
Query* qUery = Build(1,n);
for (int x=0;n>x;x++) {
// cout<<"x="<<x<<" ; ans="<<ans<<endl;
modify(qUery,1,n,dp2[x],(--cnt[dp2[x]]));
if (dp[x]!=1)ans+= QUERY(qUery,1,n,1,dp[x]-1);
}
printf("%I64d\n",ans);
}
}

(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);
    }
}