LCA RMQ ST表优化 模板

#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <map>
#include <algorithm>
#include <queue>
#include <set>
#include <cmath>
#include <sstream>
#include <stack>
#include <fstream>
#include <ctime>
#pragma warning(disable:4996);
#define mem(sx,sy) memset(sx,sy,sizeof(sx))
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-8;
const double PI = acos(-1.0);
const ll llINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
using namespace std;
//#define pa pair<int, int>
//const int mod = 1e9 + 7;
const int maxn = 250005;
struct node {
	int u, v, w, next, lca;
};

struct LCA {
	node edges[maxn<<1];
	int head[maxn<<1], cnt1;
	int id[maxn<<1], in[maxn<<1], Dep[maxn<<1], Dist[maxn<<1], cnt2;
	int RMQ[maxn<<1][20];
	void addedge(int u, int v, int w) {
		edges[cnt1].v = v;
		edges[cnt1].w = w;
		edges[cnt1].next = head[u];
		head[u] = cnt1++;
	}

	void init() {
		mem(head, -1);
		cnt1 = 0;
	}

	void DFS(int u, int f, int d, int dis) {
		in[++cnt2] = u;
		Dep[cnt2] = d;
		id[u] = cnt2;
		Dist[u] = dis;
		for (int i = head[u]; i != -1; i = edges[i].next) {
			int v = edges[i].v;
			if (v == f) continue;
			DFS(v, u, d + 1, dis + 1);
			in[++cnt2] = u;
			Dep[cnt2] = d;
		}
	}

	void initRMQ() {
		for (int i = 1; i <= cnt2; i++)
			RMQ[i][0] = i;
		for (int j = 1; (1 << j) <= cnt2; j++) {
			for (int i = 1; i + (1 << j) - 1 <= cnt2; i++) {
				int x = RMQ[i][j - 1];
				int y = RMQ[i + (1 << (j - 1))][j - 1];
				RMQ[i][j] = Dep[x] < Dep[y] ? x : y;
			}
		}
	}

	int getLCA(int a, int b) {
		int k, x, y;
		a = id[a]; b = id[b];
		if (a > b)swap(a, b);
		k = log(1.0 + b - a) / log(2.0);
		x = RMQ[a][k];
		y = RMQ[b - (1 << k) + 1][k];
		return Dep[x] < Dep[y]?in[x] : in[y];
	}

	int getdist(int x, int y) {
		return Dist[x] + Dist[y] - 2 * Dist[getLCA(x, y)];
	}

}L;

struct edge {
	int u, v;
	ll w;
	bool operator<(const edge &e)const { return w>e.w; }
	edge(int _u = 0, int  _v = 0, ll _w = 0)
		:u(_u), v(_v), w(_w) {}
};

struct Kruskal {
	int n, m;
	edge edges[maxn<<1];
	int fa[maxn];
	int Find(int x) {
		return fa[x] == -1 ? x : fa[x] = Find(fa[x]);
	}
	void init(int _n) {
		this->n = _n;
		m = 0;
		mem(fa, -1);
	}

	void AddEdge(int u, int v, ll dist) {
		edges[m++] = edge(u, v, dist);
	}

	ll kruskal() {
		ll sum = 0;
		int cntnum = 0;
		sort(edges, edges + m);
		for (int i = 0; i < m; i++) {
			int u = edges[i].u, v = edges[i].v;
			if (Find(u) != Find(v)) {
				L.addedge(u, v, 1);
				L.addedge(v, u, 1);
				//cout << u << " " << v << endl;
				sum += edges[i].w;
				fa[Find(u)] = Find(v);
				if (++cntnum >= n - 1) return sum;
			}
		}
		return -1;
	}
}G;

int main() {
	int n, m;
	while (~scanf("%d%d", &n, &m)) {
		G.init(n*m);
		L.init();
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				int w1, w2; char c1, c2;
				scanf(" %c%d %c%d", &c1, &w1, &c2, &w2);
				if (c1 == 'D') {
					G.AddEdge((i - 1)*m + j, i*m + j, w1);
				}
				if (c2 == 'R') {
					G.AddEdge((i - 1)*m + j, (i - 1)*m + j + 1, w2);
				}
			}
		}
		G.kruskal();
		L.DFS(1, 0, 0, 0);
		L.initRMQ();
		int q;
		scanf("%d", &q);
		for (int i = 1, x1, x2, y1, y2; i <= q; i++) {
			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
			int u = (x1 - 1)*m + y1;
			int v = (x2 - 1)*m + y2;
			printf("%d\n", L.getdist(u, v));
		}
	}
}