数学（九） (5-3)

{

for (int k = 0; k ＜= x; k++)

{

if (dp[j][k] ＜= y)

ans = std::max(ans, j + 1);

}

}

std::cout＜＜ans＜＜'\n';

return 0;

}

F - Range Connect MST

赛时没仔细想盲猜线段树优化建图然后就一直冲E 去了，打完一看直接升温

可以将图分成两个部分一边是1 ∼ N，另一边是 N＋1 ∼ N＋Q，操作完第二个部分所有节点一定会连到第一个部分，代价是 ∑Gᵢ，然后只要考虑第一个部分

每次操作会有[Lᵢ，Rᵢ] 中所有点和点 N＋i 连接，总共 Rᵢ – Lᵢ＋1 条边，相当于 [Lᵢ，Rᵢ] 中的点连成链，然后 N＋i 连到这个区间（怎么连不重要），我们只需要暴力把 x 连接到 x＋1(x＜Rᵢ) 如果 [Lᵢ，Rᵢ] 内某个区间

已经相连，直接跳过这个区间，这个操作用并查集很容易实现，根据上面连接方式，每个点的祖先一定大于或者等于它，最后只要判断 1 的祖先是不是 N 判断是否连通

至于最小生成树问题，存下每次询问然后排序

struct DSU

{

int n;

std::vector＜int＞ fa, size;

DSU(int n) : n(n), fa(n + 1), size(n + 1, 1) { std::iota(fa.begin(), fa.end(), 0); }

int find(int x)

{

if (x != fa[x])

{

fa[x] = find(fa[x]);

}

return fa[x];

}

void merge(int x, int y) // x -＞ y

{

x = find(x), y = find(y);

if (x == y)

return;

// if (size[x]＞size[y])

// std::swap(x, y);

fa[x] = y, size[y] += size[x];

}

bool same(int x, int y)

{

return find(x) == find(y);

}

};

int main()

{

std::ios::sync_with_stdio(false);

std::cin.tie(0);

int n, q;

std::cin＞＞n＞＞q;

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。