結果

問題 No.3305 Shift Sort
ユーザー Today03
提出日時 2025-10-05 16:29:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,206 bytes
コンパイル時間 3,289 ms
コンパイル使用メモリ 291,276 KB
実行使用メモリ 9,744 KB
最終ジャッジ日時 2025-10-05 16:30:25
合計ジャッジ時間 27,477 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 14 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define REP(i,n) for(int i=0; i<n; i++)
bool chmax(auto& a, auto b) { return a<b ? a=b, true : false; }
bool chmin(auto& a, auto b) { return a>b ? a=b, true : false; }
using ll=long long; const int INF=1e9+10; const ll INFL=4e18;

#ifdef DEBUG
#include "./debug.hpp"
#else
#define debug(...)
#define print_line
#endif


/// @brief Mo's Algorithm
/// @ref https://ei1333.hateblo.jp/entry/2017/09/11/211011
struct Mo {
    /// @brief コンストラクタ
    Mo(int n) {
        this->n=n;
        q=0;
    }

    /// @brief クエリ [l, r) を追加する
    void add(int l, int r) {
        q++;
        ls.push_back(l);
        rs.push_back(r);
    }

    /// @brief クエリを実行する
    /// @param add_left `add_left(i)` i 番目の要素が左から加わるときの処理
    /// @param add_right `add_right(i)` i 番目の要素が右から加わるときの処理
    /// @param del_left `del_left(i)` i 番目の要素が左から抜けるときの処理
    /// @param del_right `del_right(i)` i 番目の要素が右から抜けるときの処理
    /// @param out `out(i)` i 番目のクエリの答えを求めたときの処理
    /// @note O(N sqrt(Q))
    template<typename F1, typename F2, typename F3, typename F4, typename F5>
    void execute(F1&& add_left, F2&& add_right, F3&& del_left, F4&& del_right, F5&& out) {
        vector<int> qi(q); iota(qi.begin(),qi.end(),0);

        // https://nyaannyaan.github.io/library/misc/mo.hpp.html
        const int wid=max<int>(1,1.0*n/max<double>(1.0,sqrt(q*2.0/3.0)));
        sort(qi.begin(),qi.end(),[&](int a, int b) {
            if(ls[a]/wid!=ls[b]/wid) return ls[a]<ls[b];
            if((ls[a]/wid)&1) return rs[a]<rs[b];
            return rs[a]>rs[b];
        });

        int nl=0, nr=0;
        for(int& i: qi){
            while(nl>ls[i]) add_left(--nl);
            while(nr<rs[i]) add_right(nr++);
            while(nl<ls[i]) del_left(nl++);
            while(nr>rs[i]) del_right(--nr);
            out(i);
        }
    }

private:
    int n, q;
    vector<int> ls, rs;
};


struct FenwickTree {
    FenwickTree()=default;
    FenwickTree(int n) {
        this->n=n;
        dat=vector<ll>(n,0);
    }
    void add(int i, ll x) {
        i++;
        while(i<=n) dat[i-1]+=x, i+=i&-i;
    }
    ll sum(int l, int r) { return sum(r)-sum(l); }
    ll operator[](int i) { return sum(i,i+1); }
    int size() { return n; }

private:
    int n;
    vector<ll> dat;
    ll sum(int r) {
        ll ret=0;
        while(r>0) ret+=dat[r-1], r-=r&-r;
        return ret;
    }
};


/// @brief 可換群
namespace Abel {
    /// @brief 和
    template<typename T>
    struct Sum {
        using Type=T;
        static Type id() { return T(0); }
        static Type op(const Type& a, const Type& b) { return a+b; }
        static Type inv(const Type& x) { return -x; }
    };

    /// @brief XOR
    template<typename T>
    struct Xor {
        using Type=T;
        static Type id() { return T(0); }
        static Type op(const Type& a, const Type& b) { return a^b; }
        static Type inv(const Type& x) { return x; }
    };
}

//----------------------------------------------------------

void solve() {
    int N,Q; cin>>N>>Q;
    vector<int> A(N); REP(i,N) cin>>A[i], A[i]--;
    vector<ll> ans(Q);

    Mo mo(N);
    FenwickTree ft(N);

    ll cur=0;
    auto add_left=[&](int i) {
        cur+=ft.sum(0,A[i]);
        ft.add(A[i],+1);
    };
    auto add_right=[&](int i) {
        cur+=min(ft.sum(A[i]+1,N),1ll);
        ft.add(A[i],+1);
    };
    auto del_left=[&](int i) {
        cur-=ft.sum(0,A[i]);
        ft.add(A[i],-1);
    };
    auto del_right=[&](int i) {
        cur-=min(ft.sum(A[i]+1,N),1ll);
        ft.add(A[i],-1);
    };
    auto out=[&](int q) { ans[q]=cur; };

    REP(i,Q) {
        int l,r; cin>>l>>r;
        l--;
        mo.add(l,r);
    }
    debug(N,Q,A);

    mo.execute(add_left,add_right,del_left,del_right,out);
    for(ll x: ans) cout<<x<<'\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    //cout<<fixed<<setprecision(15);
    int T=1; //cin>>T;
    while(T--) solve();
}
0