欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LCA RMQ ST表优化 模板

程序员文章站 2024-01-14 16:26:34
...
#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));
		}
	}
}

 

上一篇: json格式总结速记

下一篇: ST表求LCA