結果

問題 No.3305 Shift Sort
コンテスト
ユーザー GOTKAKO
提出日時 2025-11-19 01:58:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 975 ms / 2,000 ms
コード長 3,040 bytes
コンパイル時間 2,529 ms
コンパイル使用メモリ 211,980 KB
実行使用メモリ 80,136 KB
最終ジャッジ日時 2025-11-19 01:58:46
合計ジャッジ時間 19,803 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using MS = int;
class MergeSortTree{
    //構築O(要素数log|A|) クエリO(log|A|*log要素数).
    private:
    int siz = 1;
    vector<vector<MS>> dat,ng;
    void merge(int u,int p,int q){ //昇順に並んだdat[p],dat[q]の要素をdat[u]にマージ.
        int n = dat.at(p).size(),m = dat.at(q).size();
        auto &P = dat.at(p),&Q = dat.at(q),&U = dat.at(u);
        U.resize(n+m);
        int posP = 0,posQ = 0,posU = 0;
        while(posP < n && posQ < m){
            if(P.at(posP) <= Q.at(posQ)) U.at(posU++) = P.at(posP++);
            else U.at(posU++) = Q.at(posQ++);
        }
        while(posP < n) U.at(posU++) = P.at(posP++);
        while(posQ < m) U.at(posU++) = Q.at(posQ++);
    }
    vector<int> findSegment(int l,int r){ //[l,r)のセグ木区間を返す.
        l += siz; r += siz;
        vector<int> ret;
        while(l < r){
            if(l&1) ret.push_back(l++);
            if(r&1) ret.push_back(--r);
            l >>= 1; r >>= 1; 
        }
        return ret;
    }
 
    public:
    MergeSortTree(const vector<MS> &A){ //各要素値1つ.
        int N = A.size();
        while(siz < N) siz *= 2;
        dat.resize(siz<<1); ng.resize(siz<<1);
        for(int i=0; i<N; i++) dat.at(i+siz) = {A.at(i)};
        for(int i=siz-1; i>0; i--) merge(i,i*2,i*2+1);
        for(int i=siz-1; i>0; i--){
            if(dat.at(i*2).size() == 0) continue;
            ng.at(i) = ng.at(i*2);
            for(auto n : ng.at(i*2+1)) ng.at(i).push_back(n);
            int maxa = dat.at(i*2).back();
            for(auto d : dat.at(i*2+1)) if(maxa > d) ng.at(i).push_back(d);
            sort(ng.at(i).begin(),ng.at(i).end());
            ng.at(i).erase(unique(ng.at(i).begin(),ng.at(i).end()),ng.at(i).end()); 
        }
    };

    int query(int l,int r){
        l += siz,r += siz;
        vector<int> Ls,Rs;
        while(l < r){
            if(l&1) Ls.push_back(l++);
            if(r&1) Rs.push_back(--r);
            l >>= 1,r >>= 1;
        }
        reverse(Rs.begin(),Rs.end());

        int maxa = -1,ret = 0;
        for(auto pos : Ls){
            ret += lower_bound(dat.at(pos).begin(),dat.at(pos).end(),maxa)-dat.at(pos).begin();
            ret += ng.at(pos).size();
            ret -= lower_bound(ng.at(pos).begin(),ng.at(pos).end(),maxa)-ng.at(pos).begin();
            maxa = max(maxa,dat.at(pos).back());
        }
        for(auto pos : Rs){
            ret += lower_bound(dat.at(pos).begin(),dat.at(pos).end(),maxa)-dat.at(pos).begin();
            ret += ng.at(pos).size();
            ret -= lower_bound(ng.at(pos).begin(),ng.at(pos).end(),maxa)-ng.at(pos).begin();
            maxa = max(maxa,dat.at(pos).back());
        }
        return ret;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,Q; cin >> N >> Q;
    vector<int> A(N);
    for(auto &a : A) cin >> a,a--;

    MergeSortTree Z(A);
    while(Q--){
        int l,r; cin >> l >> r; l--;
        cout << Z.query(l,r) << "\n";
    }
}
0