治病

首先我们要算出，如果不忽略任何医生，尼特花费的钱数。根据题意我们知道，对于某种药片，尼特吃这种药片的时间就是所有医生药方里的时间的并集，也就是给出一些区间让你求并。这是经典问题，按照左端点从小到大排序，维护当前最大的右端点即可。

如果忽略某个医生，只需要找到只被这一个医生覆盖的 (药片,时间) 二元组，把这些二元组的贡献减掉。对每种药片分开考虑，也就是对每个区间，求出只被这一个区间覆盖的位置的总长度。首先用差分求出每个位置被覆盖了多少次，找出只被覆盖一次的位置，把这些位置的权值赋值成 1，对权值做前缀和，然后求出每个区间内的位置的权值之和，就是只被这一个区间覆盖的位置的总长度。

所有差分、前缀和都需要在离散化之后的坐标上进行，瓶颈在于离散化，总时间复杂度为 $O((\sum K)\log (\sum K)+n+m)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct e{
    int p;
    int t;
    int d;
};
struct s{
    int l;
    int r;
    int d;
};
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    vector<int> c(m);
    for(int i=0;i<m;i++){
        cin>>c[i];
    }
    vector<vector<s>> g(m);
    for(int i=0;i<n;i++){
        int L,R,K;
        cin>>L>>R>>K;
        vector<int> x(K);
        for(int j=0;j<K;j++){
            cin>>x[j];
            x[j]--;
        }
        for(int y:x){
            g[y].push_back({L,R,i});
        }
    }
    int T=0;
    vector<int> r(n,0);
    for(int x=0;x<m;x++){
        if(g[x].empty())continue;
        vector<e> a;
        for(auto &t:g[x]){
            a.push_back({t.l,1,t.d});
            a.push_back({t.r+1,-1,t.d});
        }
        sort(a.begin(),a.end(),[](const e&i,const e&j){
            if(i.p!=j.p)return i.p<j.p;
            return i.t<j.t;
        });
        set<int> b;
        unordered_map<int,int> f;
        int U=0;
        int l=a[0].p;
        int j=0;
        while(j<a.size()){
            int p=a[j].p;
            if(l<p){
                int seg=p-l;
                if(!b.empty()){
                    U+=seg;
                    if(b.size()==1){
                        int d=*b.begin();
                        f[d]+=seg;
                    }
                }
            }
            int k=j;
            while(k<a.size()&&a[k].p==p){
                if(a[k].t==-1)b.erase(a[k].d);
                else b.insert(a[k].d);
                k++;
            }
            l=p;
            j=k;
        }
        T+=c[x]*U;
        for(auto &p:f){
            r[p.first]+=c[x]*p.second;
        }
    }
    for(int i=0;i<n;i++){
        cout<<T-r[i]<<' ';
    }
    return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct e{
    int p;
    int t;
    int d;
};
struct s{
    int l;
    int r;
    int d;
};
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    vector<int> c(m);
    for(int i=0;i<m;i++){
        cin>>c[i];
    }
    vector<vector<s>> g(m);
    for(int i=0;i<n;i++){
        int L,R,K;
        cin>>L>>R>>K;
        vector<int> x(K);
        for(int j=0;j<K;j++){
            cin>>x[j];
            x[j]--;
        }
        for(int y:x){
            g[y].push_back({L,R,i});
        }
    }
    int T=0;
    vector<int> r(n,0);
    for(int x=0;x<m;x++){
        if(g[x].empty())continue;
        vector<e> a;
        for(auto &t:g[x]){
            a.push_back({t.l,1,t.d});
            a.push_back({t.r+1,-1,t.d});
        }
        sort(a.begin(),a.end(),[](const e&i,const e&j){
            if(i.p!=j.p)return i.p<j.p;
            return i.t<j.t;
        });
        set<int> b;
        unordered_map<int,int> f;
        int U=0;
        int l=a[0].p;
        int j=0;
        while(j<a.size()){
            int p=a[j].p;
            if(l<p){
                int seg=p-l;
                if(!b.empty()){
                    U+=seg;
                    if(b.size()==1){
                        int d=*b.begin();
                        f[d]+=seg;
                    }
                }
            }
            int k=j;
            while(k<a.size()&&a[k].p==p){
                if(a[k].t==-1)b.erase(a[k].d);
                else b.insert(a[k].d);
                k++;
            }
            l=p;
            j=k;
        }
        T+=c[x]*U;
        for(auto &p:f){
            r[p.first]+=c[x]*p.second;
        }
    }
    for(int i=0;i<n;i++){
        cout<<T-r[i]<<' ';
    }
    return 0;
}