Codeforces Round #301 (Div. 2)（樹狀數組+離散化）
E. Infinite Inversions time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output
There is an infinite sequence consisting of all positive integers in the increasing order: p?=?{1,?2,?3,?...}. We performed n swapoperations with this sequence. A swap(a,?b) is an operation of swapping the elements of the sequence on positions a and b. Your task is to find the number of inversions in the resulting sequence, i.e. the number of such index pairs (i,?j), that i?j and pi?>?pj.
Input
The first line contains a single integer n (1?≤?n?≤?105) — the number of swap operations applied to the sequence.
Each of the next n lines contains two integers ai and bi (1?≤?ai,?bi?≤?109, ai?≠?bi) — the arguments of the swap operation.
Output
Print a single integer — the number of inversions in the resulting sequence.
Sample test(s) input
2
4 2
1 4
output
4
input
3
1 6
3 4
2 5
output
15
Note
In the first sample the sequence is being modified as follows: 
. It has 4 inversions formed by index pairs (1,?4), (2,?3), (2,?4) and (3,?4).
題意：一個1,2,3,4,....的序列（長度無限)進行n次操作每次操作交換位置a和b上的數，問最終的序列有多少對逆序數。
先用map搞出最終的序列(只需要搞出題目中交換位置的數就行)。然後按照樹狀數組求逆序對的方式來操作。不過需要進行一下離散化。
考慮這樣一個序列a[l],l+1,l+2,....,r-1,a[r]其中l和r上的數是交換過的（不一定是l和r上的進行交換），考慮中間那段對逆序數的影響，令w = (r-1)- (l+1)-1，右邊小於l+1的數為x，則右邊的數對這段區間[l+1,r-1]逆序數的貢獻是w*x(所以ans += w*Query(Loc-1)),這段區間對在l+1左邊且值大於r-1的每個數貢獻也是w(所以Modify(Loc-1,w,tot))
#include
#define foreach(it,v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 100;
ll c[maxn];
#define lowbit(x) (x)&(-x)
void Modify(int x,ll d,int n)
{
while(x<=n) {
c[x] += d;
x += lowbit(x);
}
}
ll Query(int x)
{
ll res = 0;
while(x>0) {
res += c[x];
x -= lowbit(x);
}
return res;
}
int main(int argc, char const *argv[])
{
int n;
while(cin>>n) {
mapQ;
for(int i = 0; i < n; i++) {
int L,R; cin>>L>>R;
if(Q.find(L)==Q.end())Q[L] = L;
if(Q.find(R)==Q.end())Q[R] = R;
swap(Q[L],Q[R]);
}
int tot = 0;
vector >v;
vector sec;
foreach(it,Q) {
v.push_back(*it);
sec.push_back(it->second);
tot++;
}
sort(sec.begin(), sec.end());
memset(c,0,sizeof(c[0])*(tot+10));
ll ans = 0;
for(int i = tot-1; i >= 0; i--) {
int Loc = lower_bound(sec.begin(), sec.end(),v[i].second)-sec.begin() + 1;
ans += Query(Loc-1);/*統計右邊小於v[i].second的數*/
if(i==0)break;
Modify(Loc,1,tot);
ll w = (v[i].first-1) - v[i-1].first;/*a[l],l+1,l+2,...r-1,a[r]中的[l+1,r-1]區間元素個數*/
if(w<1)continue;
Loc = lower_bound(sec.begin(), sec.end(),v[i-1].first+1)-sec.begin()+1;/*序列v[i-1].first+1,v[i-1].first+2...,v[i].first-1在離散化後的位置*/
ans += w*Query(Loc-1);/*統計序列v[i-1].first+1,v[i-1].first+2...,v[i].first-1右邊小於該序列的數*/
/*為什麼要在Loc-1加上w呢因為v[i].first離散出來的位置是Loc，如果此處是Loc且v[k].second==v[i].first的k小於i，
那麼統計v[k].first這個位置的逆序數時不會統計到這段連續的區間*/
Modify(Loc-1,w,tot);
}
cout<
