BZOJ3672 Ticket

Hoblovski posted @ 2014年10月04日 02:03 in Solutions with tags BZOJ 点分治 Treap NOI2014 斜率DP , 1535 阅读

题意给定一棵带权有根树T,每个点u有参数a[u],b[u],lim[u],定义f:

f[root]=0

f[u]=min{f[v]+a[u]d(u,v)+b[u]

| v is an ancestor of u and d(u,v)<=lim[u]}

对于所有u,求f[u].

Tag 点分治维护凸包斜率DP Treap

考完之后沉浸在滚出的心情中,听讲题完全没上心,至今只记得谁的暴力树链剖分维护凸包DP本来该被卡飞常数的结果过了,和貌似杜教的"我觉得出题人为了卡暴力凸包上的点坑定很多"然后平方算法过了.

后来决定还是要A掉此题,看了同队进队爷的Blog发现点分治是一种不错的方法,只有2个log.

调这道题的时候调泣了...只是感觉到了那种调代码题的抓狂又安稳的气氛...

以上是废话...

首先我们重写方程,预处理出dr[u]代表d(root,u).

f[u]=min{f[v]+a[u]dr[u]-a[u]dr[v]+b[u] | v satisfies the restrictions}

一眼斜率DP,只是由于斜率不是单调的,加点的X坐标不是单调了,我们大概需要用平衡树来维护凸包.

考场上想自己写出来树上cdq分治,简直傻逼至极.

还要点分治,每次选重心centre,分类讨论centre=root?如果等于做法显然.

否则先递归Tree(root)-Tree(centre),然后再递归Tree(centre).

然后发现能用来更新Tree(centre)的点在链chain([root,centre))上(即含root不含centre).我们BFS一遍之后按dr[u]-lim[u]排序之后做就可以了.

考完一样傻逼,别人4,5K的代码我写了8K多.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

{$INLINE ON}
program bzoj3672;
 
type point=record x,y:int64; end;
     tedge=record n,next:longint; end;
     pnode=^tnode;
     tnode=record
        v,e:point;
        p:longint;
        l,r:pnode;
     end;
 
const maxn=200017;
      maxm=200017;
      maxint=longint($3f3f3f3f);
      eps=1e-9;
      nuv:point=(x:-1;y:-1);
      nev:point=(x:0;y:0);
 
var g,fa,anc,q,size,sons:array[0..maxn] of longint;
    a,b,f,dr,lim:array[0..maxn] of int64;
    mem:array[0..maxm] of tedge;
    flag:array[0..maxn] of boolean;
    n,memsize,casetype,frt,rer:longint;
    treap,null:pnode;
 
operator <(a,b:point) c:boolean; inline; begin exit((a.x<b.x)or((a.x=b.x)and(a.y<b.y))); end;
operator -(a,b:point) c:point; inline; begin c.x:=a.x-b.x; c.y:=a.y-b.y; end;
operator *(a,b:point) c:extended; inline; begin exit(extended(a.x)*b.y-extended(b.x)*a.y); end;
operator =(a,b:point) c:boolean; inline; begin exit((a.x=b.x)and(a.y=b.y)); end;
 
function min(i,j:int64):int64; inline; begin if i<j then exit(i) else exit(j); end;
function max(i,j:int64):int64; inline; begin if i>j then exit(i) else exit(j); end;
 
function sgn(r:extended):longint; inline;                begin
if r<-eps then exit(-1); if r>eps then exit(1); exit(0); end;
 
procedure insnbs(u,v:longint); inline;                                          begin
inc(memsize); mem[memsize].n:=v; mem[memsize].next:=g[u];  g[u]:=memsize;       end;
 
procedure treap_init;                                                                           begin
new(null); with null^ do begin v.x:=-1; v.y:=-1; p:=maxint; l:=null; r:=null; end; treap:=null; end;
 
procedure lrot(var i:pnode); inline; var j:pnode;
begin j:=i^.r; i^.r:=j^.l; j^.l:=i; i:=j; end;
 
procedure rrot(var i:pnode); inline; var j:pnode;
begin j:=i^.l; i^.l:=j^.r; j^.r:=i; i:=j; end;
 
procedure insert(var i:pnode;j:point);
begin
if i=null then begin
        new(i); with i^ do begin
                v:=j; p:=random(maxint); e:=nev; l:=null; r:=null;
        end;
end else if j<i^.v then begin
        insert(i^.l,j); if i^.l^.p<i^.p then rrot(i);
end else begin
        insert(i^.r,j); if i^.r^.p<i^.p then lrot(i);
end;
end;
 
procedure delete(var i:pnode;j:point);
begin
if j=i^.v then
        if i^.l=null then i:=i^.r
        else if i^.r=null then i:=i^.l
        else if i^.l^.p<i^.r^.p then begin
                rrot(i); delete(i^.r,j);
        end else begin
                lrot(i); delete(i^.l,j);
        end
else if j<i^.v then delete(i^.l,j) else delete(i^.r,j);
end;
 
function prev(i:pnode;j:point):pnode; inline;
begin
prev:=null; while i<>null do
        if not(i^.v<j) then i:=i^.l
        else begin prev:=i; i:=i^.r; end;
end;
 
function next(i:pnode;j:point):pnode; inline;
begin
next:=null; while i<>null do
        if (i^.v<j)or(i^.v=j) then i:=i^.r
        else begin next:=i; i:=i^.l; end;
end;
 
procedure update(i:point);
var t1,t2:pnode;
begin
t1:=treap; t2:=next(treap,i); while t1^.v<>i do
        if i<t1^.v then t1:=t1^.l else t1:=t1^.r;
if (t2=null)or(t1=null) then t1^.e:=nev else t1^.e:=t2^.v-t1^.v;
end;
 
procedure addpoint(a:point);
var rp,lp,np:point;
begin
lp:=prev(treap,a)^.v; if lp=nuv then begin
        rp:=next(treap,a)^.v; while true do begin
                np:=next(treap,rp)^.v; if np=nuv then break;
                if sgn((rp-a)*(np-a))>=0 then begin
                        delete(treap,rp); rp:=np;
                end else break;
        end; insert(treap,a); update(a); exit;
end;
rp:=next(treap,a)^.v; if rp=nuv then begin
        lp:=prev(treap,a)^.v; while true do begin
                np:=prev(treap,lp)^.v; if np=nuv then break;
                if sgn((lp-a)*(np-a))<=0 then begin
                        delete(treap,lp); lp:=np;
                end else break;
        end; insert(treap,a); if lp<>nuv then update(lp); exit;
end;
if sgn((a-lp)*(rp-lp))>=0 then exit;
while true do begin
        np:=prev(treap,lp)^.v; if np=nuv then break;
        if sgn((a-lp)*(np-lp))>=0 then begin
                delete(treap,lp); lp:=np;
        end else break;
end;
while true do begin
        np:=next(treap,rp)^.v; if np=nuv then break;
        if sgn((a-rp)*(np-rp))<=0 then begin
                delete(treap,rp); rp:=np;
        end else break;
end; insert(treap,a);
update(a); update(prev(treap,a)^.v);
end;
 
function tanpoint(a:point):point;
var t1:pnode;
begin
tanpoint.x:=0; tanpoint.y:=0;
if treap=null then begin tanpoint.x:=maxint; exit; end;
t1:=treap; while t1<>null do begin
        if sgn(t1^.e*a)<0 then t1:=t1^.r
        else begin tanpoint:=t1^.v; t1:=t1^.l; end;
end;
end;
 
function centre(root:longint):longint;
var i,j,head,tail,t1,ans:longint;
begin
frt:=0; rer:=1; q[1]:=root; while frt<rer do begin
        inc(frt); head:=q[frt]; t1:=g[head];
        while t1<>0 do begin tail:=mem[t1].n;
                if not flag[tail] then begin
                        inc(rer); q[rer]:=tail;
                end; t1:=mem[t1].next;
        end; size[head]:=0; sons[head]:=0;
end; ans:=maxint; for i:=rer downto 1 do begin
        j:=q[i]; inc(size[j]); sons[fa[j]]:=max(sons[fa[j]],size[j]);
        t1:=max(sons[j],rer-size[j]); if t1<ans then begin
                ans:=t1; centre:=j;
        end; inc(size[fa[j]],size[j]);
end;
end;
 
procedure qsort(l,r:longint);
var i,j,k,o:longint;
begin
i:=l; j:=r; k:=q[l+random(r-l+1)];
repeat
        while lim[q[i]]>lim[k] do inc(i);
        while lim[q[j]]<lim[k] do dec(j);
        if i<=j then begin
                o:=q[i]; q[i]:=q[j]; q[j]:=o;
                inc(i); dec(j);
        end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;
 
procedure update(u,root:longint);
var i,j,ac,head,tail,t1:longint;
    tp:point;
begin
frt:=0; rer:=1; q[1]:=u; while frt<rer do begin
        inc(frt); head:=q[frt]; t1:=g[head];
        while t1<>0 do begin tail:=mem[t1].n;
                if not flag[tail] then begin
                        inc(rer); q[rer]:=tail;
                end; t1:=mem[t1].next;
        end;
end; qsort(1,rer); treap:=null;
ac:=0; head:=u; while head<>root do begin
        head:=fa[head]; inc(ac); anc[ac]:=head;
end; if ac>0 then begin
        j:=1; for i:=1 to rer do begin u:=q[i];
                while (j<=ac)and(dr[anc[j]]>=lim[u]) do begin
                        tp.x:=f[anc[j]]; tp.y:=dr[anc[j]]; addpoint(tp); inc(j);
                end; if j>1 then begin
                        tp.x:=a[u]; tp.y:=1; tp:=tanpoint(tp);
                        f[u]:=min(f[u],dr[u]*a[u]+b[u]+tp.x-a[u]*tp.y);
                end;
        end;
end else begin
        for i:=1 to rer do begin u:=q[i];
                if dr[root]>=lim[u] then
                        f[u]:=min(f[u],dr[u]*a[u]+b[u]+f[root]-a[u]*dr[root]);
        end;
end;
end;
 
procedure init;
var i,head,t1:longint;
begin
fillchar(g,sizeof(g),0); memsize:=1;
readln(n,casetype); for i:=2 to n do begin
        readln(fa[i],dr[i],a[i],b[i],lim[i]); insnbs(fa[i],i);
end; frt:=0; rer:=1; q[1]:=1; while frt<rer do begin
        inc(frt); head:=q[frt]; inc(dr[head],dr[fa[head]]);
        t1:=g[head]; while t1<>0 do begin
                inc(rer); q[rer]:=mem[t1].n; t1:=mem[t1].next;
        end; lim[head]:=dr[head]-lim[head];
end; fillchar(flag,sizeof(flag),0); fillchar(f,sizeof(f),$3f); f[1]:=0;
end;
 
procedure work(root:longint);
var u,t1:longint;
begin
u:=centre(root); flag[u]:=true;
if u<>root then begin
        work(root); update(u,root); work(u);
end else begin
        update(u,root); t1:=g[u]; while t1<>0 do begin
                if not flag[mem[t1].n] then work(mem[t1].n);
                t1:=mem[t1].next;
        end;
end;
end;
 
procedure answer; var i:longint;
begin for i:=2 to n do writeln(f[i]); end;
 
begin
treap_init;
init;
work(1);
answer;
end.

Adieu.

[回复]

John 说:
2021年12月16日 15:24

When faced with making difficult decisions in life, many individuals lose the power to think and act rationally and then they require the support and guidance of others, in order to make the right choice. A divorce is one such emotionally devastating experience, which some couples may have to face when differences between them become irreconcilable. So, in a divorce case, neither of the individuals is in a frame of mind to handle the situation alone. personal injury attorney nashville

[回复]

https://cmbihar.in/1 说:
2022年5月21日 14:42

1st PUC Exam Pattern 2023 1st PUC Marking Scheme 2023 A Careful Comprehension of the Board Exam Pattern 2023 is the Initial move Towards Planning for any Examinations and the Equivalent is Valid for Karnataka 1st PUC Exam Pattern 2023 Board second PUC. In Karnataka,

[回复]

Bushra 说:
2022年12月29日 01:16

Thanks for the post and great tips..even I also think that hard work is the most important aspect of getting success.. cash for scrap cars

[回复]

Bushra 说:
2022年12月30日 01:04

Thanks for taking the time to discuss this, I feel strongly about it and love learning more on this topic. Pishachini

[回复]

samplepaper.in 说:
2023年5月20日 23:11

writers have joined forces under the name samplepaper to create specialised news coverage of the most recent national events. Our team includes both amateur and professional authors.is an initiative of skilled journalists who have come together for specialised samplepaper.in news coverage of recent events across the country.is a newspaper that is passionate about producing education news in the public interest and has a wide range of journalism interests. Our team is made up of professional writers and citizen journalists with diverse media interests