题目

8 15 3
1 5 2
13 14 1
5 8 3
8 14 2
14 15 1
9 12 1
12 15 2
4 6 1

10

分析

• 线段树覆盖？
• 贪心？
• 区间修改，查询最大值

代码

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 struct sb
 8 {
 9     int st,ed,num;
10 }a[200001];
11 struct AA
12 {
13     int l,r,add,sum,mx;
14 }t[200100*4];
15 bool cmp(sb a,sb b)
16 {
17     if (a.ed!=b.ed)
18     return a.ed<b.ed?true:false; 
19     else return a.st<b.st?true:false;
20 }
21 void build(int a,int b,int k)
22 {
23     t[k].l=a; t[k].r=b;
24     if (a==b) return;
25     int mid=(a+b)/2;
26     build(a,mid,k*2);
27     build(mid+1,b,k*2+1);
28 }
29 void lazy(int k,int m)
30 {
31     if (t[k].add)
32     {
33         t[k*2].add+=t[k].add;
34         t[k*2+1].add+=t[k].add;
35         t[k*2].mx+=t[k].add;
36         t[k*2+1].mx+=t[k].add;
37         t[k].add=0; 
38     }
39 }
40 void change(int x,int y,int z,int k)
41 {
42     if (t[k].l>=x&&t[k].r<=y)
43     {
44         t[k].add+=z;
45         t[k].mx+=z;
46         return;
47     }
48     lazy(k,t[k].r-t[k].l+1);
49     int mid=(t[k].l+t[k].r)/2;
50     if (y<=mid) change(x,y,z,k*2);
51     else if (x>mid) change(x,y,z,k*2+1);
52     else
53     {
54         change(x,mid,z,k*2); 
55         change(mid+1,y,z,k*2+1);
56     }
57     t[k].sum=t[k*2].sum+t[k*2+1].sum;
58     t[k].mx=max(t[k*2].mx,t[k*2+1].mx);
59 }
60 int check(int x,int y,int k)
61 {
62     if (t[k].l>=x&&t[k].r<=y)
63         return t[k].mx;
64     lazy(k,t[k].r-t[k].l+1);
65     int mid=(t[k].l+t[k].r)/2;
66     int val=0;
67     if (x<=mid) val=max(val,check(x,y,k*2));
68     if (y>mid) val=max(val,check(x,y,k*2+1));
69     return val;
70 }
71 int main()
72 {
73     int k,n,c;
74     scanf("%d%d%d",&k,&n,&c);
75     for (int i=1;i<=k;i++) scanf("%d%d%d",&a[i].st,&a[i].ed,&a[i].num);
76     sort(a+1,a+1+k,cmp);
77     build(1,20001,1);
78     int ans=0;
79     for (int i=1;i<=k;i++)
80     {
81         int maxn=check(a[i].st,a[i].ed-1,1);
82         ans+=min(a[i].num,c-maxn);
83         change(a[i].st,a[i].ed-1,min(a[i].num,c-maxn),1);
84     }
85     cout<<ans;
86     return 0;
87 }