LuoguP2605 [ZJOI2010]基站选址 题解

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=20010;
int n,m,d[N],c[N],s[N],w[N],inf=2e9,f[N],tr[N<<2],tag[N<<2],st[N],ed[N];
vector<int> v[N];
#define IT vector<int>::iterator
#define LW(x) lower_bound(d+1,d+n+1,x)-d
#define mid (l+r>>1)
#define ls x<<1,l,mid
#define rs x<<11,mid+1,r
#define UP(x) tr[x]=min(tr[x<<1],tr[x<<11])
#define PD(x) tag[x]&&(Add(x<<1,tag[x]),Add(x<<11,tag[x]),tag[x]=0)
IT It;
I void Add(CI x,CI val){tr[x]+=val;tag[x]+=val;return ;}
I void build(CI x,CI l,CI r){if(tag[x]=0,l==r) return void(tr[x]=f[l]);build(ls),build(rs),UP(x);}
I void update(CI x,CI l,CI r,CI L,CI R,CI val){if(L>R) return ;if(L<=l&&r<=R) return Add(x,val);PD(x);if(L<=mid) update(ls,L,R,val);if(R>mid) update(rs,L,R,val);UP(x);}
I int query(CI x,CI l,CI r,CI L,CI R){if(L>R) return inf;if(L<=l&&r<=R) return tr[x];PD(x);RI res=inf;if(L<=mid) res=min(res,query(ls,L,R));if(R>mid) res=min(res,query(rs,L,R));return res;}
int main(){
RI i,j,S;read(n,m);for(d[1]=0,i=2;i<=n;i++) read(d[i]);for(i=1;i<=n;i++) read(c[i]);for(i=1;i<=n;i++) read(s[i]);for(i=1;i<=n;i++) read(w[i]);++m,++n,d[n]=w[n]=inf;
for(i=1;i<=n;i++) st[i]=LW(d[i]-s[i]),ed[i]=LW(d[i]+s[i]),d[ed[i]]>d[i]+s[i]&&ed[i]--,v[ed[i]].push_back(i);for(S=0,i=1;i<=n;i++) for(f[i]=S+c[i],It=v[i].begin();It!=v[i].end();It++) S+=w[*It];
for(S=f[n],i=2;i<=m;S=min(S,f[n]),i++) for(build(1,1,n),j=1;j<=n;j++) for(f[j]=query(1,1,n,1,j-1)+c[j],It=v[j].begin();It!=v[j].end();It++) update(1,1,n,1,st[*It]-1,w[*It]);return writeln(S),0;
}