Lflame

【bzoj3838】Raper 线段树神题....

    虽然说是神题..我觉得还是因为我太弱啦...

    题意:

    你需要生产k张光盘。每张光盘需要经过两道工序:先在A工厂进行挤压,然后送到B工厂涂上反光层。

    共有n天时间,你知道每天A,B两家工厂的收费。一家工厂一天只能对一张光盘进行操作。同一天内一张光盘先后在A,B工厂被操作是允许的。你可以假定将只经过A操作的半成品暂存起来不需花费额外代价。

求出生产k张光盘的最小总花费。

    (n,k <= 500000  , bz总时限 60 s)


    首先,我们可以将其转化为括号序列,'('表示 A 工厂做操作,')'表示 B 工厂做操作,那么问题转化为求一个类似于 "()()()()()()()()...."的括号序列的一个合法子序列,使得子序列中有 k 个括号对且代价和最小。

    考虑每次选出和尽量小的两个括号,显然,我们只需要每时每刻保证选出的括号序列合法,即可得到最优解。也就是说,将括号序列转化为+-1过后,每一个前缀和都需要大于等于 0。

    设 s[] 为前缀和。如果我们选出了 "()" 的两个括号,则会使得这两个括号间的 s 加 1;如果我们选出了")("的两个括号,则会使得这两个括号间的 s 减 1,也就是说我们要选这两个括号的前提是其间的 s 最小值大于 0。

  

    好的,来理一理思路,我们现在要做的是支持做两个操作 :找到添加后合法的两个括号,以及修改连续一段的 s 值。于是考虑用线段树来维护。

    由于有区间修改,不可以直接维护选取")("的最优括号使得其间的 s 最小值大于 0 ,因为这样的信息是需要一直向下修改到叶子结点才行的。

    那么我们换一种方式,对于线段树的每个结点 t ,存下来 t 所管理的区间[ l , r ] 中选取 ")(" 的最优括号,使得括号间的 s 最小值大于 [l , r] 间的 s 最小值。这样的话,区间修改时,完整的被覆盖到的区间信息并不会被影响,所以支持区间修改。但是我们需要的并不是这个呀 ? 我们在位置 0 增加一个 0,那么线段树根节点所管理的区间的 s 最小值一定为 0,这便是我们需要的。

    这道题的思路便是这样,自己 YY 一下便可以搞出来了。

    

    不想自己 YY 的话,再继续看吧....

    具体来讲,令 A 为选取的左括号, B 为选取的右括号。那么以下为具体需要存储的信息。 ( %%% Claris )

    va:A≤B情况的最优解。

    vb:A>B情况的最优解,且满足[A,B−1]的区间s s最小值大于当前区间的s最小值。

    vc:A>B情况的最优解。

    aa:区间内代价最小的A。

    ab:区间内代价最小的B。

    ba:区间内代价最小的A,满足[st,A−1]的区间s最小值大于区间s最小值。

    bb:区间内代价最小的B,满足[B,en]的区间s s最小值大于区间s最值。

    vm:区间s最小值。

    tag:区间增量标记。

    只需要维护这些即可...

    

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define mid ((ll+rr)>>1)

using namespace std;


int K , n ;

int A[500005] , B[500005] , T[500005];

const int INF=(1<<30)-1 ;


struct couples

{

int l,r ;

couples(int _l=0,int _r=0) { l=_l , r=_r ; }

};


couples operator+ (const couples &a,const couples &b)

{

if(A[a.l]+B[a.r]<A[b.l]+B[b.r])return a;

return b;

}


bool operator==(const couples &a,const couples &b)

{

return a.l==b.l && a.r==b.r ;

}


//%%%%%%%%%%Claris

struct Segment_Tree

{

int ndnum , lc[1000005] , rc[1000005] , aa[1000005] , ab[1000005] , ba[1000005] , bb[1000005] , vm[1000005] ;

int tag[1000005] , root;

couples va[1000005],vb[1000005],vc[1000005] ;

inline int news(){ return ++ndnum ; }


void update(int s){

va[s]=va[lc[s]]+va[rc[s]]+couples(aa[lc[s]],ab[rc[s]]) , vc[s]=vc[lc[s]]+vc[rc[s]]+couples(aa[rc[s]],ab[lc[s]]) , vb[s]=vb[lc[s]]+vb[rc[s]];

aa[s]=(A[aa[lc[s]]]>A[aa[rc[s]]]?aa[rc[s]]:aa[lc[s]]) ;

ab[s]=(B[ab[lc[s]]]>B[ab[rc[s]]]?ab[rc[s]]:ab[lc[s]]) ;

if(vm[lc[s]]<vm[rc[s]]){

vb[s]=vb[s]+vc[rc[s]]+couples(aa[rc[s]],bb[lc[s]]) ;

ba[s]=ba[lc[s]] , bb[s]=(B[ab[rc[s]]]<B[bb[lc[s]]]?ab[rc[s]]:bb[lc[s]]) ;

vm[s]=vm[lc[s]] ;

}

if(vm[lc[s]]>vm[rc[s]]){

vb[s]=vb[s]+vc[lc[s]]+couples(ba[rc[s]],ab[lc[s]]) ;

ba[s]=(A[ba[rc[s]]]<A[aa[lc[s]]]?ba[rc[s]]:aa[lc[s]]) , bb[s]=bb[rc[s]] ;

vm[s]=vm[rc[s]] ;

}

if(vm[lc[s]]==vm[rc[s]]){

vb[s]=vb[s]+couples(ba[rc[s]],bb[lc[s]]) ;

ba[s]=ba[lc[s]] , bb[s]=bb[rc[s]] ;

vm[s]=vm[lc[s]] ;

}

}


void tag_it(int s,int val){

if(!s)return ;

vm[s]+=val , tag[s]+=val ;

}


void pushdown(int s){

if(tag[s]){

tag_it(lc[s],tag[s]) , tag_it(rc[s],tag[s]) ;

tag[s]=0 ;

}

}


void build(int s,int ll,int rr)

{

if(ll==rr){

aa[s]=ab[s]=ba[s]=ll ;

va[s]=couples(ll,ll) ;

return ;

}

lc[s]=news() , rc[s]=news() ;

build(lc[s],ll,mid) , build(rc[s],mid+1,rr) ;

update(s) ;

}


int c_pos ;

void change_it(int s,int ll,int rr){

pushdown(s) ;

if(ll==rr)return ;

if(c_pos<=mid)change_it(lc[s],ll,mid) ;

elsechange_it(rc[s],mid+1,rr) ;

update(s) ;

}


int a_l , a_r , a_num ;

void add(int s,int ll,int rr) {

if(ll>a_r || rr<a_l)return ;

pushdown(s) ;

if(ll>=a_l && rr<=a_r){

tag_it(s,a_num) ;

return ;

}

add(lc[s],ll,mid) , add(rc[s],mid+1,rr) ;

update(s) ;

}


void init()

{

root=news() ;

build(root,0,n) ;

}

}ST;


void solve()

{

ST.init() ;

long long ans=0 ;

while(K--){

couples t=ST.va[ST.root]+ST.vb[ST.root] ;

couples tmp=ST.vb[ST.root] ;

int x=t.l , y=t.r ;

ans+=A[x]+B[y] ;

A[x]=INF , ST.c_pos=x ;

ST.change_it(ST.root,0,n) ;

B[y]=INF , ST.c_pos=y ;

ST.change_it(ST.root,0,n) ;

if(t==tmp){

ST.a_l=y , ST.a_r=x-1 , ST.a_num=-1 ;

if(ST.a_l<=ST.a_r){

ST.add(ST.root,0,n) ;

}

}

else{

ST.a_l=x , ST.a_r=y-1 , ST.a_num=1 ;

if(ST.a_l<=ST.a_r){

ST.add(ST.root,0,n) ;

}

}

}

printf("%lld\n",ans) ;

}


int main()

{

scanf("%d%d",&n,&K) ;

for(int i=1;i<=n;++i)scanf("%d",&A[i]) ;

for(int i=1;i<=n;++i)scanf("%d",&B[i]);

A[0]=B[0]=INF ;

solve() ;

return 0 ;

}


评论(1)

热度(1)