Description

给出n个小区间[l,r],更新这段区间的代价为c，求覆盖一段区间[m,e]的最小值。

Solution

线段树优化 dp。

线段树维护区间内最小值，即从 m-1 时刻到 i 时刻要用的最少奶牛。

然后右端点排序，每次查询更新即可。

复杂度 O(挺大)

Code

 

// By YoungNeal#include
     
      #include
      
       #include
       
        #include
        
         #define N 10005#define M 86650#define int long longusing namespace std;int f[M];int n,L,R,tot=1;struct NNode{    int l,r,val;    friend bool operator<(NNode a,NNode b){        return a.r
         
          >1;    build(l,mid,node[cur].lch);    build(mid+1,r,node[cur].rch);    node[cur].l=node[node[cur].lch].l;    node[cur].r=node[node[cur].rch].r;    node[cur].minn=min(node[node[cur].lch].minn,node[node[cur].rch].minn);}int query(int l,int r,int cur){    if(l<=node[cur].l&&node[cur].r<=r) return node[cur].minn;    int mid=node[cur].l+node[cur].r>>1;    int minn=0x3f3f3f3f;    if(l<=mid) minn=min(minn,query(l,r,node[cur].lch));    if(mid
          
           >1; if(l<=mid) update(l,r,c,node[cur].lch); if(mid
           
            =0x3f3f3f3f?"-1":"%lld\n",f[R]); return 0;}