题面直达

题目描述

虱子国王尼特这天有点不舒服,它周围的 个医生立刻开出了药方:第 个医生告诉它,从这天起的第 天到第 天,它应该服用 种药,每天每种药应当服用恰好一片。注意,如果有多个医生的药方里都要求尼特在第 天服用第 种药,那尼特在第 p 天仍然只会服用一片第 种药。编号为 的药每片需要 元钱。

然而,由于尼特的疏忽,有恰好一位庸医混进了医生队伍里,但尼特并不知道哪位医生是庸医。所以它想知道,对于所有 ,如果它按照除了第 个医生之外的所有医生的药方吃药,它总共将花费多少钱。

输入格式

第一行两个正整数 ,,分别为医生数和药片种类数。

接下来一行 个正整数

接下来 行,第 行描述第 个医生。首先三个正整数 ,,,后面 个正整数 。保证 互不相同。

输出格式

输出 个非负整数,第 个表示,如果尼特认为第 个医生是庸医并除开他的药方,它总共将花费多少钱。

样例输入输出

样例输入

1
2
3
4
5
6
7
5 4
10000 1000 100 10
3 4 2 2 3
4 8 3 1 2 4
6 7 2 3 4
8 9 2 1 4
2 6 3 1 2 3
样例输出
1
87660 75640 87560 77650 66460
样例解释
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
这里仅解释输出中的第一个和第五个数。

如果第一位医生是庸医,则尼特:

在第 2,3 天会吃药片 1,2,3。花费 11100×2=22200 元。
在第 4,5,6,7 天会吃药片 1,2,3,4。花费 11110×4=44440 元。
在第 8 天会吃药片 1,2,4。花费 11010 元。
在第 9 天会吃药片 1,4。花费 10010 元。
总花费 87660 元。

如果第五位医生是庸医,则尼特:

在第 3 天会吃药片 2,3。花费 1100 元。
在第 4 天会吃药片 1,2,3,4。花费 11110 元。
在第 5 天会吃药片 1,2,4。花费 11010 元。
在第 6,7 天会吃药片 1,2,3,4。花费 11110×2=22220 元。
在第 8 天会吃药片 1,2,4。花费 11010 元。
在第 9 天会吃药片 1,4。花费 10010 元。
总花费 66460 元。

数据范围

题解

定义第 个医生的贡献值为: 其中定义为第个医生的药方中有第 种药片在第 天无其它医生开该药。

详细见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define int long long
using namespace std;
int n ,m;
int c[500005];
int l[500005] ,r[500005];
int l2[500005] ,r2[500005];
vector<int> x[500005];
int a[1000005] ,ans[500005] ,sum;
int cnt[1000005] ,cur[1000005];
int wh(int x ,int len){
return lower_bound(a+1 ,a+len+1 ,x)-a;
}
main()
{
cin >> n >> m;
for(int i=1;i<=m;i++)
cin >> c[i];
for(int i=1;i<=n;i++){
int k ,a;
cin >> l[i] >> r[i] >> k;
for(int j=1;j<=k;j++){
cin >> a;
x[a].push_back(i);
//第a号药被第i号医生开过
}
}
for(int i=1;i<=m;i++){
if(x[i].size()==0)continue;
int len=0;
for(int j=0;j<x[i].size();j++)
a[++len]=l[x[i][j]] ,a[++len]=r[x[i][j]]+1;
sort(a+1 ,a+len+1);
len=unique(a+1 ,a+len+1)-a-1;
//离散化,时间复杂度保证在O(m+K)
for(int j=0;j<x[i].size();j++){
int w=x[i][j];
l2[w]=wh(l[w] ,len) ,r2[w]=wh(r[w]+1 ,len)-1;
}
for(int j=0;j<x[i].size();j++){
int w=x[i][j];
cnt[l2[w]]++ ,cnt[r2[w]+1]--;
cur[l2[w]]^=w ,cur[r2[w]+1]^=w;
//利用x^x=0,来得出当cnt[i]=1时,贡献该1的医生编号
}
for(int j=1;j<=len;j++)
cnt[j]+=cnt[j-1] ,cur[j]^=cur[j-1];//计算前缀和和异或前缀和
for(int j=1;j<=len;j++){
if(cnt[j])//计算总共所需钱数
sum+=c[i]*(a[j+1]-a[j]);
if(cnt[j]==1)//计算cur[j]号医生的贡献值
ans[cur[j]]+=c[i]*(a[j+1]-a[j]);
cnt[j]=cur[j]=0;//清零!!!
}
}
for(int i=1;i<=n;i++)
cout << sum-ans[i] << ' ';
}