题解 P1607 【[USACO09FEB]庙会班车Fair Shuttle】
Starria的脑残粉
2017-10-29 20:56:46
想刷一下线段树题然后就写了个线段树。。
排序后贪心思路是显然正确的因为找不出更优解。。
线段树维护区间加区间max
连标记下传都不用,直接永久化好了
可以说很傻了
贴代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
int k,n,c,ans,ma[1000000],lazy[1000000];
struct lsg{int x,y,z;}a[1000000];
int read(){
char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
int kk=1,k=0;if (c=='-')kk=-1,c=getchar();
while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();return kk*k;
}int findit(int x,int y,int l,int r,int d){//查询max操作
if (x<=l&&y>=r)return ma[d];
int m=(l+r)/2,ans=lazy[d];
if (x<=m)ans=max(ans,findit(x,y,l,m,d*2)+lazy[d]);
if (y>m)ans=max(ans,findit(x,y,m+1,r,d*2+1)+lazy[d]);
return ans;
}void putit(int x,int y,int z,int l,int r,int d){//区间加
if (x<=l&&y>=r){lazy[d]+=z;ma[d]+=z;return;}
int m=(l+r)/2;if (x<=m)putit(x,y,z,l,m,d*2);
if (y>m)putit(x,y,z,m+1,r,d*2+1);
ma[d]=max(ma[d*2],ma[d*2+1])+lazy[d];
}bool pd(lsg x,lsg y){return x.y<y.y;}//按右端点排序
int main(){
k=read();n=read();c=read();for (int i=1;i<=k;i++)a[i].x=read(),a[i].y=read()-1,a[i].z=read();
sort(a+1,a+1+k,pd);for (int i=1;i<=k;i++){
int x=findit(a[i].x,a[i].y,1,n,1),y=min(c-x,a[i].z);//贪心
ans+=y;putit(a[i].x,a[i].y,y,1,n,1);
}cout<<ans<<endl;
}
```