树 | OceanEye's Blog

@OceanEye7年前

07/11

15:00

NOIP2013货物运输

为什么我在写这题的题解……
因为这题我本来想用树剖搞过去的……结果炸了
:-D然后就写了现在的倍增

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define ll long long
#define INF 10000000

#define For(i,a,b) for(int i=a;i<=b;i++)
#define p(c) (c>='0'&&c<='9')
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 10010
#define M 50010
struct rec
{
	int u,v,val;
	bool operator < (const rec &x) const { return val>x.val; }
}REC[M];
struct UNF
{
	int fa[N],siz[N];
	void init(int n)
	{ For(i,1,n) fa[i]=i,siz[i]=1; }
	int getfa(int x)
	{ return fa[x]==x?x:fa[x]=getfa(fa[x]); }
	bool combine(int u,int v)
	{
		u=getfa(u); v=getfa(v);
		if(u==v) return false;
		siz[u]<siz[v]?swap(u,v):swap(u,u);
		fa[v]=u; siz[u]+=siz[v];
		return true;
	}
	bool test(int u,int v) { return getfa(u)==getfa(v); }
}UNF_set;

struct Tedge
{
	int to,val;
}edge[N<<1];
int fst[N],nxt[N<<1],e_tot;
#define TO edge[i].to
#define VAL edge[i].val
#define NXT nxt[i]
void add_e(int a,int b,int val)
{
	static int &i=e_tot;
	TO=b; VAL=val; NXT=fst[a]; fst[a]=i++;
	TO=a; VAL=val; NXT=fst[b]; fst[b]=i++;
}

int val[N],fa[N][15],mn[N][15],dep[N],n,m;

void dfs(int x,int f)
{
	fa[x][0]=f; mn[x][0]=val[x];
	for(int i=1;i<15;i++)
	{
		fa[x][i]=fa[fa[x][i-1]][i-1];
		mn[x][i]=min(mn[x][i-1],mn[fa[x][i-1]][i-1]);
	}
	for(int i=fst[x];~i;i=NXT)
	{
		if(TO==f) continue;
		val[TO]=VAL; dep[TO]=dep[x]+1;
		dfs(TO,x);
	}
}

int getLCA(int u,int v)
{
	if(dep[u]>dep[v]) swap(u,v);
	int dis=dep[v]-dep[u];
	for(int i=14;i>=0;i--) if((1<<i)&dis) v=fa[v][i];
	if(u==v) return u;
	for(int i=14;i>=0;i--) if(fa[u][i]==fa[v][i]) continue;
	else u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}

void init()
{
	memset(fst,-1,sizeof(fst));
	read(n); read(m);
	For(i,1,m) { read(REC[i].u); read(REC[i].v); read(REC[i].val); }
	sort(REC+1,REC+1+m);
	UNF_set.init(n);
	For(i,1,m)if(UNF_set.combine(REC[i].u,REC[i].v))
		add_e(REC[i].u,REC[i].v,REC[i].val);
}

int main()
{
	init();
	int ans,u,v,p;
	for(int i=1;i<=n;i++) if(!val[i])
	{
		val[i]=INF;
		dfs(i,0);
	}
	for(read(m);m;m--)
	{
		read(u); read(v);
		if(!UNF_set.test(u,v))
		{
			puts("-1");
			continue;
		}
		p=getLCA(u,v); ans=INF;
		for(int i=14;i>=0;i--)
		{
			if((dep[u]-dep[p])&(1<<i)) ans=min(ans,mn[u][i]),u=fa[u][i];
			if((dep[v]-dep[p])&(1<<i)) ans=min(ans,mn[v][i]),v=fa[v][i];
		}
		printf("%d\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

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#define ll long long

#define INF 10000000

#define For(i,a,b) for(int i=a;i<=b;i++)

#define p(c) (c>='0'&&c<='9')

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 10010

#define M 50010

struct rec

{

int u,v,val;

bool operator < (const rec &x) const { return val>x.val; }

}REC[M];

struct UNF

{

int fa[N],siz[N];

void init(int n)

{ For(i,1,n) fa[i]=i,siz[i]=1; }

int getfa(int x)

{ return fa[x]==x?x:fa[x]=getfa(fa[x]); }

bool combine(int u,int v)

{

u=getfa(u); v=getfa(v);

if(u==v) return false;

siz[u]<siz[v]?swap(u,v):swap(u,u);

fa[v]=u; siz[u]+=siz[v];

return true;

}

bool test(int u,int v) { return getfa(u)==getfa(v); }

}UNF_set;

struct Tedge

{

int to,val;

}edge[N<<1];

int fst[N],nxt[N<<1],e_tot;

#define TO edge[i].to

#define VAL edge[i].val

#define NXT nxt[i]

void add_e(int a,int b,int val)

{

static int &i=e_tot;

TO=b; VAL=val; NXT=fst[a]; fst[a]=i++;

TO=a; VAL=val; NXT=fst[b]; fst[b]=i++;

}

int val[N],fa[N][15],mn[N][15],dep[N],n,m;

void dfs(int x,int f)

{

fa[x][0]=f; mn[x][0]=val[x];

for(int i=1;i<15;i++)

{

fa[x][i]=fa[fa[x][i-1]][i-1];

mn[x][i]=min(mn[x][i-1],mn[fa[x][i-1]][i-1]);

}

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

{

if(TO==f) continue;

val[TO]=VAL; dep[TO]=dep[x]+1;

dfs(TO,x);

}

int getLCA(int u,int v)

{

if(dep[u]>dep[v]) swap(u,v);

int dis=dep[v]-dep[u];

for(int i=14;i>=0;i--) if((1<<i)&dis) v=fa[v][i];

if(u==v) return u;

for(int i=14;i>=0;i--) if(fa[u][i]==fa[v][i]) continue;

else u=fa[u][i],v=fa[v][i];

return fa[u][0];

}

void init()

{

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

read(n); read(m);

For(i,1,m) { read(REC[i].u); read(REC[i].v); read(REC[i].val); }

sort(REC+1,REC+1+m);

UNF_set.init(n);

For(i,1,m)if(UNF_set.combine(REC[i].u,REC[i].v))

add_e(REC[i].u,REC[i].v,REC[i].val);

}

int main()

{

init();

int ans,u,v,p;

for(int i=1;i<=n;i++) if(!val[i])

{

val[i]=INF;

dfs(i,0);

}

for(read(m);m;m--)

{

read(u); read(v);

if(!UNF_set.test(u,v))

{

puts("-1");

continue;

}

p=getLCA(u,v); ans=INF;

for(int i=14;i>=0;i--)

{

if((dep[u]-dep[p])&(1<<i)) ans=min(ans,mn[u][i]),u=fa[u][i];

if((dep[v]-dep[p])&(1<<i)) ans=min(ans,mn[v][i]),v=fa[v][i];

}

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

}

return 0;

}

NOIP2013货物运输

@OceanEye7年前

06/15

21:12

BZOJ2243

OceanEye 撰写 BZOJ 树树链剖分线段树无回复

树链剖分
细节打错了然后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;

}

BZOJ4034

@OceanEye7年前

05/7

22:56

BZOJ2434

OceanEye 撰写 AC自动机 BZOJ DFS序树树状数组无回复

AC自动机的好题，充分利用了fail树的性质

性质：S串中每个包含了T的后缀的fail指针一定经过若干层指向T

fail指针不成环

把fail树上的点dfs重标号

处理单个询问时可以把S串中的每个节点的DFS序丢进树状数组里面

查询T对应节点的DFS区间即可

处理许多询问的话离线处理即可

为了保证在树上不跑 \(x^2\) 次

可以模拟之前插入节点的方式来计算……

当然开个vector在节点上记录id也是可行的……

代码应该很好看懂

[但是我写的代码一般都巨长所以没多少人看哈哈哈]

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <vector>
#include <iostream>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

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
#define E 200010
#define BASE 'a'
#define root 0

#define lb(x) (x&-x)
int Arr[N];
void add(int pos)
{ while(pos<=N) { Arr[pos]++; pos+=lb(pos); } }
void dec(int pos)
{ while(pos<=N) { Arr[pos]--; pos+=lb(pos); } }
int query(int pos)
{
	int ret=0;
	while(pos) { ret+=Arr[pos]; pos-=lb(pos); }
	return ret;
}

int TO[E],NXT[E],fst[N],e_tot;

void Link(int _,int __)
{
	TO[e_tot]=__;
	NXT[e_tot]=fst[_];
	fst[_]=e_tot++;
}

struct node
{
	int ch[26],fail;
	int fa;
	node() { for(int i=0;i<26;i++) ch[i]=-1; }
	vector <int> rec;
	int operator [] (const int &x) { return ch[x]; }
}pool[N];

int pcnt;
int tot,he[N],l[N],r[N],_____;

void dfs(int x)
{
	l[x]=++_____;
	for(int i=fst[x];~i;i=NXT[i]) dfs(TO[i]);
	r[x]=_____;
}

void build()
{
	int x,node;
	queue <int> Q;
	Q.push(0);
	while(!Q.empty())
	{
		x=Q.front(); Q.pop();
		for(int i=0;i<26;i++)
		{
			if(!~pool[x][i]) continue;
			node=pool[x].fail;
			while(~node&&!~pool[node][i]) node=pool[node].fail;
			if(~pool[node][i]) pool[pool[x][i]].fail=pool[node][i];
			else pool[pool[x][i]].fail=root;
			Q.push(pool[x][i]);
		}
	}
	for(int i=1;i<=pcnt;i++) Link(pool[i].fail,i);
}

char s[N];
int Len;

void pre()
{
	memset(fst,-1,sizeof(fst));
	int now=0;
	pool[0].fail=pool[0].fa=-1;
	scanf("%s",s);
	Len=strlen(s);
	for(int i=0;i<Len;i++)
	{
		if(s[i]=='P')
		{
			pool[now].rec.push_back(++tot);
			he[tot]=now;
			continue;
		}
		if(s[i]=='B')
		{
			now=pool[now].fa;
			continue;
		}
		s[i]-=BASE;
		if(!~pool[now][s[i]])
		{
			pool[now].ch[s[i]]=++pcnt;
			pool[pcnt].fa=now;
		}
		now=pool[now][s[i]];
	}
	build();
	dfs(0);
}
vector <int> q[N];
int m,node,ans[N],B;
int A[N];

void solve()
{
	int now=0,__=0;
	for(int i=0;i<Len;i++)
	{
		if(s[i]=='P')
		{
			__++;
			for(int k=0;k<q[__].size();k++)
				ans[q[__][k]]=query(r[he[A[q[__][k]]]])-query(l[he[A[q[__][k]]]]-1);
			continue;
		}
		if(s[i]=='B')
		{
			dec(l[now]);
			now=pool[now].fa;
			continue;
		}
		now=pool[now][s[i]];
		add(l[now]);
	}
}

int main()
{
//	freopen("BZOJ2434.in","r",stdin);
	pre();
	read(m);
	for(int i=1;i<=m;i++) { read(A[i]); read(B); q[B].push_back(i); }
	solve();
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	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

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <queue>

#include <vector>

#include <iostream>

#define ll long long

#define INF 1000000000

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

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

#define E 200010

#define BASE 'a'

#define root 0

#define lb(x) (x&-x)

int Arr[N];

void add(int pos)

{ while(pos<=N) { Arr[pos]++; pos+=lb(pos); } }

void dec(int pos)

{ while(pos<=N) { Arr[pos]--; pos+=lb(pos); } }

int query(int pos)

{

int ret=0;

while(pos) { ret+=Arr[pos]; pos-=lb(pos); }

return ret;

}

int TO[E],NXT[E],fst[N],e_tot;

void Link(int _,int __)

{

TO[e_tot]=__;

NXT[e_tot]=fst[_];

fst[_]=e_tot++;

}

struct node

{

int ch[26],fail;

int fa;

node() { for(int i=0;i<26;i++) ch[i]=-1; }

vector <int> rec;

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

}pool[N];

int pcnt;

int tot,he[N],l[N],r[N],_____;

void dfs(int x)

{

l[x]=++_____;

for(int i=fst[x];~i;i=NXT[i]) dfs(TO[i]);

r[x]=_____;

}

void build()

{

int x,node;

queue <int> Q;

Q.push(0);

while(!Q.empty())

{

x=Q.front(); Q.pop();

for(int i=0;i<26;i++)

{

if(!~pool[x][i]) continue;

node=pool[x].fail;

while(~node&&!~pool[node][i]) node=pool[node].fail;

if(~pool[node][i]) pool[pool[x][i]].fail=pool[node][i];

else pool[pool[x][i]].fail=root;

Q.push(pool[x][i]);

}

for(int i=1;i<=pcnt;i++) Link(pool[i].fail,i);

}

char s[N];

int Len;

void pre()

{

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

int now=0;

pool[0].fail=pool[0].fa=-1;

scanf("%s",s);

Len=strlen(s);

for(int i=0;i<Len;i++)

{

if(s[i]=='P')

{

pool[now].rec.push_back(++tot);

he[tot]=now;

continue;

}

if(s[i]=='B')

{

now=pool[now].fa;

continue;

}

s[i]-=BASE;

if(!~pool[now][s[i]])

{

pool[now].ch[s[i]]=++pcnt;

pool[pcnt].fa=now;

}

now=pool[now][s[i]];

}

build();

dfs(0);

}

vector <int> q[N];

int m,node,ans[N],B;

int A[N];

void solve()

{

int now=0,__=0;

for(int i=0;i<Len;i++)

{

if(s[i]=='P')

{

__++;

for(int k=0;k<q[__].size();k++)

ans[q[__][k]]=query(r[he[A[q[__][k]]]])-query(l[he[A[q[__][k]]]]-1);

continue;

}

if(s[i]=='B')

{

dec(l[now]);

now=pool[now].fa;

continue;

}

now=pool[now][s[i]];

add(l[now]);

}

int main()

{

// freopen("BZOJ2434.in","r",stdin);

pre();

read(m);

for(int i=1;i<=m;i++) { read(A[i]); read(B); q[B].push_back(i); }

solve();

for(int i=1;i<=m;i++) printf("%d\n",ans[i]);

return 0;

}

BZOJ2434

@OceanEye7年前

05/3

19:03

BZOJ4012

OceanEye 撰写二分查找动态点分治树无回复

某码农题
动态点分治[或者说点分树?]
转化一下[差分一下]就可以看出
要维护一棵树
可以在log~log方的时间复杂度内跑完整棵树的前缀和[1,l-1],[1,r]
于是用了点分树
树链剖分可不可以还没想过，目测是不行的
用了vector来控制空间
当然有大佬愿意写动态开点线段树或者平衡树也是很强的orz

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <iostream>
#define ll long long
#define INF 1000000000
#define p(x) ('0'<=x&&x<='9')

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 150010
#define Q 200010

int TO[N<<1],val[N<<1],NXT[N<<1],fst[N],e_tot;

void add_e(int _,int __,int ___)
{
	TO[e_tot]=__; val[e_tot]=___; NXT[e_tot]=fst[_]; fst[_]=e_tot++;
	TO[e_tot]=_; val[e_tot]=___; NXT[e_tot]=fst[__]; fst[__]=e_tot++;
}

int age[N];
//

struct sav
{
	ll tot; int age;
	sav(int _,int __) : tot(_),age(__){}
	bool operator < (const sav &x) const { return age<x.age; }
};

struct rec
{
	int fa,id;
	int son[3],_tot;
	vector <sav> Arr[3];
	vector <sav> dist;
	int operator [] (const int &x) { return son[x]; }
}pool[N];

int root,siz[N],mxsiz[N],d[N],T,now;
bool use[N];

void dfs_push(int x,int f,ll dist)
{
	pool[now].dist.push_back(sav(dist,x));
	siz[x]=1;
	pool[now].Arr[pool[now]._tot].push_back(sav(dist,age[x]));
	for(int i=fst[x];~i;i=NXT[i])
	{
		if(use[TO[i]]||TO[i]==f) continue;
		dfs_push(TO[i],x,dist+val[i]);
		siz[x]+=siz[TO[i]];
	}
}

void getroot(int x,int f)
{
	siz[x]=1; mxsiz[x]=0;
	for(int i=fst[x];~i;i=NXT[i])
	{
		if(TO[i]==f||use[TO[i]]) continue;
		getroot(TO[i],x);
		siz[x]+=siz[TO[i]];
		mxsiz[x]=max(mxsiz[x],siz[TO[i]]);
	}
	mxsiz[x]=max(mxsiz[x],T-siz[x]);
	if(mxsiz[x]<mxsiz[root]) root=x;
}

void dfs_build(int x,int f)
{
	now=x;
	pool[x].fa=f;
	use[x]=true;
	for(int i=fst[x];~i;i=NXT[i])
	{
		if(use[TO[i]]) continue;
		root=0;
		T=siz[TO[i]];
		dfs_push(TO[i],0,val[i]);
		getroot(TO[i],0);
		pool[now].son[pool[now]._tot]=root;
		siz[root]=siz[TO[i]];
		sort(pool[now].Arr[pool[now]._tot].begin(),pool[now].Arr[pool[now]._tot].end());
		for(int j=1;j<pool[now].Arr[pool[now]._tot].size();j++)
			pool[now].Arr[pool[now]._tot][j].tot+=pool[now].Arr[pool[now]._tot][j-1].tot;
		pool[now]._tot++;
	}
	pool[now].dist.push_back(sav(0,now));
	sort(pool[now].dist.begin(),pool[now].dist.end());
	for(int i=0;i<pool[x]._tot;i++) dfs_build(pool[x][i],x);
}

int n,m,A;

void pre()
{
	int _,__,___;
	read(n); read(m); read(A);
	for(int i=1;i<=n;i++)
	{
		fst[i]=-1;
		read(age[i]);
		age[i]++;
	}
	for(int i=1;i<n;i++)
	{
		read(_); read(__); read(___);
		add_e(_,__,___);
	}
	T=n;
	mxsiz[0]=INF;
	getroot(1,0);
	dfs_build(root,0);
}

ll get_ans(int x,int l,int r)
{
	sav _(0,l-1),__(0,r);
	vector <sav> :: iterator it,it2;
	int L,R,pre=0,tot=0,___,S=x;
	ll dist=0,ret=0;
	while(x)
	{
		tot=0;
		for(int i=0;i<pool[x]._tot;i++)
		{
			if(pool[x][i]==pre)
				continue;
			it = upper_bound(pool[x].Arr[i].begin(),pool[x].Arr[i].end(),_);
			if(it!=pool[x].Arr[i].begin())
			{
				it--;
				ret-=it->tot;
				it++;
			}
			it2 = upper_bound(pool[x].Arr[i].begin(),pool[x].Arr[i].end(),__);
			if(it2!=pool[x].Arr[i].begin())
			{
				it2--;
				ret+=it2->tot;
				it2++;
			}
			tot+=distance(it,it2);
		}
		if(age[x]<=r&&age[x]>=l) tot++;
		it=lower_bound(pool[x].dist.begin(),pool[x].dist.end(),sav(0,S));
		dist=it->tot;
		ret+=dist*tot;
		pre=x;
		x=pool[x].fa;
	}
	return ret;
}

ll lastans;

int main()
{
//	freopen("BZOJ4012.in","r",stdin);
	ll _,__,___,L,R;
	pre();
	while(m--)
	{
		read(_); read(__); read(___);
		__+=lastans; ___+=lastans;
		__%=A; ___%=A;
		__++; ___++;
		L=min(__,___);
		R=max(__,___);
		lastans=get_ans(_,L,R);
		printf("%lld\n",lastans);
	}
	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

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <vector>

#include <iostream>

#define ll long long

#define INF 1000000000

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

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 150010

#define Q 200010

int TO[N<<1],val[N<<1],NXT[N<<1],fst[N],e_tot;

void add_e(int _,int __,int ___)

{

TO[e_tot]=__; val[e_tot]=___; NXT[e_tot]=fst[_]; fst[_]=e_tot++;

TO[e_tot]=_; val[e_tot]=___; NXT[e_tot]=fst[__]; fst[__]=e_tot++;

}

int age[N];

struct sav

{

ll tot; int age;

sav(int _,int __) : tot(_),age(__){}

bool operator < (const sav &x) const { return age<x.age; }

};

struct rec

{

int fa,id;

int son[3],_tot;

vector <sav> Arr[3];

vector <sav> dist;

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

}pool[N];

int root,siz[N],mxsiz[N],d[N],T,now;

bool use[N];

void dfs_push(int x,int f,ll dist)

{

pool[now].dist.push_back(sav(dist,x));

siz[x]=1;

pool[now].Arr[pool[now]._tot].push_back(sav(dist,age[x]));

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

{

if(use[TO[i]]||TO[i]==f) continue;

dfs_push(TO[i],x,dist+val[i]);

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

}

void getroot(int x,int f)

{

siz[x]=1; mxsiz[x]=0;

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

{

if(TO[i]==f||use[TO[i]]) continue;

getroot(TO[i],x);

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

mxsiz[x]=max(mxsiz[x],siz[TO[i]]);

}

mxsiz[x]=max(mxsiz[x],T-siz[x]);

if(mxsiz[x]<mxsiz[root]) root=x;

}

void dfs_build(int x,int f)

{

now=x;

pool[x].fa=f;

use[x]=true;

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

{

if(use[TO[i]]) continue;

root=0;

T=siz[TO[i]];

dfs_push(TO[i],0,val[i]);

getroot(TO[i],0);

pool[now].son[pool[now]._tot]=root;

siz[root]=siz[TO[i]];

sort(pool[now].Arr[pool[now]._tot].begin(),pool[now].Arr[pool[now]._tot].end());

for(int j=1;j<pool[now].Arr[pool[now]._tot].size();j++)

pool[now].Arr[pool[now]._tot][j].tot+=pool[now].Arr[pool[now]._tot][j-1].tot;

pool[now]._tot++;

}

pool[now].dist.push_back(sav(0,now));

sort(pool[now].dist.begin(),pool[now].dist.end());

for(int i=0;i<pool[x]._tot;i++) dfs_build(pool[x][i],x);

}

int n,m,A;

void pre()

{

int _,__,___;

read(n); read(m); read(A);

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

{

fst[i]=-1;

read(age[i]);

age[i]++;

}

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

{

read(_); read(__); read(___);

add_e(_,__,___);

}

T=n;

mxsiz[0]=INF;

getroot(1,0);

dfs_build(root,0);

}

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

{

sav _(0,l-1),__(0,r);

vector <sav> :: iterator it,it2;

int L,R,pre=0,tot=0,___,S=x;

ll dist=0,ret=0;

while(x)

{

tot=0;

for(int i=0;i<pool[x]._tot;i++)

{

if(pool[x][i]==pre)

continue;

it = upper_bound(pool[x].Arr[i].begin(),pool[x].Arr[i].end(),_);

if(it!=pool[x].Arr[i].begin())

{

it--;

ret-=it->tot;

it++;

}

it2 = upper_bound(pool[x].Arr[i].begin(),pool[x].Arr[i].end(),__);

if(it2!=pool[x].Arr[i].begin())

{

it2--;

ret+=it2->tot;

it2++;

}

tot+=distance(it,it2);

}

if(age[x]<=r&&age[x]>=l) tot++;

it=lower_bound(pool[x].dist.begin(),pool[x].dist.end(),sav(0,S));

dist=it->tot;

ret+=dist*tot;

pre=x;

x=pool[x].fa;

}

return ret;

}

ll lastans;

int main()

{

// freopen("BZOJ4012.in","r",stdin);

ll _,__,___,L,R;

pre();

while(m--)

{

read(_); read(__); read(___);

__+=lastans; ___+=lastans;

__%=A; ___%=A;

__++; ___++;

L=min(__,___);

R=max(__,___);

lastans=get_ans(_,L,R);

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

}

return 0;

}

OceanEye's Blog

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

@OceanEye7年前

NOIP2013货物运输

NOIP2013货物运输

@OceanEye7年前

BZOJ2243

BZOJ2243

@OceanEye7年前

BZOJ4034

BZOJ4034

@OceanEye7年前

BZOJ2434

BZOJ2434

@OceanEye7年前

BZOJ4012

BZOJ4012

友情链接

近期文章

标签