程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Round #301 (Div. 2)(樹狀數組+離散化)

Codeforces Round #301 (Div. 2)(樹狀數組+離散化)

編輯:C++入門知識

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<

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved