树链剖分 | OceanEye's Blog

@OceanEye7年前

06/15

21:12

BZOJ2243

树链剖分
细节打错了然后wa了好久

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')
#define For(i,l,r) for(int i=l;i<=r;i++)

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;
#define N 100010

int to[N<<2],nxt[N<<2],fst[N],e_tot;
void add_e(const int &_,const int &__)
{
	to[e_tot]=__; nxt[e_tot]=fst[_]++; fst[_]=e_tot++;
	to[e_tot]=_; nxt[e_tot]=fst[__]++; fst[__]=e_tot++;
}
struct node
{
	int l,r,c[2];
	int cnt,col[2];
	int tag;
	node() { tag=-1; }
}pool[N<<2];
int pcnt=1;
#define L pool[x].l
#define R pool[x].r
#define Lc pool[x].c[0]
#define Rc pool[x].c[1]
#define Lcol pool[x].col[0]
#define Rcol pool[x].col[1]
#define CNT pool[x].cnt
#define TAG pool[x].tag
void PushUP(int x)
{
	CNT=pool[Lc].cnt+pool[Rc].cnt-(int)(pool[Lc].col[1]==pool[Rc].col[0]);
	Lcol=pool[Lc].col[0];
	Rcol=pool[Rc].col[1];
	if(CNT==1) TAG=Lcol;
}
void PushDown(int x)
{
	pool[Lc].col[0]=pool[Lc].col[1]=pool[Rc].col[0]=pool[Rc].col[1]=pool[Lc].tag=pool[Rc].tag=TAG;
	pool[Lc].cnt=pool[Rc].cnt=1;
	TAG=-1;
}

void build(int x,int l,int r,int a[])
{
	L=l; R=r;
	if(l==r)
	{
		Lcol=Rcol=a[l];
		CNT=1;
		return;
	}
	int mid=(l+r)>>1;
	build(Lc=++pcnt,l,mid,a);
	build(Rc=++pcnt,mid+1,r,a);
	PushUP(x);
}

int query(int x,int l,int r)
{
	if(~TAG) return 1;
	if(l<=L&&R<=r) return CNT;
	int mid=(L+R)>>1;
	if(mid>=r) return query(Lc,l,r);
	if(mid<l) return query(Rc,l,r);
	return query(Lc,l,r)+query(Rc,l,r)-(int)(pool[Lc].col[1]==pool[Rc].col[0]);
}

int fill(int x,int l,int r,int col)
{
	if(l<=L&&R<=r)
	{
		Lcol=Rcol=TAG=col; CNT=1;
		return 0;
	}
	int mid=(L+R)>>1;
	if(~TAG) PushDown(x);
	if(mid>=l) fill(Lc,l,r,col);
	if(mid<r) fill(Rc,l,r,col);
	PushUP(x);
}

int find(int x,int pos)
{
	if(L==R) return Lcol; 
	if(~TAG) return TAG;
	return find(pos<=((L+R)>>1)?Lc:Rc,pos);
}
int col[N],a[N],id[N],up[N],fa[N],dep[N],mxson[N],siz[N],tot;
int n,m;
void dfs1(int x,int f)
{
	siz[x]=1;
	for(int i=fst[x];~i;i=nxt[i])
	{
		if(to[i]==f) continue;
		dfs1(to[i],x);
		if(siz[to[i]]>siz[mxson[x]]) mxson[x]=to[i];
		siz[x]+=siz[to[i]];
	}
}

void dfs2(int x,int f)
{
	id[x]=++tot;
	if(!mxson[x]) return;
	fa[mxson[x]]=fa[x]; up[mxson[x]]=up[x]; dep[mxson[x]]=dep[x];
	dfs2(mxson[x],x);
	for(int i=fst[x];~i;i=nxt[i])
	{
		if(to[i]==mxson[x]||to[i]==f) continue;
		fa[to[i]]=x; up[to[i]]=to[i]; dep[to[i]]=dep[x]+1;
		dfs2(to[i],x);
	}
}

void init()
{
	memset(fst,-1,sizeof(fst));
	int _,__;
	read(n); read(m);
	For(i,1,n) read(col[i]);
	For(i,1,n-1)
	{
		read(_); read(__);
		add_e(_,__);
	}
	dfs1(1,0);
	up[1]=1;
	dfs2(1,0);
	for(int i=1;i<=n;i++) a[id[i]]=col[i];
	build(pcnt,1,n,a);
}

int LCA(int x,int y)
{
	if(dep[x]>dep[y]) swap(x,y);
	while(dep[x]<dep[y]) y=fa[y];
	while(up[x]!=up[y]) x=fa[x],y=fa[y];
	return id[x]>id[y]?y:x;
}

int find_col(int pos)
{ return find(1,pos); }

int solve()
{
	static int rt,ret,a,b,last_a,last_b;
	read(a); read(b); rt=LCA(a,b);
	ret=last_a=last_b=0;
	while(id[a]>=id[rt])
	{
		ret+=query(1,max(id[up[a]],id[rt]),id[a]);
		if(last_a) ret-=(int)(find_col(id[last_a])==find_col(id[a]));
		last_a=up[a]; a=fa[a];
	}
	while(id[b]>=id[rt])
	{
		ret+=query(1,max(id[up[b]],id[rt]),id[b]);
		if(last_b) ret-=(int)(find_col(id[last_b])==find_col(id[b]));
		last_b=up[b]; b=fa[b];
	}
	return ret-1;
}

void fill()
{
	static int rt,a,b,col;
	read(a); read(b); read(col); rt=LCA(a,b);
	while(id[a]>=id[rt])
	{
		fill(1,max(id[up[a]],id[rt]),id[a],col);
		a=fa[a];
	}
	while(id[b]>=id[rt])
	{
		fill(1,max(id[up[b]],id[rt]),id[b],col);
		b=fa[b];
	}
}

int main()
{
	freopen("BZOJ2243.in","r",stdin);
	char s[10];
	init();
	while(m--)
	{
		scanf("%s",s);
		if(s[0]=='Q') printf("%d\n",solve());
		else fill();
	}
	return 0;
}

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

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <cmath>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

#define For(i,l,r) for(int i=l;i<=r;i++)

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 100010

int to[N<<2],nxt[N<<2],fst[N],e_tot;

void add_e(const int &_,const int &__)

{

to[e_tot]=__; nxt[e_tot]=fst[_]++; fst[_]=e_tot++;

to[e_tot]=_; nxt[e_tot]=fst[__]++; fst[__]=e_tot++;

}

struct node

{

int l,r,c[2];

int cnt,col[2];

int tag;

node() { tag=-1; }

}pool[N<<2];

int pcnt=1;

#define L pool[x].l

#define R pool[x].r

#define Lc pool[x].c[0]

#define Rc pool[x].c[1]

#define Lcol pool[x].col[0]

#define Rcol pool[x].col[1]

#define CNT pool[x].cnt

#define TAG pool[x].tag

void PushUP(int x)

{

CNT=pool[Lc].cnt+pool[Rc].cnt-(int)(pool[Lc].col[1]==pool[Rc].col[0]);

Lcol=pool[Lc].col[0];

Rcol=pool[Rc].col[1];

if(CNT==1) TAG=Lcol;

}

void PushDown(int x)

{

pool[Lc].col[0]=pool[Lc].col[1]=pool[Rc].col[0]=pool[Rc].col[1]=pool[Lc].tag=pool[Rc].tag=TAG;

pool[Lc].cnt=pool[Rc].cnt=1;

TAG=-1;

}

void build(int x,int l,int r,int a[])

{

L=l; R=r;

if(l==r)

{

Lcol=Rcol=a[l];

CNT=1;

return;

}

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

build(Lc=++pcnt,l,mid,a);

build(Rc=++pcnt,mid+1,r,a);

PushUP(x);

}

int query(int x,int l,int r)

{

if(~TAG) return 1;

if(l<=L&&R<=r) return CNT;

int mid=(L+R)>>1;

if(mid>=r) return query(Lc,l,r);

if(mid<l) return query(Rc,l,r);

return query(Lc,l,r)+query(Rc,l,r)-(int)(pool[Lc].col[1]==pool[Rc].col[0]);

}

int fill(int x,int l,int r,int col)

{

if(l<=L&&R<=r)

{

Lcol=Rcol=TAG=col; CNT=1;

return 0;

}

int mid=(L+R)>>1;

if(~TAG) PushDown(x);

if(mid>=l) fill(Lc,l,r,col);

if(mid<r) fill(Rc,l,r,col);

PushUP(x);

}

int find(int x,int pos)

{

if(L==R) return Lcol;

if(~TAG) return TAG;

return find(pos<=((L+R)>>1)?Lc:Rc,pos);

}

int col[N],a[N],id[N],up[N],fa[N],dep[N],mxson[N],siz[N],tot;

int n,m;

void dfs1(int x,int f)

{

siz[x]=1;

for(int i=fst[x];~i;i=nxt[i])

{

if(to[i]==f) continue;

dfs1(to[i],x);

if(siz[to[i]]>siz[mxson[x]]) mxson[x]=to[i];

siz[x]+=siz[to[i]];

}

void dfs2(int x,int f)

{

id[x]=++tot;

if(!mxson[x]) return;

fa[mxson[x]]=fa[x]; up[mxson[x]]=up[x]; dep[mxson[x]]=dep[x];

dfs2(mxson[x],x);

for(int i=fst[x];~i;i=nxt[i])

{

if(to[i]==mxson[x]||to[i]==f) continue;

fa[to[i]]=x; up[to[i]]=to[i]; dep[to[i]]=dep[x]+1;

dfs2(to[i],x);

}

void init()

{

memset(fst,-1,sizeof(fst));

int _,__;

read(n); read(m);

For(i,1,n) read(col[i]);

For(i,1,n-1)

{

read(_); read(__);

add_e(_,__);

}

dfs1(1,0);

up[1]=1;

dfs2(1,0);

for(int i=1;i<=n;i++) a[id[i]]=col[i];

build(pcnt,1,n,a);

}

int LCA(int x,int y)

{

if(dep[x]>dep[y]) swap(x,y);

while(dep[x]<dep[y]) y=fa[y];

while(up[x]!=up[y]) x=fa[x],y=fa[y];

return id[x]>id[y]?y:x;

}

int find_col(int pos)

{ return find(1,pos); }

int solve()

{

static int rt,ret,a,b,last_a,last_b;

read(a); read(b); rt=LCA(a,b);

ret=last_a=last_b=0;

while(id[a]>=id[rt])

{

ret+=query(1,max(id[up[a]],id[rt]),id[a]);

if(last_a) ret-=(int)(find_col(id[last_a])==find_col(id[a]));

last_a=up[a]; a=fa[a];

}

while(id[b]>=id[rt])

{

ret+=query(1,max(id[up[b]],id[rt]),id[b]);

if(last_b) ret-=(int)(find_col(id[last_b])==find_col(id[b]));

last_b=up[b]; b=fa[b];

}

return ret-1;

}

void fill()

{

static int rt,a,b,col;

read(a); read(b); read(col); rt=LCA(a,b);

while(id[a]>=id[rt])

{

fill(1,max(id[up[a]],id[rt]),id[a],col);

a=fa[a];

}

while(id[b]>=id[rt])

{

fill(1,max(id[up[b]],id[rt]),id[b],col);

b=fa[b];

}

int main()

{

freopen("BZOJ2243.in","r",stdin);

char s[10];

init();

while(m--)

{

scanf("%s",s);

if(s[0]=='Q') printf("%d\n",solve());

else fill();

}

return 0;

}

数据

7 8
1 1 1 1 1 1 1
1 2
2 3
3 4
2 5
1 6
5 7
Q 3 5
Q 3 7
C 1 4 2
Q 3 5
Q 3 7
C 3 6 2
Q 3 5
Q 3 7

6 5

2 2 1 2 1 1

1 2

1 3

2 4

2 5

2 6

Q 3 5

C 2 1 1

Q 3 5

C 5 1 2

Q 3 5

7 8

1 1 1 1 1 1 1

1 2

2 3

3 4

2 5

1 6

5 7

Q 3 5

Q 3 7

C 1 4 2

Q 3 5

Q 3 7

C 3 6 2

Q 3 5

Q 3 7

6 5

2 2 1 2 1 1

1 2

1 3

2 4

2 5

2 6

Q 3 5

C 2 1 1

Q 3 5

C 5 1 2

Q 3 5

BZOJ2243

@OceanEye7年前

06/4

13:26

BZOJ4034

OceanEye 撰写基础题树树链剖分模版题线段树无回复

简单的树链剖分，分轻重链之后依然满足DFS序的性质所以可以用线段树的区间加来表示子树加法

挂代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdlib>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')
#define For(i,l,r) for(int i=l;i<=r;i++)

char cc; int C;
template <class T>
void read( T &x )
{
	x=0; cc=getchar(); C=1;
	while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }
	while(p(cc)) { x=x*10+cc-48; cc=getchar(); }
	x*=C;
}

using namespace std;
#define N 100010
int val[N],Arr[N],n,m;
struct node
{
	int c[2],l,r;
	ll val,tag;
	int operator [] (const int &x) { return c[x]; }
}pool[N<<2];
#define L pool[x].l
#define R pool[x].r
#define VAL pool[x].val
#define TAG pool[x].tag
#define Lc pool[x].c[0]
#define Rc pool[x].c[1]
#define SIZ (R-L+1)
int pcnt=1;

inline void PushUP(int x) { VAL=pool[Lc].val+pool[Rc].val+TAG*SIZ; }

void build(int x,int l,int r)
{
	L=l; R=r;
	if(l==r)
	{
		TAG=Arr[l];
		PushUP(x);
		return;
	}
	int mid=(l+r)>>1;
	build(Lc=++pcnt,l,mid); build(Rc=++pcnt,mid+1,r);
	PushUP(x);
}

void add(int x,int l,int r,int val)
{
	if(l<=L&&R<=r)
	{
		TAG+=val; PushUP(x);
		return;
	}
	int mid=(L+R)>>1;
	if(mid>=l) add(Lc,l,r,val);
	if(mid <r) add(Rc,l,r,val);
	PushUP(x);
}

void add(int x,int pos,int val)
{
	if(L==R)
	{
		TAG+=val;
		PushUP(x);
		return;
	}
	if(pos>((L+R)>>1)) add(Rc,pos,val);
	else add(Lc,pos,val);
	PushUP(x);
}

ll query(int x,int l,int r)
{
	if(l<=L&&R<=r) return VAL;
	int mid=(L+R)>>1; ll ret=0;
	if(l<=mid) ret+=query(Lc,l,r);
	if(r >mid) ret+=query(Rc,l,r);
	ret+=1LL*TAG*(min(R,r)-max(L,l)+1);
	return ret;
}

int mxson[N],siz[N],up[N],fa[N],id[N],l[N],r[N],tmp;
vector <int> G[N];
#define TO G[x][i]
void dfs(int x,int f)
{
	int node;
	siz[x]=1;
	for(int i=0;i<G[x].size();i++)
	{
		node=TO;
		if(node==f) continue;
		dfs(node,x);
		siz[x]+=siz[node];
		if(siz[node]>siz[mxson[x]]) mxson[x]=node;
	}
}
void ddfs(int x,int f)
{
	l[x]=id[x]=++tmp;
	int node=mxson[x];
	if(!node)
	{
		r[x]=tmp;
		return;
	}
	fa[node]=fa[x]; up[node]=up[x];
	ddfs(mxson[x],x);
	for(int i=0;i<G[x].size();i++)
	{
		node=TO;
		if(node==f||node==mxson[x]) continue;
		fa[node]=node; up[node]=x;
		ddfs(node,x);
	}
	r[x]=tmp;
}

void init()
{
	int _,__;
	read(n); read(m);
	For(i,1,n) read(val[i]);
	For(i,1,n-1)
	{
		read(_); read(__);
		G[_].push_back(__); G[__].push_back(_);
	}
	dfs(1,0);
	fa[1]=1; up[1]=0;
	ddfs(1,0);
	For(i,1,n) Arr[id[i]]=val[i];
	build(1,1,n);
}

int main()
{
	freopen("BZOJ4034.in","r",stdin);
	int a,x,val;
	ll ans;
	init();
	while(m--)
	{
		read(a); read(x);
		if(a==1)
		{
			read(val);
			add(1,id[x],val);
		}
		if(a==2)
		{
			read(val);
			add(1,l[x],r[x],val);
		}
		if(a==3)
		{
			ans=0;
			while(x)
			{
				ans+=query(1,id[fa[x]],id[x]);
				x=up[x];
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}

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

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <vector>

#include <cstdlib>

#define ll long long

#define INF 1000000000

#define p(x) ('0'<=x&&x<='9')

#define For(i,l,r) for(int i=l;i<=r;i++)

char cc; int C;

template <class T>

void read( T &x )

{

x=0; cc=getchar(); C=1;

while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); }

while(p(cc)) { x=x*10+cc-48; cc=getchar(); }

x*=C;

}

using namespace std;

#define N 100010

int val[N],Arr[N],n,m;

struct node

{

int c[2],l,r;

ll val,tag;

int operator [] (const int &x) { return c[x]; }

}pool[N<<2];

#define L pool[x].l

#define R pool[x].r

#define VAL pool[x].val

#define TAG pool[x].tag

#define Lc pool[x].c[0]

#define Rc pool[x].c[1]

#define SIZ (R-L+1)

int pcnt=1;

inline void PushUP(int x) { VAL=pool[Lc].val+pool[Rc].val+TAG*SIZ; }

void build(int x,int l,int r)

{

L=l; R=r;

if(l==r)

{

TAG=Arr[l];

PushUP(x);

return;

}

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

build(Lc=++pcnt,l,mid); build(Rc=++pcnt,mid+1,r);

PushUP(x);

}

void add(int x,int l,int r,int val)

{

if(l<=L&&R<=r)

{

TAG+=val; PushUP(x);

return;

}

int mid=(L+R)>>1;

if(mid>=l) add(Lc,l,r,val);

if(mid <r) add(Rc,l,r,val);

PushUP(x);

}

void add(int x,int pos,int val)

{

if(L==R)

{

TAG+=val;

PushUP(x);

return;

}

if(pos>((L+R)>>1)) add(Rc,pos,val);

else add(Lc,pos,val);

PushUP(x);

}

ll query(int x,int l,int r)

{

if(l<=L&&R<=r) return VAL;

int mid=(L+R)>>1; ll ret=0;

if(l<=mid) ret+=query(Lc,l,r);

if(r >mid) ret+=query(Rc,l,r);

ret+=1LL*TAG*(min(R,r)-max(L,l)+1);

return ret;

}

int mxson[N],siz[N],up[N],fa[N],id[N],l[N],r[N],tmp;

vector <int> G[N];

#define TO G[x][i]

void dfs(int x,int f)

{

int node;

siz[x]=1;

for(int i=0;i<G[x].size();i++)

{

node=TO;

if(node==f) continue;

dfs(node,x);

siz[x]+=siz[node];

if(siz[node]>siz[mxson[x]]) mxson[x]=node;

}

void ddfs(int x,int f)

{

l[x]=id[x]=++tmp;

int node=mxson[x];

if(!node)

{

r[x]=tmp;

return;

}

fa[node]=fa[x]; up[node]=up[x];

ddfs(mxson[x],x);

for(int i=0;i<G[x].size();i++)

{

node=TO;

if(node==f||node==mxson[x]) continue;

fa[node]=node; up[node]=x;

ddfs(node,x);

}

r[x]=tmp;

}

void init()

{

int _,__;

read(n); read(m);

For(i,1,n) read(val[i]);

For(i,1,n-1)

{

read(_); read(__);

G[_].push_back(__); G[__].push_back(_);

}

dfs(1,0);

fa[1]=1; up[1]=0;

ddfs(1,0);

For(i,1,n) Arr[id[i]]=val[i];

build(1,1,n);

}

int main()

{

freopen("BZOJ4034.in","r",stdin);

int a,x,val;

ll ans;

init();

while(m--)

{

read(a); read(x);

if(a==1)

{

read(val);

add(1,id[x],val);

}

if(a==2)

{

read(val);

add(1,l[x],r[x],val);

}

if(a==3)

{

ans=0;

while(x)

{

ans+=query(1,id[fa[x]],id[x]);

x=up[x];

}

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

}

return 0;

}

OceanEye's Blog

很多人即使只见过一面，已经算见过了最后一面。

@OceanEye7年前

BZOJ2243

BZOJ2243

@OceanEye7年前

BZOJ4034

BZOJ4034

友情链接

近期文章

标签