【2016/3/6考题 \ 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)