题解 - 题解 - 青藤 OJ

显然可以对于每只虱子分开考虑。如果没有某一项不算的话，只需要求出这些区间的并的大小，再乘上这只虱子的难受程度即可。

但是现在有撤销，容易发现一个操作取消只会影响那些恰好被一个区间覆盖的点，于是统计这些点计算贡献即可。时间复杂度 O(nlogn)

#include <bits/stdc++.h>
#define Gc() getchar()

#define Me(x, y) memset(x, y, sizeof(x))

#define Mc(x, y) memcpy(x, y, sizeof(x))

#define d(x, y) ((m) * (x - 1) + (y))

#define R(n) (rnd() % (n) + 1)

#define Pc(x) putchar(x)

#define LB lower_bound

#define UB upper_bound

#define PB push_back

using ll = long long;
using db = double;
using lb = long db;
using ui = unsigned;
using ull = unsigned ll;
using namespace std;
const int N = 1e6 + 5, M = N * 4 + 5, K = 1e5 + 5, mod = 1e9 + 7, Mod = mod - 1, INF = 1e9 + 7;
const db eps = 1e-5;
mt19937 rnd(time(0));
struct IO {
    static const int S = 1 << 21;
    char buf[S], *p1, *p2;
    int st[105], Top;
    ~IO() { clear(); }
    inline void clear() {
        fwrite(buf, 1, Top, stdout);
        Top = 0;
    }
    inline void pc(const char c) {
        Top == S && (clear(), 0);
        buf[Top++] = c;
    }
    inline char gc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
    }
    inline IO& operator>>(char& x) {
        while (x = gc(), x == ' ' || x == '\n' || x == '\r')
            ;
        return *this;
    }
    template <typename T>
    inline IO& operator>>(T& x) {
        x = 0;
        bool f = 0;
        char ch = gc();
        while (ch < '0' || ch > '9') {
            if (ch == '-')
                f ^= 1;
            ch = gc();
        }
        while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = gc();
        f ? x = -x : 0;
        return *this;
    }
    inline IO& operator<<(const char c) {
        pc(c);
        return *this;
    }
    template <typename T>
    inline IO& operator<<(T x) {
        if (x < 0)
            pc('-'), x = -x;
        do {
            st[++st[0]] = x % 10, x /= 10;
        } while (x);
        while (st[0]) pc('0' + st[st[0]--]);
        return *this;
    }
} fin, fout;
int n, m, k, x, y, z, l, r, A[N], Bh, B[N], Sum[N], Ct[N];
ll Ans[N], ToT;
struct Node {
    int l, r, id;
};
vector<Node> S[N];
int main() {
    freopen("doctor.in", "r", stdin);
    freopen("doctor.out", "w", stdout);
    int i, j;
    fin >> n >> m;
    for (i = 1; i <= m; i++) fin >> A[i];
    for (i = 1; i <= n; i++) {
        fin >> l >> r >> x;
        while (x--) fin >> y, S[y].PB((Node){ l, r, i });
    }
    for (i = 1; i <= m; i++) {
        Bh = 0;
        for (Node j : S[i]) B[++Bh] = j.l, B[++Bh] = j.r + 1;
        sort(B + 1, B + Bh + 1);
        Bh = unique(B + 1, B + Bh + 1) - B - 1;
        for (j = 0; j < S[i].size(); j++)
            Sum[S[i][j].l = LB(B + 1, B + Bh + 1, S[i][j].l) - B]++,
                Sum[S[i][j].r = LB(B + 1, B + Bh + 1, S[i][j].r + 1) - B]--;
        for (j = 1; j <= Bh; j++)
            Sum[j] += Sum[j - 1], Sum[j] && (ToT += 1ll * (B[j + 1] - B[j]) * A[i]),
                Ct[j] = Ct[j - 1] + (Sum[j] == 1 ? B[j + 1] - B[j] : 0);
        for (Node j : S[i]) Ans[j.id] += 1ll * (Ct[j.r - 1] - Ct[j.l - 1]) * A[i];
        for (j = 1; j <= Bh; j++) Sum[j] = 0;
    }
    for (i = 1; i <= n; i++) fout << ToT - Ans[i] << " \n"[i == n];
}