2019.01.13 bzoj4538: [Hnoi2016]网络（树链剖分）-白红宇

2019.01.13 bzoj4538: [Hnoi2016]网络（树链剖分）

阅读量：5240 次

发布时间：2019-06-14

本文共 1654 字，大约阅读时间需要 5 分钟。

树链剖分一眼题。

题意简述：

给定一棵树，有三种操作：

加入一条路径

删除一条已加入的路径

询问不过一个点x的路径的最大值。

思路：

直接树链剖分维护答案。

因为询问的事不过点

x

的最大值，因此对于一条路径我们只需要修改它的补集。

考虑到树上一条到根节点的路径映射到序列上只有

l o g

段，因此它的补集也只有

l o g

段，这样就可以修改了。

然后有了一种叫做删除的操作。

不难想到可以用可删堆+永久化标记。

代码很简单。

代码：

#include
    
     #define ri register int#define lc (p<<1)#define rc (p<<1|1)#define mid (l+r>>1)using namespace std;inline int read(){
    	int ans=0;	char ch=getchar();	while(!isdigit(ch))ch=getchar();	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();	return ans;}typedef pair
     
       pii;const int N=2e5+5;int n,m,sig=0,tot=0,fa[N],hson[N],dep[N],top[N],siz[N],num[N],pred[N];pii stk[N];vector
      
       e[N];struct Node{
    int a,b,v;}qry[N];void dfs1(int p){
    	siz[p]=1;	for(ri i=0,v;i
       
        siz[hson[p]])hson[p]=v;	}}void dfs2(int p,int tp){
    	top[p]=tp,pred[num[p]=++tot]=p;	if(!hson[p])return;	dfs2(hson[p],tp);	for(ri i=0,v;i

a,b; inline void push(const int&x){

a.push(x);} inline void del(const int&x){

b.push(x);} inline int size(){

return a.size()-b.size();} inline int top(){

while(b.size()&&a.top()==b.top())a.pop(),b.pop();return a.top();} inline int max(){

return size()?top():-1;}}T[N<<2];inline void update(int p,int l,int r,int ql,int qr,int v,int op){

if(ql>r||qr

mid)update(rc,mid+1,r,ql,qr,v,op); else update(lc,l,mid,ql,mid,v,op),update(rc,mid+1,r,mid+1,qr,v,op);}inline int query(int p,int l,int r,int k,int val){ val=max(val,T[p].max()); if(l==r)return val; return k<=mid?query(lc,l,mid,k,val):query(rc,mid+1,r,k,val);}inline void change(int x,int y,int v,int op){ sig=0; while(top[x]^top[y]){ if(dep[top[x]]

转载于:https://www.cnblogs.com/ldxcaicai/p/10367770.html

你可能感兴趣的文章