結果

問題 No.877 Range ReLU Query
コンテスト
ユーザー zelda_master
提出日時 2026-08-25 00:46:20
言語 C++14
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 241 ms / 2,000 ms
+ 721µs
コード長 1,945 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 740 ms
コンパイル使用メモリ 96,268 KB
実行使用メモリ 77,184 KB
最終ジャッジ日時 2026-08-25 00:46:28
合計ジャッジ時間 6,888 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long LL;
typedef pair<int, LL> PIL;

const int N = 100010, V = 1000000000;

struct Node {
    int l, r, cnt;
    LL sum;
};

int n, q, a[N];

struct PSegTree {
    Node seg[N * 100];
    int rt[N], idx;
    void PushUp(int u) {
        seg[u].cnt = seg[seg[u].l].cnt + seg[seg[u].r].cnt;
        seg[u].sum = seg[seg[u].l].sum + seg[seg[u].r].sum;
    }
    void Insert(int u1, int &u2, int ul, int ur, int x) {
        u2 = ++idx;
        seg[u2] = seg[u1];
        if (ul == ur) {
            ++seg[u2].cnt;
            seg[u2].sum += x;
            return;
        }
        int mid = ul + ur >> 1;
        if (mid >= x) Insert(seg[u1].l, seg[u2].l, ul, mid, x);
        else Insert(seg[u1].r, seg[u2].r, mid + 1, ur, x);
        PushUp(u2);
    }
    PIL Query(int u1, int u2, int ul, int ur, int l, int r) {
        if (l <= ul && ur <= r) return { seg[u2].cnt - seg[u1].cnt, seg[u2].sum - seg[u1].sum };
        int mid = ul + ur >> 1;
        PIL ret = { 0, 0LL };
        if (mid >= l) {
            PIL res = Query(seg[u1].l, seg[u2].l, ul, mid, l, r);
            ret.first += res.first, ret.second += res.second;
        }
        if (mid + 1 <= r) {
            PIL res = Query(seg[u1].r, seg[u2].r, mid + 1, ur, l, r);
            ret.first += res.first, ret.second += res.second;
        }
        return ret;
    }
};
PSegTree pst;

int main() {
    // freopen("query.in", "r", stdin);
    // freopen("query.out", "w", stdout);

    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        pst.Insert(pst.rt[i - 1], pst.rt[i], 1, V, a[i]);
    }
    while (q--) {
        int op, l, r, x;
        scanf("%d%d%d%d", &op, &l, &r, &x);
        PIL p = pst.Query(pst.rt[l - 1], pst.rt[r], 1, V, x + 1, V);
        printf("%lld\n", p.second - 1LL * p.first * x);
    }

    return 0;
}
0