結果

問題 No.1270 Range Arrange Query
コンテスト
ユーザー Nachia
提出日時 2020-10-23 23:36:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,106 ms / 7,000 ms
コード長 3,390 bytes
コンパイル時間 2,558 ms
コンパイル使用メモリ 186,140 KB
実行使用メモリ 5,476 KB
最終ジャッジ日時 2024-07-21 13:33:17
合計ジャッジ時間 8,267 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

template<
    class S,
    S(*op)(S a, S b),
    S(*e)()
>
struct segtree {
private:
    int N;
    vector<S> V;
public:

    segtree(int n) {
        N = 1; while (N < n) N *= 2;
        V.assign(N * 2, e());
    }
    segtree(vector<S> A) {
        N = 1; while (N < A.size()) N *= 2;
        V.assign(N * 2, e());
        rep(i, A.size()) V[N + i] = A[i];
        for (int i = N - 1; i >= 1; i--)
            V[i] = op(V[i * 2], V[i * 2 + 1]);
    }

    void set(int p, S v) {
        p += N;
        V[p] = v;
        while (p != 1) {
            p /= 2;
            V[p] = op(V[p * 2], V[p * 2 + 1]);
        }
    }
    S get(int p) {
        p += N;
        return V[p];
    }

    S prod(int l, int r) {
        S ans_l = e(), ans_r = e();
        l += N; r += N;
        while (l < r) {
            if (l & 1) ans_l = op(ans_l, V[l++]);
            if (r & 1) ans_r = op(V[--r], ans_r);
            l /= 2; r /= 2;
        }
        return op(ans_l, ans_r);
    }
};

struct S { int a, b, x; };
S op(S l, S r) {
    S res;
    res.a = l.a + r.a;
    res.b = l.b + r.b;
    res.x = min(min(l.b + r.x, l.x + r.a), l.b + r.a);
    return res;
}
S e() { return { 0, 0, 100000000 }; }
using RQ = segtree<S, op, e>;

struct S2 { int a; };
S2 op2(S2 l, S2 r) {
    S2 res;
    res.a = l.a + r.a;
    return res;
}
S2 e2() { return { 0 }; }
using RQ2 = segtree<S2, op2, e2>;

int N, Q;
pair<int, int> A[20000];
int I[20000];
RQ G(1);
RQ2 GL(1), GR(1);

int mo_l = 0;
int mo_r = 0;
int mo_reverses = 0;

void moverange(int l, int r) {
    for (; mo_l > l; mo_l--) {
        G.set(I[mo_l - 1], { 0,0,0 });
        GL.set(I[mo_l - 1], { 0 });
        mo_reverses += GR.prod(0, I[mo_l - 1]).a;
        mo_reverses += GL.prod(I[mo_l - 1] + 1, N).a;
    }
    for (; mo_r < r; mo_r++) {
        G.set(I[mo_r], { 0,0,0 });
        GR.set(I[mo_r], { 0 });
        mo_reverses += GR.prod(0, I[mo_r]).a;
        mo_reverses += GL.prod(I[mo_r] + 1, N).a;
    }
    for (; mo_l < l; mo_l++) {
        G.set(I[mo_l], { 1,0,0 });
        GL.set(I[mo_l], { 1 });
        mo_reverses -= GR.prod(0, I[mo_l]).a;
        mo_reverses -= GL.prod(I[mo_l] + 1, N).a;
    }
    for (; mo_r > r; mo_r--) {
        G.set(I[mo_r - 1], { 0,1,0 });
        GR.set(I[mo_r - 1], { 1 });
        mo_reverses -= GR.prod(0, I[mo_r - 1]).a;
        mo_reverses -= GL.prod(I[mo_r - 1] + 1, N).a;
    }
}

int TotalReverses = 0;

struct Query {
    int l, r, i;
    bool operator<(Query b) const { return r < b.r; }
};
vector<Query> queries[100];
int ans[20000];

int main() {
    cin >> N >> Q;
    rep(i, N) { int a; cin >> a; A[i] = { a,i }; }
    sort(A, A + N);
    rep(i, N) I[A[i].second] = i;

    rep(q, Q) {
        int l, r; cin >> l >> r; l--;
        queries[l / 200].push_back({ l,r,q });
    }
    rep(i, 100) sort(queries[i].begin(), queries[i].end());

    G = RQ(vector<S>(N, S{ 0,0,0 }));
    GL = RQ2(vector<S2>(N, S2{ 0 }));
    GR = RQ2(vector<S2>(N, S2{ 1 }));

    moverange(0, N);
    TotalReverses = mo_reverses;

    rep(i, 100) {
        for (auto q : queries[i]) {
            moverange(q.l, q.r);
            ans[q.i] = TotalReverses - mo_reverses + G.prod(0, N).x * (q.r - q.l);
        }
    }

    rep(i, Q) cout << ans[i] << endl;

    return 0;
}
0