题解

#include <bits/stdc++.h>
#define int long long

using namespace std;

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;
namespace my_namespace {
	
const int N = 8e5 + 10, M = 1e6 + 10;

int a[N], c[N], b[N], q[N], ans[N];

struct Node {
	int l, r, d;
};
vector<Node> s[N];
signed main() {
    freopen("doctor.in", "r", stdin);
    freopen("doctor.out", "w", stdout);
    int n, m;
	fin >> n >> m;
	for (int i = 1; i <= m; ++i) fin >> c[i];
	
	for (int i = 1; i <= n; ++i) {
		int l, r, x, y;
		fin >> l >> r >> x;
		while (x --) {
			fin >> y;
			s[y].push_back({l, r, i});
		}
	} 
	int tot = 0;
	for (int i = 1; i <= m; ++i) {
		int sz = s[i].size();
		int cnt = 0;
		int len = 0;
		for (int j = 0; j < sz; ++j) {
			q[++cnt] = s[i][j].l - 1; q[++cnt] = s[i][j].r;
		}
		sort(q + 1, q + cnt + 1);
		cnt = unique(q + 1, q + cnt + 1) - q - 1;
		for (int j = 0; j < sz; ++j) {
			int l = lower_bound(q + 1, q + cnt + 1, s[i][j].l - 1) - q;
			int r = lower_bound(q + 1, q + cnt + 1, s[i][j].r) - q;
			//cout << l << " " << r << endl;
			a[l + 1] += 1;
			a[r + 1] -= 1; 
			s[i][j].l = l, s[i][j].r = r;
		} 
		for (int j = 2; j <= cnt; ++j) {
			a[j] += a[j - 1];
			if (a[j] > 0) len += q[j] - q[j - 1];
		}
		
		for (int j = 2; j <= cnt; ++j) {
			if (a[j] == 1) a[j] = q[j] - q[j - 1]; else a[j] = 0;
			b[j] = b[j - 1] + a[j];
		}
		for (int j = 0; j < sz; ++j) {
			ans[s[i][j].d] += c[i] * (b[s[i][j].r] - b[s[i][j].l]); 
		}
		tot += len * c[i];
		
		for (int j = 0; j <= cnt + 1; ++j) a[j] = b[j] = 0;
	}
	for (int i = 1; i <= n; ++i) fout << tot - ans[i] << " \n"[i == n];
    return 0;
}

}  // namespace my_namespace
signed main() {
    return my_namespace::main();
}