//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "基站选址": {
        "prefix": "acm-5.1线段树优化",
        "body": [
            "#include<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "#include<vector>",
            "#define LL long long",
            "#define Re register int",
            "using namespace std;",
            "const LL N=2e4+3,inf=1e18;",
            "int n,K,L[N],R[N],D[N],C[N],W[N],S[N];LL ans=inf,dp[N];vector<int>V[N];",
            "inline void in(Re &x){",
            "    int f=0;x=0;char c=getchar();",
            "    while(c<'0'||c>'9')f|=c=='-',c=getchar();",
            "    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();",
            "    x=f?-x:x;",
            "}",
            "inline LL calc(Re j,Re i){",
            "\tLL ans=0;",
            "\tfor(Re k=j+1;k<i;++k)if(L[k]>j&&R[k]<i)ans+=W[k];",
            "\treturn ans;",
            "}",
            "struct Segment_Tree{",
            "\t#define pl (p<<1)",
            "\t#define pr (p<<1|1)",
            "\t#define mid ((L+R)>>1)",
            "\tLL tr[N<<2],add[N<<2];",
            "\tinline void updata(Re p,LL v){tr[p]+=v,add[p]+=v;}",
            "\tinline void pushdown(Re p){",
            "\t\tif(add[p])updata(pl,add[p]),updata(pr,add[p]),add[p]=0;",
            "\t}",
            "\tinline void build(Re p,Re L,Re R){",
            "\t\tadd[p]=0;",
            "\t\tif(L==R){tr[p]=dp[L];return;}",
            "\t\tbuild(pl,L,mid),build(pr,mid+1,R);",
            "\t\ttr[p]=min(tr[pl],tr[pr]);",
            "\t}",
            "\tinline void change(Re p,Re L,Re R,Re l,Re r,Re v){",
            "\t\tif(l<=L&&R<=r){updata(p,v);return;}",
            "\t\tpushdown(p);",
            "\t\tif(l<=mid)change(pl,L,mid,l,r,v);",
            "\t\tif(r>mid)change(pr,mid+1,R,l,r,v);",
            "\t\ttr[p]=min(tr[pl],tr[pr]);",
            "\t}",
            "\tinline void change(Re p,Re L,Re R,Re x,Re v){",
            "\t\tif(L==R){tr[p]+=v;return;}",
            "\t\tpushdown(p);",
            "\t\tif(x<=mid)change(pl,L,mid,x,v);",
            "\t\telse change(pr,mid+1,R,x,v);",
            "\t\ttr[p]=min(tr[pl],tr[pr]);",
            "\t}",
            "\tinline LL ask(Re p,Re L,Re R,Re l,Re r){",
            "\t\tif(l<=L&&R<=r)return tr[p];",
            "\t\tLL ans=inf;pushdown(p);",
            "\t\tif(l<=mid)ans=min(ans,ask(pl,L,mid,l,r));",
            "\t\tif(r>mid)ans=min(ans,ask(pr,mid+1,R,l,r));",
            "\t\treturn ans; ",
            "\t}",
            "\t#undef mid",
            "}TR;",
            "int main(){",
            "//\tfreopen(\"123.txt\",\"r\",stdin);",
            "\tin(n),in(K);",
            "\tfor(Re i=2;i<=n;++i)in(D[i]);",
            "\tfor(Re i=1;i<=n;++i)in(C[i]);",
            "\tfor(Re i=1;i<=n;++i){",
            "\t\tin(S[i]);",
            "\t\tRe l=1,r=i;",
            "\t\twhile(l<r){",
            "\t\t\tRe mid=l+r>>1;",
            "\t\t\tif(D[mid]>=D[i]-S[i])r=mid;",
            "\t\t\telse l=mid+1;",
            "\t\t}",
            "\t\tL[i]=r;",
            "\t\tl=i,r=n;",
            "\t\twhile(l<r){",
            "\t\t\tRe mid=l+r+1>>1;",
            "\t\t\tif(D[mid]<=D[i]+S[i])l=mid;",
            "\t\t\telse r=mid-1;",
            "\t\t}",
            "\t\tR[i]=l,V[R[i]].push_back(i);",
            "\t}",
            "\tfor(Re i=1;i<=n;++i)in(W[i]);",
            "\tmemset(dp,20,sizeof(dp));",
            "\tdp[0]=0,D[0]=-1e9,C[n+1]=0;",
            "\tfor(Re k=1;k<=K;++k){",
            "\t\tTR.build(1,0,n);",
            "\t\tfor(Re i=1;i<=n+1;++i){",
            "\t\t\tLL tmp=dp[i];",
            "\t\t\tdp[i]=min(dp[i],TR.ask(1,0,n,0,i-1)+C[i]);",
            "\t\t\tfor(Re j=0,SZ=V[i].size();j<SZ;++j)TR.change(1,0,n,0,L[V[i][j]]-1,W[V[i][j]]);",
            "\t\t\tif(dp[i]!=tmp)TR.change(1,0,n,i,dp[i]-tmp);",
            "\t\t}",
            "\t\tans=min(ans,dp[n+1]);",
            "\t}",
            "\tprintf(\"%lld\\n\",ans);",
            "}",
            ""
        ],
        "description": "插入 基站选址"
    }
}