結果

問題 No.1270 Range Arrange Query
コンテスト
ユーザー Kude
提出日時 2020-10-24 11:35:04
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,893 bytes
コンパイル時間 3,152 ms
コンパイル使用メモリ 192,760 KB
実行使用メモリ 25,860 KB
最終ジャッジ日時 2024-07-21 15:07:47
合計ジャッジ時間 30,842 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >= 0; --i)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;

template <class S, S (*op)(S, S), S (*e)(), int update_query_num=1000000, int height=20> struct persistent_segtree {
    struct Node {
        Node *lch, *rch;
        S d;
    };
    Node node_pool[1 + (height + 1) * update_query_num];
    int last_node = 0;
    Node *nil = &node_pool[0];
    Node *root[1 + update_query_num];
    int last_root = 0;
    const int n;
    persistent_segtree(int n): n(n) {
        assert(n <= (1 << height));
        nil->lch = nil->rch = nil;
        nil->d = e();
        root[0] = nil;
    }
    int set(int p, S x, int rev=-1) {
        Node *now = (rev == -1 ? root[last_root] : root[rev]);
        Node *path[height + 1];
        path[0] = now;
        bool took_left[height];
        int idx = 0;
        int l = 0, r = n;
        while(r - l != 1) {
            int m = (l + r) / 2;
            if (p < m) {
                now = now->lch;
                took_left[idx] = true;
                r = m;
            } else {
                now = now->rch;
                took_left[idx] = false;
                l = m;
            }
            path[++idx] = now;
        }
        Node *pre = &node_pool[++last_node];
        pre->d = x;
        for(--idx; idx >= 0; --idx) {
            Node *nd = &node_pool[++last_node];
            if (took_left[idx]) {
                nd->lch = pre;
                nd->rch = path[idx]->rch;
            } else {
                nd->lch = path[idx]->lch;
                nd->rch = pre;
            }
            nd->d = op(nd->lch->d, nd->rch->d);
            pre = nd;
        }
        root[++last_root] = pre;
        return last_root;
    }
    S get(int p, int rev=-1) {
        Node *now = (rev == -1 ? root[last_root] : root[rev]);
        int l = 0, r = n;
        while(r - l != 1) {
            int m = (r + l) / 2;
            if (p < m) {
                now = now->lch;
                r = m;
            } else {
                now = now->rch;
                l = m;
            }
        }
        return now->d;
    }
    S prod(int l, int r, int rev=-1) {
        Node *now = (rev == -1 ? root[last_root] : root[rev]);
        return prod_sub(l, r, 0, n, now);
    }
    S prod_sub(int l, int r, int lb, int rb, Node *x) {
        if (x == nil) return e();
        if (r <= lb || rb <= l) return e();
        if (l <= lb && rb <= r) return x->d;
        int m = (lb + rb) / 2;
        return op(
            prod_sub(l, r, lb, m, x->lch),
            prod_sub(l, r, m, rb, x->rch)
        );
    }

    std::vector<S> reconstruct_array(int rev=-1) {
        Node *rt = (rev == -1 ? root[last_root] : root[rev]);
        std::vector<S> ret;
        ret.reserve(n);
        int l = 0, r = n;
        struct node_range {
            Node *x;
            int l, r;
        } nr[height];
        nr[0] = {rt, 0, n};
        for(int idx = 0; idx >= 0;) {
            Node *now = nr[idx].x;
            int l = nr[idx].l, r = nr[idx].r;
            --idx;
            if (r - l == 1) {
                ret.push_back(now->d);
            } else {
                int m = (r + l) / 2;
                nr[++idx] = {now->rch, m, r};
                nr[++idx] = {now->lch, l, m};
            }
        }
        return ret;
    }
};

int op(int x, int y) {return x + y;}
int e() {return 0;}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n, q;
    scanf("%d%d", &n, &q);
    VI a(n);
    rep(i, n) scanf("%d", a.data() + i);
    const int MX = 20001;
    persistent_segtree<int, op, e, 20000, 15> st_f(MX), st_b(MX);
    VI s_f(n+1), s_b(n+1);
    int now = 0;
    rep(i, n) {
        now += st_f.prod(a[i] + 1, MX);
        s_f[i+1] = now;
        st_f.set(a[i], st_f.get(a[i]) + 1);
    }
    now = 0;
    rrep(i, n) {
        now += st_b.prod(0, a[i]);
        s_b[i] = now;
        st_b.set(a[i], st_b.get(a[i]) + 1);
    }
    while(q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        --l, --r;
        int ans = s_f[l] + s_b[r+1];
        auto arr_f = st_f.reconstruct_array(l), arr_b = st_b.reconstruct_array(n-r-1);
        int acc = 0;
        rep(x, MX) {
            ans += arr_f[x] * acc;
            acc += arr_b[x];
        }
        rep(x, MX-1) arr_f[x+1] += arr_f[x], arr_b[x+1] += arr_b[x];
        int t = 2e9;
        for(int x = 1; x < MX; ++x) {
            int nt = arr_f[MX-1] - arr_f[x] + arr_b[x-1];
            chmin(t, nt);
        }
        ans += t * (r - l + 1);
        printf("%d\n", ans);
    }
}
0