题解 P1607 【[USACO09FEB]庙会班车Fair Shuttle】

2017-10-29 20:56:46


想刷一下线段树题然后就写了个线段树。。

排序后贪心思路是显然正确的因为找不出更优解。。

线段树维护区间加区间max

连标记下传都不用,直接永久化好了

可以说很傻了

贴代码:

#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;
}