分类目录归档:线段树

124 – ZOJ Monthly, March 2013 – A, A Simple Tree Problem, 修改子树 和查询。

Given a rooted tree, each node has a boolean (0 or 1) labeled on it. Initially, all the labels are 0.

We define this kind of operation: given a subtree, negate all its labels.

And we want to query the numbers of 1’s of a subtree.

Input

Multiple test cases.

First line, two integer N and M, denoting the numbers of nodes and numbers of operations and queries.(1<=N<=100000, 1<=M<=10000)

Then a line with N-1 integers, denoting the parent of node 2..N. Root is node 1.

Then M lines, each line are in the format “o node” or “q node“, denoting we want to operate or query on the subtree with root of a certain node.

Output

For each query, output an integer in a line.

Output a blank line after each test case.

Sample Input

3 2
1 1
o 2
q 1

Sample Output

1

Problem’s Author: CUI, Tianyi

批量地 修改子树 可以被看做段修改(把树通过一个入点出点路径序列来表示),这样即转化为了线段树的段修改和段查询。

SPOJ QTREE 树链剖分 做法。

这个做法。。。纯粹。。。。恶心自己。。。。泪奔。。。。

# include <cstdio>
# include <cstring>
# include <iostream>
# include <algorithm>
# include <vector>
using namespace std;
const int SIZE = 10007;
const int INF = 2147483647;
int t, n;
struct EDGE { int v, next, len; } e[SIZE<<1];
int h[SIZE], tot, Edgesign[SIZE];
void AddEdge(int u, int v, int len)
{
	e[++tot].v = v;
	e[tot].len = len;
	e[tot].next = h[u];
	h[u] = tot;
}
bool vis[SIZE];
int tree[(SIZE<<1)<<2], pos[(SIZE<<1)<<2], M;
int list[SIZE<<1], firstshow[SIZE], ltot;
int tsize[SIZE], Ednode[SIZE], dist[SIZE];
int Generfa(int s, int t)
{
	s = firstshow[s];
	t = firstshow[t];
	if ( s > t ) swap(s, t);
	int ans = 0, min = INF;
	for ( s+=M-1, t+=M+1; s^t^1; s>>=1, t>>=1)
	{
		if (~s&1 && tree[s^1] < min) min = tree[s^1], ans = pos[s^1];
		if ( t&1 && tree[t^1] < min) min = tree[t^1], ans = pos[t^1];
	}
	return list[ans];
}
inline void Intree(int &x, int &d)
{
	tree[M + (++ltot)] = d;
	list[ltot] = x;
	pos[M+ltot] = ltot;
	if ( firstshow[x] == 0 ) firstshow[x] = ltot;
}
void LCA(int x, int d)
{
	vis[x] = true;
	Intree(x, d);
	tsize[x] = 1;
	dist[x] = d;
	for (int i = h[x]; i; i = e[i].next)
	{
		if ( vis[e[i].v] ) continue;
		LCA(e[i].v, d+1);
		Intree(x, d);
		tsize[x] += tsize[e[i].v];
		Ednode[e[i].v] = e[i].len; //边权加在点上
	}
	vis[x] = false;
}
class Sgttree
{
	public:
	vector <int> tree;
	int size, M;
	void Init(int insize)
	{
		size = insize; tree.clear();
		if ( size == 1 ) tree.resize(7);
		else tree.resize(size<<2);
		for (M = 1; M <= size + 1; M <<= 1);
		for (int i = (size<<2) - 1; i; --i ) tree[i] = -INF;
	}
	void Build()
	{
		for (int i = M - 1; i; --i )
			if ( tree[i<<1] > tree[(i<<1)+1] ) tree[i] = tree[i<<1];
			else tree[i] = tree[(i<<1)+1];
	}
	void Modify(int x, int n)
	{
		tree[n+=M] = x;
		for ( n >>= 1; n; n >>= 1 ) tree[n] = max(tree[n<<1], tree[(n<<1)+1]);
	}
	int getmax(int s, int t)
	{
		int max = -INF;
		if ( s > t ) swap(s, t);
		for ( s+=M-1, t+=M+1; s^t^1; s>>=1, t>>=1 )
		{
			if (~s&1 && tree[s^1] > max ) max = tree[s^1];
			if ( t&1 && tree[t^1] > max ) max = tree[t^1];
		}
		return max;
	}
}_st;
vector <Sgttree> sgtree;
int belong[SIZE], sgttot, sgtsize[SIZE], sgtpos[SIZE], pointpos[SIZE];
int firptr[SIZE]; //当前线段树中第一个节点编号
int fa[SIZE];
void SelcEdge(int x)
{
	vis[x] = true;
	int i, maxsize = -INF, which;
	for (i = h[x]; i; i = e[i].next)
		if ( !vis[e[i].v] && tsize[e[i].v] > maxsize ) maxsize = tsize[e[i].v], which = e[i].v;
	for (i = h[x]; i; i = e[i].next)
	{
		if ( vis[e[i].v] ) continue;
		if ( e[i].v == which )
		{
			if( belong[x] == -1 ) belong[e[i].v] = ++sgttot;
			else belong[e[i].v] = belong[x];
		}
		else belong[e[i].v] = -1; //标记为轻边指向点
		SelcEdge(e[i].v);
	}
	vis[x] = false;
}
inline void InsertSgt(int x)
{
	int k = belong[x];
	if ( sgtpos[k] == 0 ) firptr[k] = x;
	sgtree[k].tree[sgtree[k].M + (++sgtpos[k])] = Ednode[x];
	pointpos[x] = sgtpos[k];
}
void CreatSgt(int x)
{
	vis[x] = true;
	if ( belong[x] != -1 ) InsertSgt(x);
	for (int i = h[x]; i; i = e[i].next )
	{
		if ( vis[e[i].v] ) continue;
		CreatSgt(e[i].v);
		fa[e[i].v] = x;
	}
	vis[x] = false;
}

void Init()
{
	int i, a, b, c;
	scanf("%d", &n);
	memset(h, 0, sizeof(h));
	memset(vis, 0, sizeof(vis));
	memset(firstshow, 0, sizeof(firstshow));
	memset(tree, 44, sizeof(tree));
	memset(sgtsize, 0, sizeof(sgtsize));
	memset(sgtpos, 0, sizeof(sgtpos));
	sgtree.clear();
	tot = ltot = sgttot = 0;
	Ednode[1] = -INF;
	for ( M = 1; M <= (n<<1)+1; M <<= 1 );
	for (i = 1; i != n; ++i )
	{
		scanf("%d%d%d", &a, &b, &c);
		AddEdge(a,b,c); Edgesign[i] = tot;
		AddEdge(b,a,c);
	}
	LCA(1,0);
	for (i = ltot+M; i; --i )
		if ( tree[i>>1] > tree[i] ) tree[i>>1] = tree[i], pos[i>>1] = pos[i];

}
void change(int x, int a)
{
	int b = e[ Edgesign[a]+1].v, k;
	a = e[ Edgesign[a] ].v;
	if( dist[a] < dist[b] ) a = b;
	k = belong[a];
	if ( k != -1 ) sgtree[k].Modify(x, pointpos[a]);
	else Ednode[a] = x;
}
int find(int a, int b)
{
	if ( a == b ) return 0;
	int root = Generfa(a, b), ans = -INF, l, r;
	for (int i = 0; i != 2; ++i, a = b )
		for ( ;a && dist[a] > dist[root]; a = fa[a] )
			if ( belong[root] == belong[a] && belong[a] != -1 )
			{
				l = min(pointpos[root], pointpos[a])+1;
				r = max(pointpos[root], pointpos[a]);
				ans = max( ans, sgtree[belong[root]].getmax(l, r) );
				break;
			}
			else if ( belong[a] == -1 ) ans = max( ans, Ednode[a]);
			else
			{
				ans = max( ans, sgtree[belong[a]].getmax(1,pointpos[a]) );
				a = firptr[belong[a]];
			}
	return ans;
}
void Work()
{
	int i, a, b;
	char tmp[30];
	belong[1] = -1; SelcEdge(1);
	for (i = 1; i <= n; ++i ) if ( belong[i] > 0 ) ++sgtsize[ belong[i] ];
	sgtsize[0] = 1;
	for (i = 0; i <= sgttot; ++i ) //vector下表从0开始
	{
		_st.Init(sgtsize[i]);
		sgtree.push_back(_st);
	}
	fa[1] = 1; CreatSgt(1);
	for (i = 1; i <= sgttot; ++i ) sgtree[i].Build();
	while( true )
	{
		scanf("%s", tmp);
		if ( tmp[0] != 'D' ) scanf("%d%d", &a, &b);
		else return ;
		switch(tmp[0])
		{
			case 'Q': printf("%d\n", find(a, b)); break;
			case 'C': change(b, a); break;
		}
	}
}
int main()
{
	scanf("%d", &t);
	while(t--)
	{
		Init();
		Work();
	}
	return 0;
}

POJ 2528 线段树

本体思路其实很简单,离散化后线段树段修改,最后统计一遍即可。

不过此题数据甚是恶心,HASH改了好几遍才AC,想想以后离散化还是不用HASH比较好= =。。

不过也借由此题促使咱回去看《统计的力量》熟悉重口味版线段树,收获良多>u<。。

# include <cstdio>
# include <algorithm>
# include <cstring>
using namespace std;
const int MOD = 50007;
int t, n;

struct POST
{
	int l, r, id;
	bool show;
	POST(){ show = false; }
}p[10003];

int list[40003], tot, f[MOD+2], trans[MOD+2];
int hash(int x)
{
	int pos;
	pos = (3*x + x%107 + x>>2) % MOD;
	while ( f[pos] && f[pos] != x ) pos = (pos + 173)%MOD;
	if ( pos < 0 ) pos += MOD;
	return pos;
}

int M, tree[131077], tf[131007], time;
const int tsize = sizeof(tree), fsize = sizeof(f);
void modify(int s, int t, int c)
{
	++time;
	for ( s+=M-1, t+=M+1; s^t^1; s>>=1, t>>=1 )
	{
		if (~s&1 ) tree[s^1] = c, tf[s^1] = time;
		if ( t&1 ) tree[t^1] = c, tf[t^1] = time;
	}
}
void ask(int x, int mt, int c)
{
	if ( x <= M + tot && tree[x] && tf[x] > mt ) c = tree[x], mt = tf[x];
	if ( x >= M )
	{
		if (c) p1.show = true;
		return ;
	}
	ask(x<<1, mt, c);
	ask((x<<1)+1, mt, c);
}

void work()
{
	int i, a, b;
	tot = time = 0;
	memset(f, 0, sizeof(f));
	scanf("%d", &n);
	if ( n == 0 )
	{
		printf("0\n");
		return ;
	}
	for ( i = 1; i <= n; ++i ) scanf("%d%d", &p[i].l, &p[i].r);
	for ( i = 1; i <= n; ++i )
	{
		p[i].id = i;
		p[i].show = false;
		a = hash(p[i].l);
		b = hash(p[i].r);
		if ( !f[a] ) f[a] = p[i].l, list[++tot] = p[i].l;
		if ( !f[b] ) f[b] = p[i].r, list[++tot] = p[i].r;
	}
	sort(list+1, list+1+tot);
	a = tot;
	for (i = 1; i < a; ++i )
		if ( list[i] + 1 < list[i+1] ) list[++tot] = list[i] + 1;
	sort(list+1, list+1+tot);

	for ( i = 1; i <= tot; ++i ) trans[hash(list[i])] = i;
	for ( i = 1; i <= n; ++i )
	{
		p[i].l = trans[hash(p[i].l)];
		p[i].r = trans[hash(p[i].r)];
	}
	for ( M = 1; M < tot+2; M<<=1 );
	memset(tree, 0, tsize);

	for ( i = 1; i <= n; ++i ) modify(p[i].l, p[i].r, p[i].id);
	ask(1, 0, 0);
	for ( a = 0, i = 1; i<= n; ++i ) if ( p[i].show ) ++a;
	printf("%d\n", a);
}

int main()
{
	scanf("%d", &t);
	while ( t-- ) work();
	return 0;
}