RMQ、LCA

Catalog

POJ 3264 Balanced Lineup（ Line segment tree 、RMQ）

HDU 2586 How far away？（LCA The use of, ）

CSU 1079 Query on tree （LCA）

---

POJ 3264 Balanced Lineup（ Line segment tree 、RMQ）

  subject ：

Description

For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

Input

Line 1: Two space-separated integers, N and Q. 
Lines 2.. N+1: Line i+1 contains a single integer that is the height of cow i 
Lines N+2.. N+ Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.

Output

Lines 1.. Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.

Sample Input

6 3
1
7
3
4
2
5
1 5
4 6
2 2

Sample Output

6
3
0

The question ：

Give a sequence and some queries

Output the difference between the maximum value and the minimum value in the query interval

This topic can be done with line segment tree , It can also be used. RMQ To do it

RMQ Code ：

// Why does the second dimension of the array open 16 It's wrong. ,17 Yes. ...
#include<iostream>
using namespace std;

int maxs[50000][17];
int mins[50000][17];

int main()
{
	int n, q, k, low, high, rmax, rmin;
	cin >> n >> q;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &maxs[i][0]);
		mins[i][0] = maxs[i][0];
	}
	for (int j = 1; (1 << j) <= n; j++)
	{
		for (int i = 0; i < n; i++)
		{
			maxs[i][j] = maxs[i][j - 1];
			mins[i][j] = mins[i][j - 1];
			k = i + (1 << (j - 1));
			if (k < n && maxs[i][j] < maxs[k][j - 1])maxs[i][j] = maxs[k][j - 1];
			if (k < n && mins[i][j] > mins[k][j - 1])mins[i][j] = mins[k][j - 1];
		}
	}
	while (q--)
	{
		scanf("%d%d", &low, &high);
		low--;
		high--;
		int j = 0;
		while ((1 << j) <= high - low)j++;
		j--;
		rmax = maxs[high + 1 - (1 << j)][j];
		if (rmax < maxs[low][j])rmax = maxs[low][j];
		rmin = mins[high + 1 - (1 << j)][j];
		if (rmin > mins[low][j])rmin = mins[low][j];
		printf("%d\n", rmax - rmin);
	}
	return 0;
}

Write RMQ Pay attention to your code ,main There is nothing in the function 50000, It didn't show up 17, All calculations about crossing the border must rely on n, It has nothing to do with the size of the array . Of course , The array must be large enough .

Line tree code ：

#include<iostream>
using namespace std;

int num[50001];
int maxx[200001];
int minn[200001];

void build(int key, int low, int high)
{
	if (low == high)
	{
		minn[key] = maxx[key] = num[low];
		return;
	}
	int mid = (low + high) / 2;
	build(key * 2, low, mid);
	build(key * 2 + 1, mid + 1, high);
	maxx[key] = (maxx[key * 2] > maxx[key * 2 + 1]) ? maxx[key * 2] : maxx[key * 2 + 1];
	minn[key] = (minn[key * 2] < minn[key * 2 + 1]) ? minn[key * 2] : minn[key * 2 + 1];
}

int querymaxx(int key, int low, int high, int x, int y)
{
	if (low == x && high == y)return maxx[key];
	int mid = (low + high) / 2;
	if (mid < x)return querymaxx(key * 2 + 1, mid + 1, high, x, y);
	if (mid >= y)return querymaxx(key * 2, low, mid, x, y);
	int a = querymaxx(key * 2, low, mid, x, mid);
	int b = querymaxx(key * 2 + 1, mid + 1, high, mid + 1, y);
	return  (a>b) ? a : b;
}

int queryminn(int key, int low, int high, int x, int y)
{
	if (low == x && high == y)return minn[key];
	int mid = (low + high) / 2;
	if (mid < x)return queryminn(key * 2 + 1, mid + 1, high, x, y);
	if (mid >= y)return queryminn(key * 2, low, mid, x, y);
	int a = queryminn(key * 2, low, mid, x, mid);
	int b = queryminn(key * 2 + 1, mid + 1, high, mid + 1, y);
	return  (a<b) ? a : b;
}

int main()
{
	int n, q, low, high;
	cin >> n >> q;
	for (int i = 1; i <= n; i++)scanf("%d", &num[i]);
	build(1, 1, n);
	while (q--)
	{
		scanf("%d%d", &low, &high);
		printf("%d\n", querymaxx(1, 1, n, low, high) - queryminn(1, 1, n, low, high));
	}
	return 0;
}

Because there is no update operation , So it's omitted update function .

HDU 2586 How far away？（LCA The use of, ）

  subject ：

Description

There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.

Input

First line is a single integer T(T<=10), indicating the number of test cases. 
  For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n. 
  Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.

Output

For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.

Sample Input

2
3 2
1 2 10
3 1 15
1 2
2 3

2 2
1 2 100
1 2
2 1

Sample Output

10
25
100
100

The question ：
n A house for n-1 The roads connect （ It's a tree ）, For each inquiry ,

Find out 2 A direct line distance from the house

Ideas ：

This topic only needs to build a tree , Then query any 2 The distance between the points , No update operation , So it can be used LCA To do it .

LCA Is to find the nearest common ancestor , What's the use ？

This is because there is a property , hypothesis B and C The most recent public ancestor of A, So for the root node of the whole tree D,

There are ：|BD|+|CD|-|AD|*2=|BC|

in other words , As long as all points are found in advance D Distance of dist（dist The size is n）,

Then for the input B and C, Just find the nearest common ancestor , You can use the above formula to get the answer .

step ：

1, Save edge

Every time you type 1 side , hold 2 Each point is stored in the other's son list

Because the number of sons is unknown , But the total is 2n-2, So use a vector array v It is more appropriate to deposit .（v The size is n）

2, Build up trees

There are many ways to build trees , and n Each point can be used as a root node .

Here I use the first node as the root node , Use depth first search to build trees

Because it's calculating dist You need to find the root node before , So we need to 1 An array fa Record your father's label （fa The size is n）

3, Depth-first search

Since there is a list of sons , Then you can search in depth first .

Use depth first , Map the tree to a one-dimensional array , This is a kind of hash .

What's the use of getting this watch ？

I don't know which God man came up with it , Using this table alone, you can get the nearest common ancestor .

such as B The traversal number of is 3,C The traversal number of is 6, from 3 To 6, The depth is 3 2 3 4,

The smallest is 2, The corresponding is A, therefore A Namely B and C The latest public ancestor of .

Be careful , It is not necessarily the only thing to go through , For example, please A and I The latest public ancestor of ,A Yes 3 Different traversal numbers ,

But whichever you choose , The results are the same .

So , Just use dynamic programming RMQ Method to find the minimum value of interval , We can find the common ancestor .

4, spatial analysis

First , We need to save for each point 1 A number of times , Optional 1 Just save one .（visitn The size is n）

then , We also need to save the point corresponding to all traversal numbers .

that , How many times are there in total ？

The rules are obvious , Summarized below ：1 Leaf nodes only have 1 A number of times , The number of iterations per node is equal to the output plus 1

So there is a total of ： Total number of nodes + Total output =n+n-1（visitnum The size is n+n-1）

（mins The size of the first dimension is n+n-1, The second dimension is about log2(n)+1）

above 9 One node has 17 A number of times .

5, Calculate the distance from each point to the root node .

visit Function is a recursively called function , Used to achieve depth first search .

In the process of searching , Except to calculate visitn and visitnum, And count deep and dist（deep The size is n）

（ thus ,7 The purpose and size of the arrays are marked in bold blue ）

deep and dist Can take advantage of recursive parameters d and dis Very convenient to calculate .

6,RMQ

use RMQ What do you want , Don't get this wrong .

RMQ What I'm looking for is visitnum An interval in an array , Have the smallest deep The point corresponding to visitnum

It's not asking deep The minimum value of , It's not asking visitnum The minimum value of .

7,LCA

This and RMQ Corresponding , What I'm looking for is visitnum An interval in an array , Have the smallest deep The point corresponding to visitnum.

Only according to visitnum Then we can know which point is the nearest common ancestor

8, Inquire about

Input x,y, Take their traversal numbers visitn, From this we can find their nearest common ancestor .

It should be noted that , Because there are many ergodic numbers , Take any one and save it to visitn Array ,

that x and y We don't know who is the bigger or smaller traversal number of , You need to determine .

Code ：

#include<iostream>
#include<vector>
using namespace std;

struct node
{
	int son;
	int distance;
};

int n;
vector<node>v[40001];// Save your son's label 
int deep[40001];// The depth of each point 
int visitnum[80001];// The number of passes is 2*n-1
int visitn[40001];// Any number of passes at each point 
int vnum;
int mins[80001][18];		// Interval minimum 
int dist[40001];		// The distance from each point to the ancestor distance
int fa[40001];

void visit(int m, int d, int dis)		// Traverse renumber 、 Calculation distance
{
	vector<node>::iterator p;
	deep[m] = d;
	dist[m] = dis;
	for (p = v[m].begin(); p != v[m].end(); p++)
	{
		if (fa[(*p).son]>-1)continue;
		fa[(*p).son] = m;
		visitnum[vnum++] = m;	// Save the accessed page vnum Which point is it 
		visit((*p).son, d + 1, dis + (*p).distance);
	}
	visitn[m] = vnum;		// Pay attention to this 2 The order of sentences 
	visitnum[vnum++] = m;
}

void rmq()		// Calculate the minimum value of the interval 
{
	for (int i = 1; i <= 2 * n - 1; i++)mins[i][0] = visitnum[i];
	for (int j = 1; (1 << j) <= 2 * n - 1; j++)
	{
		for (int i = 1; i <= 2 * n - 1; i++)
		{
			mins[i][j] = mins[i][j - 1];
			int k = i + (1 << (j - 1));
			if (k <= 2 * n - 1 && deep[mins[i][j]] > deep[mins[k][j - 1]])
				mins[i][j] = mins[k][j - 1];
		}
	}
}

int lca(int x, int y)	// Seek the nearest common ancestor 
{
	x = visitn[x], y = visitn[y];
	if (x > y)x ^= y ^= x ^= y;
	int j = 0;
	while ((1 << j) <= y - x + 1)j++;
	j--;
	int min = mins[y + 1 - (1 << j)][j];
	if (deep[min] > deep[mins[x][j]])min = mins[x][j];
	return min;
}

int main()
{
	int t, m, x, y, l;
	cin >> t;
	while (t--)
	{
		cin >> n >> m;
		vnum = 1;
		for (int i = 1; i <= n; i++)
		{
			v[i].clear();	// initialization 
			fa[i] = -1;
		}
		for (int i = 1; i < n; i++)
		{
			scanf("%d%d%d", &x, &y, &l);
			node nod1, nod2;
			nod1.distance = l, nod1.son = y;
			v[x].insert(v[x].end(), nod1);
			nod2.distance = l, nod2.son = x;
			v[y].insert(v[y].end(), nod2);
		}
		fa[1] = 1;
		visit(1, 1, 0);
		rmq();
		while (m--)
		{
			scanf("%d%d", &x, &y);
			printf("%d\n", dist[x] + dist[y] - dist[lca(x, y)] * 2);
		}
	}
	return 0;
}

CSU 1079 Query on tree （LCA）

subject ：

Description

There is a tree with N A tree at the top , The labels of the vertices are 1, 2, …, N. For each shape such as a b k Of , You need to answer from point a point-to-point b Whether the path of contains points k.

Input

Input contains multiple sets of test data .

For each group of test data , The first line contains two positive integers N, Q (1<=N, Q<=10^5), There are... In this tree N vertices , Next you need to answer Q A asked . Next N-1 In line , The first i Line describes the... Of the tree i side ： Contains two positive integers xi、yi, Indication point xi Sum point yi There is an undirected edge between them . And then there are Q That's ok , Each row contains three positive integers a、b、k (1<=a, b, k<=N), Indicates that you need to answer from point a point-to-point b Whether the path of contains points k.

Output

For each group of test data , You need to answer each question in order . For any query a b k, If you order a point-to-point b The path of contains points k, The output “YES”（ Exclude Quotes ）, Otherwise output “NO”（ Exclude Quotes ）. An empty line is output at the end of each group of data .

Sample Input

3 4
1 2
3 2
2 3 2
2 1 1
1 2 3
1 3 2

Sample Output

YES
YES
NO
YES

Hint

        Because of the large amount of data , Recommended scanf/printf.

Code ：

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;

int n;
vector<int>v[100001];// Save your son's label 
int deep[100001];// The depth of each point 
int visitnum[200001];// The number of passes is 2*n-1
int visitn[100001];// Any number of passes at each point 
int vnum;
int mins[200001][20];		// Interval minimum 
int fa[100001];

void visit(int m, int d)		// Traverse renumber 
{
	vector<int>::iterator p;
	deep[m] = d;
	for (p = v[m].begin(); p != v[m].end(); p++)
	{
		if (fa[*p]>-1)continue;
		fa[*p] = m;
		visitnum[vnum++] = m;	// Save the accessed page vnum Which point is it 
		visit(*p, d + 1);
	}
	visitn[m] = vnum;		// Pay attention to this 2 The order of sentences 
	visitnum[vnum++] = m;
}

void rmq()		// Calculate the minimum value of the interval 
{
	for (int i = 1; i <= 2 * n - 1; i++)mins[i][0] = visitnum[i];
	for (int j = 1; (1 << j) <= 2 * n - 1; j++)
	{
		for (int i = 1; i <= 2 * n - 1; i++)
		{
			mins[i][j] = mins[i][j - 1];
			int k = i + (1 << (j - 1));
			if (k <= 2 * n - 1 && deep[mins[i][j]] > deep[mins[k][j - 1]])
				mins[i][j] = mins[k][j - 1];
		}
	}
}

int lca(int x, int y)	// Seek the nearest common ancestor 
{
	x = visitn[x], y = visitn[y];
	if (x > y)x ^= y ^= x ^= y;
	int j = 0;
	while ((1 << j) <= y - x + 1)j++;
	j--;
	int min = mins[y + 1 - (1 << j)][j];
	if (deep[min] > deep[mins[x][j]])min = mins[x][j];
	return min;
}

int main()
{
	int q, x, y, k;
	bool fl = false;
	while (scanf("%d%d", &n, &q) != EOF)
	{
		if (fl)printf("\n");
		fl = true;
		vnum = 1;
		for (int i = 1; i <= n; i++)
		{
			v[i].clear();	// initialization 
			fa[i] = -1;
		}
		for (int i = 1; i < n; i++)
		{
			scanf("%d%d", &x, &y);
			v[x].insert(v[x].end(), y);// Deposit the son's label 
			v[y].insert(v[y].end(), x);// Deposit the son's label 
		}
		fa[1] = 1;
		visit(1, 1);		
		rmq();
		while (q--)
		{
			scanf("%d%d%d", &x, &y, &k);
			int lca1 = lca(x, y), lca2 = lca(x, k), lca3 = lca(y, k);
			bool flag = (lca1 == lca2 && lca3 == k);
			if (lca1 == lca3 && lca2 == k)flag = true;
			if (flag)printf("YES\n");
			else printf("NO\n");
		}
	}
	return 0;
}