Gọi ~cnt0(x)~ là số lượng số lớn hơn ~x~ ở bên trái ~x~ và ~cnt1(x)~ là số lượng số bé hơn ~x~ ở bên phải ~x~. Ta thấy ~cnt0(x) + cnt1(x)~ là số cặp nghịch thế chứa ~x~ trong đó.

Gọi ~prev~ là giá trị trước đó của ~x~ và ~inv~ là số cặp nghịch thế trước khi cập nhật.

Sau mỗi lần cập nhật, số lượng cặp nghịch thế sẽ là $$inv−cnt0(prev)−cnt1(prev)+cnt0(x)+cnt1(x)$$

Cách 1 (Sqrt Decomposition + Fenwick)

Ta chia mảng ra thành các đoạn liên tiếp mỗi đoạn ~\sqrt{NlogN}~ phần tử. Mỗi đoạn sẽ chứa một cây fenwick lưu số lần xuất hiện của các giá trị trong đoạn đó. Để tìm số phần tử bé hơn ~x~ trong đoạn, ta chỉ cần truy vấn tổng tiền tố của các cây fenwick.

Để tính ~cnt0~, ta duyệt qua các đoạn ở bên trái ~x~. Để tính ~cnt1~, ta duyệt qua các đoạn ở bên phải ~x~.

Độ phức tạp: ~O(Q \sqrt{NlogN})~.

Code tham khảo

#include<bits/stdc++.h>
#define NMAX 200005
//#pragma GCC optimize("O3")
using namespace std;
unordered_map<int,int> id;
set<int> s;
int v[NMAX],n;
pair<int,int> queries[NMAX];
int chunk_size;
int chunks[77][NMAX];
void insert(const int& pos, int val, const int& cnt){
    while(val<NMAX)
        chunks[pos/chunk_size][val]+=cnt,val+=val&-val;
}
int cnt(int pos, const int& val){ /// #less equal before
    if(pos<0) return 0;
    int ans=0;
    while((pos+1)%chunk_size)
        ans+=v[pos--]<=val;
    pos=(pos+1)/chunk_size-1;
    while(pos>=0){
        int v2=val;
        while(v2) ans+=chunks[pos][v2],v2-=v2&-v2;
        pos--;
    }
    return ans;
}
int cnt2(int pos, const int& val){ /// #less equal after
    if(pos<0 || pos>=n) return 0;
    int ans=0;
    while(pos<n && pos%chunk_size)
        ans+=v[pos++]<=val;
    if(pos==n) return ans;
    pos/=chunk_size;
    while(pos*chunk_size<n){
        int v2=val;
        while(v2) ans+=chunks[pos][v2],v2-=v2&-v2;
        pos++;
    }
    return ans;
}
int main()
{
    int q;
    long long inversions=0;
    scanf("%d%d",&n,&q);
    chunk_size=sqrt(n*log2(NMAX));
    for(int i=0;i<n;i++){
        scanf("%d",&v[i]), s.insert(v[i]);
    }
    for(int i=0;i<q;i++){
        scanf("%d%d",&queries[i].first,&queries[i].second), s.insert(queries[i].second);
    }
    for(const auto& it : s) id[it]=id.size()+1;
    for(int i=0;i<n;i++){
        v[i]=id[v[i]];
        inversions+=(long long)(cnt(i-1,NMAX-1)-cnt(i-1,v[i]));
        insert(i,v[i],1);
    }
    for(int i=0;i<q;i++){
        int p=queries[i].first-1,x=id[queries[i].second];
        insert(p,v[p],-1);
        inversions-=(long long)(p-cnt(p-1,v[p])+cnt2(p+1,v[p]-1));
        v[p]=x;
        insert(p,v[p],1);
        inversions+=(long long)(p-cnt(p-1,v[p])+cnt2(p+1,v[p]-1));
        printf("%lld\n",inversions);
    }
    return 0;
}

Cách 2 (Fenwick + Data Structures)

Ta có thể tạo một cây fenwick sao cho mỗi nút của cây chứa một ordered set (cây trie nhị phân, treap, cây AVL, ...) của các phần tử chứa bởi nút đó.

Các thao tác truy vấn và cập nhật sẽ được xử lí như cây fenwick bình thường.

Độ phức tạp: ~O((N+Q) \cdot \log_{2}N \cdot \log_2 \max a_i)~.

Code tham khảo

#include<bits/stdc++.h>

using namespace std;
const int NMAX=1e5+2;
template<size_t bit_count=31>
struct bitwise_trie{
    struct node{
        int subtreeSize=0;
        node* children[2]={NULL,NULL};
    };
    node* root=new node;
    void insert(int num, int cnt=1){
        node* curr=root;
        for(int i=bit_count;i>=0;i--){
            if(curr->children[num>>i&1]==NULL)
                curr->children[num>>i&1] = new node;
            curr=curr->children[num>>i&1];
            curr->subtreeSize+=cnt;
        }
    }
    int order_of_key(int num){
        node* curr=root;
        int cnt_less=0;
        for(int i=bit_count;i>=0;i--){
            if((num>>i&1) && curr->children[0]!=NULL)
                cnt_less+=curr->children[0]->subtreeSize;
            if(curr->children[num>>i&1]==NULL)
                return cnt_less;
            curr=curr->children[num>>i&1];
        }
        return cnt_less;
    }
};
bitwise_trie<17> BIT[NMAX];
void insert(int pos, int num, int cnt=1){
    while(pos<NMAX){
        BIT[pos].insert(num,cnt);
        pos+=pos&-pos;
    }
}
int order_of_key(int pos, int num){
    int cnt=0;
    while(pos){
        cnt+=BIT[pos].order_of_key(num);
        pos-=pos&-pos;
    }
    return cnt;
}
int v[NMAX];
set<int> s;
map<int,int> compressed_value;
pair<int,int> queries[NMAX];
int main()
{
    int n,q;
    long long inversions=0;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        cin>>v[i];
        s.insert(v[i]);
    }
    for(int i=0;i<q;i++){
        scanf("%d%d",&queries[i].first,&queries[i].second);
        s.insert(queries[i].second);
    }
    for(auto it : s) compressed_value[it]=compressed_value.size();
    for(int i=1;i<=n;i++){
        v[i]=compressed_value[v[i]];
        insert(i,v[i]);
        inversions+=i-1-order_of_key(i-1,v[i]+1);
    }
    for(int i=0;i<q;i++){
        int p=queries[i].first,x=compressed_value[queries[i].second];
        inversions-=p-1-order_of_key(p-1,v[p]+1);
        inversions+=p-1-order_of_key(p-1,x+1);
        inversions-=order_of_key(n,v[p])-order_of_key(p,v[p]);
        inversions+=order_of_key(n,x)-order_of_key(p,x);
        insert(p,v[p],-1);
        insert(p,x,1);
        v[p]=x;
        printf("%lld\n",inversions);
    }
    return 0;
}