题解 P4559 【[JSOI2018]列队】

眠ㅤㅤㅤ · 2019-09-24 13:15:04 · 个人记录

constexpr auto Inf = 0X3F3F3F3F;
#ifndef LOCAL
    #include <bits/stdc++.h>
#endif
typedef long long LL;
using namespace std;

namespace IO {
    inline LL read() {
        LL o = 0, f = 1; char c = getchar();
        while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
        while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
        return o * f;
    }
    inline char recd() {
        char o; while ((o = getchar()) < '0' || o > '9'); return o;
    }
    inline double reod() {
        double o = read(), f = 1; char c; 
        while ((c = getchar()) > '/' && c < ':') o += (c - '0') / (f *= 10);
        return o;
    }
}
using namespace IO;

const int SIZE = 1E6 + 7, Mod = 1E9 + 7;

struct Node {
    int L, R, w; LL S;
} Node[SIZE << 6]; int Ind, Root[SIZE];

void Ins(int &now, int pre, int L, int R, int w) {
    now = ++Ind;
    Node[now] = Node[pre];
    Node[now].w++, Node[now].S += w;
    if (L == R) return;
    int M = (L + R) >> 1;
    if (w > M) Ins(Node[now].R, Node[pre].R, M + 1, R, w);
    else Ins(Node[now].L, Node[pre].L, L, M, w);
}

LL Ask(int now, int pre, int L, int R, LL T, LL K) {
    int w = Node[now].w - Node[pre].w;
    if (!w) return 0;
    if (L >= K + T) return Node[now].S - Node[pre].S - (((((K + T) << 1) + w - 1) * w) >> 1);
    if (R <= K + T + w - 1) return -(Node[now].S - Node[pre].S - (((((K + T) << 1) + w - 1) * w) >> 1));
    int M = (L + R) >> 1;
    return Ask(Node[now].L, Node[pre].L, L, M, T, K) + Ask(Node[now].R, Node[pre].R, M + 1, R, T + Node[Node[now].L].w - Node[Node[pre].L].w, K);
}

int main() {
    int N = read(), M = read();
    for (int pos = 1, w; pos <= N; pos++)
        w = read(), Ins(Root[pos], Root[pos - 1], 1, 1E6, w);
    while (M--) {
        int L = read(), R = read(), K = read();
        printf("%lld\n", Ask(Root[R], Root[L - 1], 1, 1E6, 0, K));
    }
}