test/yosupo_Static_Range_Inversions_Query.test.cpp

View this file on GitHub
Last update: 2023-04-05 23:10:22+09:00
Problem: https://judge.yosupo.jp/problem/static_range_inversions_query

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"

#include "../template.hpp"

#include "../Algorithm/Mo.hpp"

#include "../DataStructure/BinaryIndexedTree.hpp"


signed main(){
    int n,q;cin>>n>>q;
    vector<int> a(n);
    cin>>a;

    auto comp=a;
    sort(ALL(comp));
    comp.erase(unique(ALL(comp)),end(comp));
    rep(i,n) a[i]=lower_bound(ALL(comp),a[i])-begin(comp);

    BinaryIndexedTree<ll> seg(n+10);
    
    ll res=0;
    auto add_left=[&](int x){
        res+=seg.query(0,a[x]);
        seg.add(a[x],1);
    };
    auto add_right=[&](int x){
        res+=seg.query(a[x]+1,n+5);
        seg.add(a[x],1);
    };
    auto erase_left=[&](int x){
        res-=seg.query(0,a[x]);
        seg.add(a[x],-1);
    };
    auto erase_right=[&](int x){
        res-=seg.query(a[x]+1,n+5);
        seg.add(a[x],-1);
    };

    Mo mo(n,add_left,add_right,erase_left,erase_right);

    rep(i,q){
        int l,r;cin>>l>>r;
        mo.add(l,r);
    }
    mo.build();

    vector<ll> ans(q);
    rep(i,q){
        int j=mo.process();
        ans[j]=res;
    }

    for(auto &x:ans) cout<<x<<"\n";
    return 0;
}

#line 1 "test/yosupo_Static_Range_Inversions_Query.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"

#line 1 "template.hpp"
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

#line 4 "test/yosupo_Static_Range_Inversions_Query.test.cpp"

#line 1 "Algorithm/Mo.hpp"
/*
refs : https://beet-aizu.github.io/library/algorithm/mo.hpp
       https://ei1333.github.io/library/other/mo.hpp
*/
struct Mo{
    using F=function<void(int)>;
    int n,idx,ql,qr;
    vector<pair<int,int>> query;
    vector<int> ord;
    // [l,r) 
    // add_left  : l-1を足す, add_right : rを足す
    // erase_left: lを消す,  erase_right: r-1を消す
    F add_left,add_right,erase_left,erase_right;
 
    Mo(int n,F add_left,F add_right,F erase_left,F erase_right):
    n(n),idx(0),ql(0),qr(0),
    add_left(add_left),add_right(add_right),erase_left(erase_left),erase_right(erase_right)
    {}
 
    void add(int l,int r){
        query.emplace_back(l,r);
    }
 
    void build(){
        int q=(int)query.size();
        int bs=n/min(n,int(sqrt(q)));
        // 左端のブロックでソート
        // 左端のブロックが同じなら右端でソート
        ord.resize(q);
        iota(begin(ord),end(ord),0);
        sort(begin(ord),end(ord),[&](int a,int b){
            int al=query[a].first/bs,bl=query[b].first/bs;
            if(al!=bl) return al<bl;
            // 偶奇で始点を左右に振ると動きに無駄がない
            if(al&1) return query[a].second>query[b].second;
            return query[a].second<query[b].second;
        });
    }
 
    // 1個クエリを進め，処理したクエリのindexを返す
    // processが終わってから結果を格納すること
    // ans[process()]=res; はできない
    int process(){
        if(idx>=(int)ord.size()) return -1;
        int cur=ord[idx++];
        while(ql>query[cur].first)  add_left(--ql);
        while(qr<query[cur].second) add_right(qr++);
        while(ql<query[cur].first)  erase_left(ql++);
        while(qr>query[cur].second) erase_right(--qr);
        return cur;
    }
};
#line 6 "test/yosupo_Static_Range_Inversions_Query.test.cpp"

#line 1 "DataStructure/BinaryIndexedTree.hpp"
template<typename T>
struct BinaryIndexedTree{
    vector<T> data;
    BinaryIndexedTree()=default;
    BinaryIndexedTree(int sz):data(sz+1,0){}
    BinaryIndexedTree(const vector<T> &a):data(a.size()+1,0){
        for(int i=0;i<(int)a.size();i++)data[i+1]=a[i];
        for(int i=1;i<(int)data.size();i++){
            int j=i+(i&-i);
            if(j<(int)data.size()) data[j]+=data[i];
        }
    }
    void add(int k,const T &x){for(++k;k<(int)data.size();k+=(k&-k)) data[k]+=x;}
    // sum [0,k)
    T sum(int k){
        T ret=T();
        for(;k>0;k-=(k&-k))ret+=data[k];
        return ret;
    }
    // sum [l,r)
    T query(int l,int r){
        return sum(r)-sum(l);
    }
    T operator[](const int &k){return query(k,k+1);}
    // sum[0,i)>=xとなる最小のi
    int lower_bound(T x){
        int r=1,i=0;
        while(r<(int)data.size())r<<=1;
        for(;r>0;r>>=1)if(i+r<(int)data.size() and data[i+r]<x){
            x-=data[i+r];i+=r;
        }
        return i+1;
    }
};
#line 8 "test/yosupo_Static_Range_Inversions_Query.test.cpp"


signed main(){
    int n,q;cin>>n>>q;
    vector<int> a(n);
    cin>>a;

    auto comp=a;
    sort(ALL(comp));
    comp.erase(unique(ALL(comp)),end(comp));
    rep(i,n) a[i]=lower_bound(ALL(comp),a[i])-begin(comp);

    BinaryIndexedTree<ll> seg(n+10);
    
    ll res=0;
    auto add_left=[&](int x){
        res+=seg.query(0,a[x]);
        seg.add(a[x],1);
    };
    auto add_right=[&](int x){
        res+=seg.query(a[x]+1,n+5);
        seg.add(a[x],1);
    };
    auto erase_left=[&](int x){
        res-=seg.query(0,a[x]);
        seg.add(a[x],-1);
    };
    auto erase_right=[&](int x){
        res-=seg.query(a[x]+1,n+5);
        seg.add(a[x],-1);
    };

    Mo mo(n,add_left,add_right,erase_left,erase_right);

    rep(i,q){
        int l,r;cin>>l>>r;
        mo.add(l,r);
    }
    mo.build();

    vector<ll> ans(q);
    rep(i,q){
        int j=mo.process();
        ans[j]=res;
    }

    for(auto &x:ans) cout<<x<<"\n";
    return 0;
}