基础题 – OceanEye's Blog

Date Time

17/06/4 13:26

Author

简单的树链剖分，分轻重链之后依然满足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;

}

Date Time

17/05/20 15:36

Author

OceanEye

裸的主席树

前k个可能是一个优先级的一部分

看代码吧:-D

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#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

struct rec
{
	int id,pos,val;
}RRR[N<<1];
int ____;

bool comp(const rec &x,const rec &y)
{ return x.id<y.id; }

int n,m,p;

void pre()
{
	read(n); read(m);
	int _,__,___;
	for(int i=1;i<=n;i++)
	{
		read(_); read(__); read(___);
		RRR[____].id=_; RRR[____].val=1; RRR[____].pos=___; ____++;
		RRR[____].id=__+1; RRR[____].val=-1; RRR[____].pos=___; ____++;
	}
	sort(RRR,RRR+____,comp);
}

struct node
{
	int l,r,c[2],cnt;
	ll sum;
}pool[N<<6];
#define L pool[x].l
#define R pool[x].r
#define Lc pool[x].c[0]
#define Rc pool[x].c[1]
#define SUM pool[x].sum
#define CNT pool[x].cnt

int RT[N],pcnt;

void PushUP(int x)
{
	SUM=pool[Lc].sum+pool[Rc].sum;
	CNT=pool[Lc].cnt+pool[Rc].cnt;
}

void insert(const int &pos,int& x,const int &val)
{
	pool[++pcnt]=pool[x]; x=pcnt;
	if(L==R) { CNT+=val; SUM=1LL*CNT*pos; return; }
	int mid=(L+R)>>1;
	if(mid>=pos)
	{
		if(Lc==0)pool[Lc].l=L,pool[Lc].r=mid;
		insert(pos,Lc,val);
	}
	else
	{
		if(Rc==0)pool[Rc].l=mid+1,pool[Rc].r=R;
		insert(pos,Rc,val);
	}
	PushUP(x);
}

ll sum(int x,int k)
{
	if(x==0) return 0;
	if(CNT<=k) return SUM;
	if(L==R) { return (ll)min(k,CNT)*L; }
	return pool[Lc].cnt>=k?sum(Lc,k):pool[Lc].sum+sum(Rc,k-pool[Lc].cnt);
}

int main()
{
	freopen("BZOJ3932.in","r",stdin);
	pre();
	____=0;
	pool[0].l=1; pool[0].r=10000050;
	for(int i=1;i<=m;i++)
	{
		RT[i]=RT[i-1];
		for(;RRR[____].id==i;____++)
			insert(RRR[____].pos,RT[i],RRR[____].val);
	}
	static int Q,T,A,B,C,k,mid;
	ll pre=1;
	while(m--)
	{
		read(T); read(A); read(B); read(C);
		pre%=C; A%=C; B%=C;
		k=1+(ll)(1LL*A*pre+B)%C;
		printf("%lld\n",pre=sum(RT[T],k));
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#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

struct rec

{

int id,pos,val;

}RRR[N<<1];

int ____;

bool comp(const rec &x,const rec &y)

{ return x.id<y.id; }

int n,m,p;

void pre()

{

read(n); read(m);

int _,__,___;

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

{

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

RRR[____].id=_; RRR[____].val=1; RRR[____].pos=___; ____++;

RRR[____].id=__+1; RRR[____].val=-1; RRR[____].pos=___; ____++;

}

sort(RRR,RRR+____,comp);

}

struct node

{

int l,r,c[2],cnt;

ll sum;

}pool[N<<6];

#define L pool[x].l

#define R pool[x].r

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

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

#define SUM pool[x].sum

#define CNT pool[x].cnt

int RT[N],pcnt;

void PushUP(int x)

{

SUM=pool[Lc].sum+pool[Rc].sum;

CNT=pool[Lc].cnt+pool[Rc].cnt;

}

void insert(const int &pos,int& x,const int &val)

{

pool[++pcnt]=pool[x]; x=pcnt;

if(L==R) { CNT+=val; SUM=1LL*CNT*pos; return; }

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

if(mid>=pos)

{

if(Lc==0)pool[Lc].l=L,pool[Lc].r=mid;

insert(pos,Lc,val);

}

else

{

if(Rc==0)pool[Rc].l=mid+1,pool[Rc].r=R;

insert(pos,Rc,val);

}

PushUP(x);

}

ll sum(int x,int k)

{

if(x==0) return 0;

if(CNT<=k) return SUM;

if(L==R) { return (ll)min(k,CNT)*L; }

return pool[Lc].cnt>=k?sum(Lc,k):pool[Lc].sum+sum(Rc,k-pool[Lc].cnt);

}

int main()

{

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

pre();

____=0;

pool[0].l=1; pool[0].r=10000050;

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

{

RT[i]=RT[i-1];

for(;RRR[____].id==i;____++)

insert(RRR[____].pos,RT[i],RRR[____].val);

}

static int Q,T,A,B,C,k,mid;

ll pre=1;

while(m--)

{

read(T); read(A); read(B); read(C);

pre%=C; A%=C; B%=C;

k=1+(ll)(1LL*A*pre+B)%C;

printf("%lld\n",pre=sum(RT[T],k));

}

return 0;

}

Date Time

17/04/8 18:51

Author

OceanEye

妈呀这题真卡时。
不得不承认这是我第二道用递归线段树AC的题目qwq太感动了
这题差不多是线段树的裸题了，，只需要bitset维护每一条线段上的颜色还有记得维护PushDown标记就好了。
其他都是细节问题，但是不知道为什么我加了读入优化之后就爆炸WA，，
所以只贴一份AC的无读入优化的代码好了qwq

#include <cstdio>
#include <algorithm>
#include <bitset>
#include <iostream>

using namespace std;

const int NIL = 0;
const int maxn = 100050;
const int Root = 1;

struct node 
{
	bitset <32> rec;
	int l,r;
	bool flag;
}T[8*maxn];

int n,t,o,i,j;
bitset <32> ans;

void build(int l,int r,int k)
{
	T[k].rec.set(1);
	T[k].l = l;T[k].r = r;
	if (l==r) return;
	int mid = (l+r) >> 1;
	build(l,mid,k<<1); build(mid+1,r,k<<1|1);
}

void PushUP(int x)
{
	int lc = x<<1 , rc = x<<1|1; T[x].rec.reset();
	for(int i=1;i<=t;i++) if(T[lc].rec.test(i) || T[rc].rec.test(i)) T[x].rec.set(i); if (T[x].rec.count() == 1) T[x].flag = true; } void insert(int l,int r,int c,int x) { if (T[x].l >= l && T[x].r <= r)
	{ T[x].rec.reset(); T[x].rec.set(c); T[x].flag = true; return; }
	if (T[x].l==T[x].r || T[x].r < l || T[x].l > r) return;
	if(T[x].flag)
	{
		T[x<<1].rec.reset(); T[x<<1|1].rec.reset();
		for(int i=1;i<=t;i++)
			if (T[x].rec.test(i)){ T[x<<1].rec.set(i); T[x<<1|1].rec.set(i); }
		T[x<<1].flag = true;T[x<<1|1].flag = true;
		T[x].flag = false;
	}
	insert(l,r,c,x<<1);
	insert(l,r,c,x<<1|1);
	PushUP(x);
}
void query(int l,int r ,int x)
{
	if(T[x].l > r || T[x].r < l) return; 
	if(T[x].l <= l || T[x].r >= r)if (T[x].flag)
	{
		for(int i=1;i<=t;i++) if (T[x].rec.test(i)) ans.set(i); return; } if (T[x].l >= l && T[x].r <= r)
	{
		for(int i=1;i<=t;i++) if (T[x].rec.test(i)) ans.set(i);
		return;
	}
	if (T[x].l==T[x].r) return;
	query(l,r,x<<1);
	query(l,r,x<<1|1);
}
int main()
{
	std::ios::sync_with_stdio(false); cin >> n >> t >> o;
	build(1,n,Root); 
	for(i=1;i<=o;i++) { char cmd = getchar(); while(cmd == '\n' || cmd == ' ') cmd = getchar(); if (cmd == 'C') { int l,r,c; cin >> l >> r >> c ; if (l > r) swap(l,r);
			insert(l,r,c,Root);
		}
		if (cmd == 'P')
		{
			int l,r;
			cin >> l >> r ; if (l > r) swap(l,r);
			ans.reset();
			query(l,r,Root);
			cout << ans.count() << endl;
		}
	}
	return 0;
}

#include <cstdio>

#include <algorithm>

#include <bitset>

#include <iostream>

using namespace std;

const int NIL = 0;

const int maxn = 100050;

const int Root = 1;

struct node

{

bitset <32> rec;

int l,r;

bool flag;

}T[8*maxn];

int n,t,o,i,j;

bitset <32> ans;

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

{

T[k].rec.set(1);

T[k].l = l;T[k].r = r;

if (l==r) return;

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

build(l,mid,k<<1); build(mid+1,r,k<<1|1);

}

void PushUP(int x)

{

int lc = x<<1 , rc = x<<1|1; T[x].rec.reset();

for(int i=1;i<=t;i++) if(T[lc].rec.test(i) || T[rc].rec.test(i)) T[x].rec.set(i); if (T[x].rec.count() == 1) T[x].flag = true; } void insert(int l,int r,int c,int x) { if (T[x].l >= l && T[x].r <= r)

{ T[x].rec.reset(); T[x].rec.set(c); T[x].flag = true; return; }

if (T[x].l==T[x].r || T[x].r < l || T[x].l > r) return;

if(T[x].flag)

{

T[x<<1].rec.reset(); T[x<<1|1].rec.reset();

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

if (T[x].rec.test(i)){ T[x<<1].rec.set(i); T[x<<1|1].rec.set(i); }

T[x<<1].flag = true;T[x<<1|1].flag = true;

T[x].flag = false;

}

insert(l,r,c,x<<1);

insert(l,r,c,x<<1|1);

PushUP(x);

}

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

{

if(T[x].l > r || T[x].r < l) return;

if(T[x].l <= l || T[x].r >= r)if (T[x].flag)

{

for(int i=1;i<=t;i++) if (T[x].rec.test(i)) ans.set(i); return; } if (T[x].l >= l && T[x].r <= r)

{

for(int i=1;i<=t;i++) if (T[x].rec.test(i)) ans.set(i);

return;

}

if (T[x].l==T[x].r) return;

query(l,r,x<<1);

query(l,r,x<<1|1);

}

int main()

{

std::ios::sync_with_stdio(false); cin >> n >> t >> o;

build(1,n,Root);

for(i=1;i<=o;i++) { char cmd = getchar(); while(cmd == '\n' || cmd == ' ') cmd = getchar(); if (cmd == 'C') { int l,r,c; cin >> l >> r >> c ; if (l > r) swap(l,r);

insert(l,r,c,Root);

}

if (cmd == 'P')

{

int l,r;

cin >> l >> r ; if (l > r) swap(l,r);

ans.reset();

query(l,r,Root);

cout << ans.count() << endl;

}

return 0;

}

OceanEye's Blog

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

Date Time

Author

Category

Tags

BZOJ4034

Date Time

Author

Category

Tags

BZOJ3932

Date Time

Author

Category

Tags

POJ 2777 线段树+bitset