BZOJ3159: 决战（FHQ Treap）

传送门：

解题思路：

算是补坑了，这题除了Invert以外就可以树剖线段树解决了。

考虑Invert操作，延续先前树链剖分的做法，考虑先前算法的瓶颈。

最暴力的方法是暴力交换权值，然而这种方法忽略了当前树链剖分序的一个性质，那就是很多部分的树链是连续的，而且仅有$O(\lg n)$个区间。

考虑只有一个区间的做法，就很显然是区间翻转（这个不会搞的话你是怎么做到这道题的），于是，由于区间个数并不多，我们大胆猜想：正确的解法就是考虑翻如何转这些不连续区间

由于链区间具有一定的连续性，且我们需要翻转其权值，考虑更换我们所使用的数据结构，Splay和FHQ Treap都可以，我个人更倾向于使用后者（因为好写）。

现在问题瓶颈就是如何翻转不连续的区间权值。

其实方法很简单，将这$O(\lg n)$个拼接在一起，翻转，再重新安回去，很显然这样做的时间复杂度是$O((\lg n)^2))$的。

考虑具体的操作，由于下标索引在拆树的时候可能改变非常恶心，所以我们预处理出x-y中所有链区间，按dfs序排序，倒着拆，把x到lca上的树链翻转后拼接，再与y到lca上的树链翻转。最后再翻转，正着安回去。

大概就可以愉快地AC了。

代码：

  1 #include<cstdio>

  2 #include<cstring>

  3 #include<cstdlib>

  4 #include<algorithm>

  5 #define lll tr[spc].ls

  6 #define rrr tr[spc].rs

  7 typedef long long lnt;

  8 struct chain{

  9     int ind;

 10     int len;

 11     bool x;

 12 }ch[100010];

 13 struct trnt{

 14     int ls,rs;

 15     int lzt;

 16     int wgt;

 17     int rnd;

 18     lnt lzta;

 19     lnt val;

 20     lnt sum;

 21     lnt maxval,minval;

 22     void rediff(int seed){

 23         ls=rs=lzt=0;

 24         lzta=val=sum=maxval=minval=0;

 25         rnd=seed+rand()%500+1;

 26         wgt=1;

 27         return ;

 28     }

 29 }tr[1000010];

 30 struct pnt{

 31     int hd;

 32     int fa;

 33     int tp;

 34     int dep;

 35     int ind;

 36     int mxs;

 37     int wgt;

 38 }p[100010];

 39 struct ent{

 40     int twd;

 41     int lst;

 42 }e[100010];

 43 int cnt;

 44 int siz;

 45 int dfn;

 46 int top;

 47 int n,m,r;

 48 char cmd[100];

 49 int rootl,rootr,rootm,root;

 50 int pos[100010],size[100010];

 51 int cmp(chain a,chain b){

 52     return a.ind<b.ind;

 53 }

 54 void ade(int f,int t){

 55     cnt++;

 56     e[cnt].twd=t;

 57     e[cnt].lst=p[f].hd;

 58     p[f].hd=cnt;

 59     return ;

 60 }

 61 void push_up(int spc){

 62     tr[spc].wgt=1;

 63     tr[spc].minval=tr[spc].maxval=tr[spc].sum=tr[spc].val;

 64     if(lll){

 65         tr[spc].wgt+=tr[lll].wgt;

 66         tr[spc].sum+=tr[lll].sum;

 67         tr[spc].minval=std::min(tr[spc].minval,tr[lll].minval);

 68         tr[spc].maxval=std::max(tr[spc].maxval,tr[lll].maxval);

 69     }

 70     if(rrr){

 71         tr[spc].wgt+=tr[rrr].wgt;

 72         tr[spc].sum+=tr[rrr].sum;

 73         tr[spc].minval=std::min(tr[spc].minval,tr[rrr].minval);

 74         tr[spc].maxval=std::max(tr[spc].maxval,tr[rrr].maxval);

 75     }

 76     return ;

 77 }

 78 void add(int spc,lnt val){

 79     if(!spc){

 80         return ;

 81     }

 82     tr[spc].val+=val;

 83     tr[spc].lzta+=val;

 84     tr[spc].maxval+=val;

 85     tr[spc].minval+=val;

 86     tr[spc].sum+=val*tr[spc].wgt;

 87     return ;

 88 }

 89 void trr(int spc){

 90     if(!spc){

 91         return ;

 92     }

 93     std::swap(lll,rrr);

 94     tr[spc].lzt^=1;

 95     return ;

 96 }

 97 void push_down(int spc){

 98     if(tr[spc].lzt){

 99         trr(lll);

100         trr(rrr);

101         tr[spc].lzt=0;

102     }

103     if(tr[spc].lzta){

104         add(lll,tr[spc].lzta);

105         add(rrr,tr[spc].lzta);

106         tr[spc].lzta=0;

107     }

108     return ;

109 }

110 void build(int l,int r,int &spc,int seed){

111     if(l>r){

112         return ;

113     }

114     int mid=(l+r)>>1;

115     spc=++siz;

116     tr[spc].rediff(seed);

117     build(l,mid-1,lll,tr[spc].rnd);

118     build(mid+1,r,rrr,tr[spc].rnd);

119     push_up(spc);

120     return ;

121 }

122 void split(int spc,int &ll,int &rr,int k){

123     if(!spc){

124         ll=rr=0;

125         return ;

126     }

127     push_down(spc);

128     if(tr[lll].wgt<k){

129         ll=spc;

130         split(rrr,rrr,rr,k-tr[lll].wgt-1);

131     }else{

132         rr=spc;

133         split(lll,ll,lll,k);

134     }

135     push_up(spc);

136     return ;

137 }

138 int merge(int ll,int rr){

139     if(!ll||!rr){

140         return ll|rr;

141     }else{

142         if(tr[ll].rnd<tr[rr].rnd){

143             push_down(ll);

144             tr[ll].rs=merge(tr[ll].rs,rr);

145             push_up(ll);

146             return ll;

147         }else{

148             push_down(rr);

149             tr[rr].ls=merge(ll,tr[rr].ls);

150             push_up(rr);

151             return rr;

152         }

153     }

154     return 0;

155 }

156 void Basic_dfs(int x,int f){

157     p[x].fa=f;

158     p[x].wgt=1;

159     p[x].dep=p[f].dep+1;

160     int maxs(-1);

161     for(int i=p[x].hd;i;i=e[i].lst){

162         int to=e[i].twd;

163         if(to==f){

164             continue;

165         }

166         Basic_dfs(to,x);

167         p[x].wgt+=p[to].wgt;

168         if(p[to].wgt>maxs){

169             p[x].mxs=to;

170             maxs=p[to].wgt;

171         }

172     }

173     return ;

174 }

175 void Build_dfs(int x,int t){

176     if(!x){

177         return ;

178     }

179     p[x].tp=t;

180     p[x].ind=++dfn;

181     Build_dfs(p[x].mxs,t);

182     for(int i=p[x].hd;i;i=e[i].lst){

183         int to=e[i].twd;

184         if(p[to].ind){

185             continue;

186         }

187         Build_dfs(to,to);

188     }

189     return ;

190 }

191 void Increase(int x,int y,lnt z){

192     while(p[x].tp!=p[y].tp){

193         if(p[p[x].tp].dep<p[p[y].tp].dep){

194             std::swap(x,y);

195         }

196         int S(p[p[x].tp].ind-1),T(p[x].ind);

197         split(root,rootl,rootr,T);

198         split(rootl,rootl,rootm,S);

199         add(rootm,z);

200         root=merge(rootl,merge(rootm,rootr));

201         x=p[p[x].tp].fa;

202

203     }

204     if(p[x].dep>p[y].dep){

205         std::swap(x,y);

206     }

207     int S(p[x].ind-1),T(p[y].ind);

208     split(root,rootl,rootr,T);

209     split(rootl,rootl,rootm,S);

210     add(rootm,z);

211     root=merge(rootl,merge(rootm,rootr));

212     return ;

213 }

214 void Invert(int x,int y){

215     top=0;

216     if(p[x].ind>p[y].ind){

217         std::swap(x,y);

218     }

219     int lca(r);

220     int tmpx(x),tmpy(y);

221     while(p[x].tp!=p[y].tp){

222         if(p[p[x].tp].dep>p[p[y].tp].dep){

223             top++;

224             ch[top].ind=p[p[x].tp].ind;

225             ch[top].len=p[x].ind-p[p[x].tp].ind+1;

226             ch[top].x=true;

227             x=p[p[x].tp].fa;

228         }else{

229             top++;

230             ch[top].ind=p[p[y].tp].ind;

231             ch[top].len=p[y].ind-p[p[y].tp].ind+1;

232             ch[top].x=false;

233             y=p[p[y].tp].fa;

234         }

235     }

236     if(p[x].dep<=p[y].dep){

237         top++;

238         ch[top].ind=p[x].ind;

239         ch[top].len=p[y].ind-p[x].ind+1;

240         ch[top].x=false;

241     }else{

242         top++;

243         ch[top].ind=p[y].ind;

244         ch[top].len=p[x].ind-p[y].ind+1;

245         ch[top].x=true;

246     }

247     std::sort(ch+1,ch+top+1,cmp);

248     int tmptop(top);

249     int root_(0);

250     while(top){

251         int S(ch[top].ind-1),T(ch[top].ind+ch[top].len-1);

252         split(root,rootl,rootr,T);

253         split(rootl,rootl,rootm,S);

254         root=merge(rootl,rootr);

255         if(ch[top].x){

256             trr(rootm);

257         }

258         root_=merge(rootm,root_);

259         top--;

260     }

261     trr(root_);

262     top=1;

263     while(top<=tmptop){

264         int S(ch[top].ind-1);

265         split(root,rootl,rootr,S);

266         split(root_,rootm,root_,ch[top].len);

267         if(ch[top].x){

268             trr(rootm);

269         }

270         root=merge(rootl,merge(rootm,rootr));

271         top++;

272     }

273     return ;

274 }

275 lnt Sum(int x,int y){

276     lnt ans(0);

277     while(p[x].tp!=p[y].tp){

278         if(p[p[x].tp].dep<p[p[y].tp].dep){

279             std::swap(x,y);

280         }

281         int S(p[p[x].tp].ind-1),T(p[x].ind);

282         split(root,rootl,rootr,T);

283         split(rootl,rootl,rootm,S);

284         ans=ans+tr[rootm].sum;

285         root=merge(rootl,merge(rootm,rootr));

286         x=p[p[x].tp].fa;

287     }

288     if(p[x].dep>p[y].dep){

289         std::swap(x,y);

290     }

291     int S(p[x].ind-1),T(p[y].ind);

292     split(root,rootl,rootr,T);

293     split(rootl,rootl,rootm,S);

294     ans=ans+tr[rootm].sum;

295     root=merge(rootl,merge(rootm,rootr));

296     return ans;

297 }

298 lnt Major(int x,int y){

299     lnt ans(-0x3f3f3f3f3f3fll);

300     while(p[x].tp!=p[y].tp){

301         if(p[p[x].tp].dep<p[p[y].tp].dep){

302             std::swap(x,y);

303         }

304         int S(p[p[x].tp].ind-1),T(p[x].ind);

305         split(root,rootl,rootr,T);

306         split(rootl,rootl,rootm,S);

307         ans=std::max(ans,tr[rootm].maxval);

308         root=merge(rootl,merge(rootm,rootr));

309         x=p[p[x].tp].fa;

310     }

311     if(p[x].dep>p[y].dep){

312         std::swap(x,y);

313     }

314     int S(p[x].ind-1),T(p[y].ind);

315     split(root,rootl,rootr,T);

316     split(rootl,rootl,rootm,S);

317     ans=std::max(ans,tr[rootm].maxval);

318     root=merge(rootl,merge(rootm,rootr));

319     return ans;

320 }

321 lnt Minor(int x,int y){

322     lnt ans(0x3f3f3f3f3f3fll);

323     while(p[x].tp!=p[y].tp){

324         if(p[p[x].tp].dep<p[p[y].tp].dep){

325             std::swap(x,y);

326         }

327         int S(p[p[x].tp].ind-1),T(p[x].ind);

328         split(root,rootl,rootr,T);

329         split(rootl,rootl,rootm,S);

330         ans=std::min(ans,tr[rootm].minval);

331         root=merge(rootl,merge(rootm,rootr));

332         x=p[p[x].tp].fa;

333     }

334     if(p[x].dep>p[y].dep){

335         std::swap(x,y);

336     }

337     int S(p[x].ind-1),T(p[y].ind);

338     split(root,rootl,rootr,T);

339     split(rootl,rootl,rootm,S);

340     ans=std::min(ans,tr[rootm].minval);

341     root=merge(rootl,merge(rootm,rootr));

342     return ans;

343 }

344 void pia(int spc){

345     if(!spc){

346         return ;

347     }

348     push_down(spc);

349     pia(lll);

350     printf("%lld ",tr[spc].val);

351     pia(rrr);

352     return ;

353 }

354 int main(){

355     scanf("%d%d%d",&n,&m,&r);

356     for(int i=1;i<=n;++i){

357         int a,b;

358         scanf("%d%d",&a,&b);

359         ade(a,b);

360         ade(b,a);

361     }

362     build(1,n,root,0);

363     Basic_dfs(r,r);

364     Build_dfs(r,r);

365     int pro(0);

366     while(m--){

367         int x,y,z;

368         scanf("%s",cmd+1);

369         if(cmd[1]=='I'){

370             if(cmd[3]=='c'){

371                 scanf("%d%d%d",&x,&y,&z);

372                 Increase(x,y,lnt(z));

373             }

374             if(cmd[3]=='v'){

375                 scanf("%d%d",&x,&y);

376                 Invert(x,y);

377             }

378         }

379         if(cmd[1]=='S'){

380             scanf("%d%d",&x,&y);

381             printf("%lld\n",Sum(x,y));

382         }

383         if(cmd[1]=='M'){

384             if(cmd[2]=='a'){

385                 scanf("%d%d",&x,&y);

386                 printf("%lld\n",Major(x,y));

387             }

388             if(cmd[2]=='i'){

389                 scanf("%d%d",&x,&y);

390                 printf("%lld\n",Minor(x,y));

391             }

392         }

393     }

394     return 0;

395 }

巴特西

BZOJ3159: 决战（FHQ Treap）

解题思路：

最新文章

热门文章