根号分治之类的思路分析这里就不讲了，主要关注代码细节：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#define For(i, j, n) for (int i = j; i <= n; ++i)
using namespace std;
const int N = 50005, M = 2e5 + 5;
int n, m, q;
inline int read()
{
int x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
ch = getchar();
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0', ch = getchar();
return x;
}
// 最小生成树 并查集
int fa[N];
inline int find(int x)
{
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
struct StrForEdge
{
int _from, _to, w;
bool operator<(const StrForEdge &_other) const
{
return w < _other.w;
}
} Edge[M * 2];
// 树边需要的一些数据成员
typedef pair<int, int> PII;
vector<PII> tree_edges[N];
// 连边
void on_tree_connect(int a, int b, int w)
{
tree_edges[a].push_back({b, w});
tree_edges[b].push_back({a, w});
}
void init_tree()
{
// 初始化并查集
for (int i = 1; i <= n; i++)
fa[i] = i;
int tree_cnt = 0;
for (int i = 1; i <= m; i++)
{
int a = Edge[i]._from, b = Edge[i]._to;
int pa = find(a), pb = find(b);
if (pa != pb)
{
on_tree_connect(a, b, Edge[i].w);
fa[pa] = pb;
if (++tree_cnt == n - 1)
return;
}
}
}
// 最小生成树
int lca_fa[N][17], maxw[N][17], depth[N];
void dfs_lca(int now, int Father)
{
for (PII edge_on_tree : tree_edges[now])
{
int v = edge_on_tree.first, w = edge_on_tree.second;
if (v == Father)
continue;
depth[v] = depth[now] + 1;
lca_fa[v][0] = now;
maxw[v][0] = w;
for (int i = 1; i <= 16; i++)
{
lca_fa[v][i] = lca_fa[lca_fa[v][i - 1]][i - 1];
maxw[v][i] = max(maxw[v][i - 1], maxw[lca_fa[v][i - 1]][i - 1]);
}
dfs_lca(v, now);
}
}
int link_on_tree(int a, int b)
{
int res = -1;
if (depth[a] < depth[b])
swap(a, b);
int d_of_depth = depth[a] - depth[b];
for (int i = d_of_depth, Base = 0; i > 0; i >>= 1, Base++)
{
if (i & 1)
{
res = max(res, maxw[a][Base]);
a = lca_fa[a][Base];
}
}
if (a == b)
return res;
for (int i = 16; i >= 0; i--)
if (lca_fa[a][i] != lca_fa[b][i])
{
res = max(res, maxw[a][i]);
a = lca_fa[a][i];
res = max(res, maxw[b][i]);
b = lca_fa[b][i];
}
res = max(res, max(maxw[a][0], maxw[b][0]));
return res;
}
void init_lca()
{
// 以一号节点为根
depth[1] = 1;
dfs_lca(1, 0);
}
// 把询问离线，分辨建立线段树
int ans[N];
struct StruForSegTree
{
int l, r, maxx;
} SegTree[N * 4];
// 线段树的元数据
int DisofSegTree[N];
struct StruForQuery
{
int l, r, k, c, id;
bool operator<(const StruForQuery &_other) const
{
if (k != _other.k)
return k < _other.k;
return c < _other.c;
}
} Q[N];
void BuildSegTree(int now, int l, int r)
{
SegTree[now] = {l, r, 0};
if (l == r)
{
SegTree[now].maxx = DisofSegTree[l];
return;
}
int mid = (l + r) >> 1;
int lson = now << 1, rson = now << 1 | 1;
BuildSegTree(lson, l, mid);
BuildSegTree(rson, mid + 1, r);
SegTree[now].maxx = max(SegTree[lson].maxx, SegTree[rson].maxx);
}
void SmallInit(StruForQuery qnow)
{
int L = 0, R = n, DataCnt = 0;
for (int i = L / qnow.k * qnow.k + qnow.c; i + qnow.k <= R; i += qnow.k)
{
if (i < L)
continue;
DisofSegTree[++DataCnt] = link_on_tree(i, i + qnow.k);
}
BuildSegTree(1, 1, DataCnt);
}
int SegTreeQuery(int now, int l, int r)
{
if (SegTree[now].l >= l && SegTree[now].r <= r)
return SegTree[now].maxx;
int mid = (SegTree[now].l + SegTree[now].r) >> 1;
int res = -1;
if (l <= mid)
res = SegTreeQuery(now << 1, l, r);
if (r > mid)
res = max(res, SegTreeQuery(now << 1 | 1, l, r));
return res;
}
int SmallQuery(StruForQuery qnow, bool has_changed)
{
if (has_changed)
SmallInit(qnow);
int L = qnow.l, R = qnow.r;
int k = qnow.k, c = qnow.c;
int _offset = 1 + ((L - c) % k != 0);
int l_to_query = (L - c) / k + _offset;
if (L <= c)
l_to_query = 1;
int r_to_query = (R - c) / k;
return SegTreeQuery(1, l_to_query, r_to_query);
}
int BigQuery(StruForQuery qnow)
{
int L = qnow.l, R = qnow.r, ans = -1;
for (int i = L / qnow.k * qnow.k + qnow.c; i + qnow.k <= R; i += qnow.k)
{
if (i < L)
continue;
ans = max(ans, link_on_tree(i, i + qnow.k));
}
return ans;
}
int main()
{
n = read();
m = read();
q = read();
int tmpa, tmpb, tmpc;
for (int i = 1; i <= m; i++)
{
tmpa = read();
tmpb = read();
tmpc = read();
Edge[i] = {tmpa, tmpb, tmpc};
}
sort(Edge + 1, Edge + m + 1);
init_tree();
init_lca();
int ql, qr, qk, qc;
int Threshold = min(n / 3, 110);
for (int i = 1; i <= q; i++)
{
ql = read();
qr = read();
qk = read();
qc = read();
Q[i] = {ql, qr, qk, qc, i};
}
sort(Q + 1, Q + q + 1);
int know = 0, kc = 0;
for (int i = 1; i <= q; i++)
{
if (Q[i].k > Threshold)
{
ans[Q[i].id] = BigQuery(Q[i]);
continue;
}
bool has_changed = false;
if (know != Q[i].k)
know = Q[i].k, has_changed = true;
if (kc != Q[i].c)
kc = Q[i].c, has_changed = true;
ans[Q[i].id] = SmallQuery(Q[i], has_changed);
}
for (int i = 1; i <= q; i++)
printf("%d\n", ans[i]);
return 0;
}
为什么一开始会超时：
确实，通过重定义小于运算符来对查询进行排序，理论上会将具有相同`k`和`c`值的查询放在一起。这是因为你的排序策略首先考虑`k`的值，然后是`c`的值。这样做的目的是为了将具有相同参数的查询分组，以便可以一次性处理这些查询，减少重复的初始化操作。你提供的代码片段是：
```cpp
bool operator < (const StruForQuery &_other)const
{
return k < _other.k;
if(k == _other.k)
return c < _other.c;
}
```
然而，上面的重载`operator<`实际上有一个逻辑错误。如果`k < _other.k`为`true`，那么比较就在这里结束，这是正确的。但是，如果`k == _other.k`，那么你希望进一步比较`c`的值。然而，由于`return k < _other.k;`这行代码的存在，当`k`等于`_other.k`时，函数就会结束，后面的`if(k == _other.k)`永远不会执行。
正确的写法应该是：
```cpp
bool operator < (const StruForQuery &_other)const
{
if(k != _other.k) return k < _other.k;
return c < _other.c;
}
```
或者更简洁的形式：
```cpp
bool operator < (const StruForQuery &_other)const
{
return k == _other.k ? c < _other.c : k < _other.k;
}
```
这样就可以确保当`k`相等时，会根据`c`的值进行排序，确保具有相同`k`和`c`的查询会被放在一起。
如果你在实现中已经正确地排序了查询，那么每次遇到不同的`(k, c)`组合时确实应该只初始化一次。如果出现重复初始化的情况，可能需要进一步检查逻辑，确认是不是每个组合确实只处理了一次，或者是不是排序后的查询确实如你所期望的那样正确分组。此外，确认`SmallInit`调用和相关处理是否被正确地限制在每个独特的`(k, c)`组合上。
总之，正确实现和应用排序逻辑是关键，这将确保查询按照期望的方式被组织和处理，从而避免不必要的重复操作。
关键就在于直接return了，如果k!=_other.k，那么就会直接return false，但是后面有关c的判断并不会被执行。
标签：return,int,res,蓝桥,other,lca,2015,const,P8626 From： https://www.cnblogs.com/smartljy/p/18081730