admin 管理员组文章数量: 1184232
本文涉及知识点
C++并集查找
重构树
P9638 「yyOI R1」youyou 的军训
题目背景
在 youyou 的班上，身高可能是一个敏感的话题。
题目描述
youyou 的班上一共有 n n n 位同学， m m m 对朋友，第 i i i 对朋友关系对于身高有一个敏感值 k i k_i ki，敏感值可能会改变。
我们定义两位同学如果互为朋友，那么必然存在某对关系，将两位同学直接相连。
我们定义两位同学如果互为好友，那么必然存在直接或间接的关系，将两位同学相连。
例如存在关系 ( 1 , 2 ) (1,2) (1,2) 和 ( 2 , 3 ) (2,3) (2,3)，那么， 1 1 1 与 2 2 2 是朋友，但 1 1 1 与 3 3 3 就是好友。
现在，马上就要军训了，同学们要去领军训的服装，如果一位同学领到了尺码为 p p p 的服装，所有同学会与朋友关系敏感值小于 p p p 的朋友断交。即对于所有的朋友关系，若其敏感值小于 p p p，那么该朋友关系就会断开。不过在下一位同学领到服装时，所有之前的断开的朋友关系会恢复。
由于军训领服装是一个复杂的过程，而 youyou 对此十分感兴趣，所以给出 q q q 次操作，且一共有三种操作:
-
操作 1 1 1，形如
1 x，表示有一位同学领到尺码为 x x x 的服装。 -
操作 2 2 2，形如
2 x，表示询问第 x x x 位同学还有多少位好友（包括自己）。 -
操作 3 3 3，形如
3 x y，表示第 x x x 对朋友的敏感值变为 y y y，特别地，敏感值的相对大小不会变化 ∗ ^* ∗（详情见下方），同时原来已经断开的关系不会恢复。
注意：好友跟朋友是两个概念，朋友一定是好友，但好友不一定是朋友。
∗ ^* ∗：相对大小不会变化，指对于当前所有的敏感值而言，修改后的敏感值与原来的敏感值排名相同。
例如，若原来所有对朋友之间敏感值是 { 1 , 2 , 3 , 5 , 6 } \{1,2,3,5,6\} {1,2,3,5,6}， 3 3 3 的排名为 3 3 3，因此 3 3 3 只能修改为 3 , 4 3,4 3,4 中的一个，这样才能保证排名不变，即相对大小位置不会变换。
输入格式
第一行，输入三个正整数 n , m , q n,m,q n,m,q。
后面 m m m 行，给定 m m m 对朋友关系，对于第 i i i 行给定三个正整数 x i , y i , k i x_i,y_i,k_i xi,yi,ki。
最后 q q q 行，给定 q q q 次操作。对于每次操作，给定一个正整数为 o p op op，即操作类型。
当 o p = 1 op=1 op=1 时，再给定一个正整数 x x x，表示有一位同学领到尺码为 x x x 的服装；
当 o p = 2 op=2 op=2 时，再给定一个正整数 x x x，表示一次询问；
当 o p = 3 op=3 op=3 时，再给定两个正整数 x , y x,y x,y，表示一次修改。
输出格式
对于每次询问操作，输出一个 x x x 表示询问的同学还有几位好友（包括自己）。保证对于每一个测试点，都会有一个询问操作。
输入输出样例 #1
输入 #1
4 3 3
1 2 156
1 4 42
2 3 0
1 26963
3 3 40
2 4
输出 #1
1
输入输出样例 #2
输入 #2
7 6 7
1 2 292
1 3 274
1 4 221
1 5 156
3 4 42
3 6 40
1 30
3 4 50
2 6
3 3 250
3 1 298
1 280
2 1
输出 #2
6
2
说明/提示
样例解释 #1
如图所示，这是初始的关系图。
第一次操作为：有一位同学领到尺码为 26963 26963 26963 的服装，这样，图中所有的边都会断开。
下一次操作：第三对朋友即边 ( 2 , 3 ) (2,3) (2,3) 的权变为 40 40 40。
下一次操作：询问同学 4 4 4 的好友数量，因为没有任何存在的边，因此答案为 1 1 1。
数据范围
| 测试点编号 | n n n | q q q | 特殊性质 |
|---|---|---|---|
| 1 , 2 1,2 1,2 | ≤ 10 \le 10 ≤10 | ≤ 4 × 10 5 \le 4 \times 10^5 ≤4×105 | 无 |
| 3 3 3 | ≤ 10 3 \le 10^3 ≤103 | ≤ 10 3 \le 10^3 ≤103 | 无 |
| 4 4 4 | ≤ 10 5 \le 10^5 ≤105 | ≤ 4 × 10 5 \le 4 \times 10^5 ≤4×105 | 没有操作 3 3 3 |
| 5 , 6 5,6 5,6 | ≤ 10 5 \le 10^5 ≤105 | ≤ 10 3 \le 10^3 ≤103 | 无 |
| 7 7 7 | ≤ 10 5 \le 10^5 ≤105 | ≤ 4 × 10 5 \le 4 \times 10^5 ≤4×105 | 没有操作 1 1 1 |
| 8 , 9 , 10 8,9,10 8,9,10 | ≤ 4 × 10 5 \le 4 \times 10^5 ≤4×105 | ≤ 4 × 10 5 \le 4 \times 10^5 ≤4×105 | 无 |
用 c i c_i ci 表示询问中同学领到服装尺码的大小， e i e_i ei 表示修改后敏感值的大小。
对于 100 % 100\% 100% 的数据， 1 ≤ n , m , q , x i , y i ≤ 4 × 10 5 1 \le n,m,q,x_i,y_i \le 4 \times 10^5 1≤n,m,q,xi,yi≤4×105， 1 ≤ k i , c i , e i ≤ 1 × 10 9 1 \le k_i,c_i,e_i \le 1 \times 10^9 1≤ki,ci,ei≤1×109， m ≤ min { n ( n − 1 ) 2 , 4 × 10 5 } m\le \min\{\frac{n(n-1)}{2},4 \times 10^5\} m≤min{2n(n−1),4×105}。
同时数据保证在任何时刻，所有对朋友关系之间的敏感值互不相同。
请注意常数因子对时间和空间产生的影响。
重构树
边权从大到小建树。
m_iMin记录最后一个同学领取的服装。初始:0。
操作二：查询x 的最远祖先g，点权
≥
\ge
≥m_iMin ，g子树真实节点的数量。
操作三：如果是有效边，修改对应节点的边权。
注意：敏感值的相对大小不变，即重构树的形态不变，即无需重新建树。
代码
核心代码
#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>
#include <bitset>
using namespace std;
template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {
in >> pr.first >> pr.second;
return in;
}
template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {
in >> get<0>(t) >> get<1>(t) >> get<2>(t);
return in;
}
template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {
in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
return in;
}
template<class T = int>
vector<T> Read() {
int n;
cin >> n;
vector<T> ret(n);
for (int i = 0; i < n; i++) {
cin >> ret[i];
}
return ret;
}
template<class T = int>
vector<T> ReadNotNum() {
vector<T> ret;
T tmp;
while (cin >> tmp) {
ret.emplace_back(tmp);
if ('\n' == cin.get()) { break; }
}
return ret;
}
template<class T = int>
vector<T> Read(int n) {
vector<T> ret(n);
for (int i = 0; i < n; i++) {
cin >> ret[i];
}
return ret;
}
template<int N = 1'000'000>
class COutBuff
{
public:
COutBuff() {
m_p = puffer;
}
template<class T>
void write(T x) {
int num[28], sp = 0;
if (x < 0)
*m_p++ = '-', x = -x;
if (!x)
*m_p++ = 48;
while (x)
num[++sp] = x % 10, x /= 10;
while (sp)
*m_p++ = num[sp--] + 48;
AuotToFile();
}
void writestr(const char* sz) {
strcpy(m_p, sz);
m_p += strlen(sz);
AuotToFile();
}
inline void write(char ch)
{
*m_p++ = ch;
AuotToFile();
}
inline void ToFile() {
fwrite(puffer, 1, m_p - puffer, stdout);
m_p = puffer;
}
~COutBuff() {
ToFile();
}
private:
inline void AuotToFile() {
if (m_p - puffer > N - 100) {
ToFile();
}
}
char puffer[N], * m_p;
};
template<int N = 1'000'000>
class CInBuff
{
public:
inline CInBuff() {}
inline CInBuff<N>& operator>>(char& ch) {
FileToBuf();
ch = *S++;
return *this;
}
inline CInBuff<N>& operator>>(int& val) {
FileToBuf();
int x(0), f(0);
while (!isdigit(*S))
f |= (*S++ == '-');
while (isdigit(*S))
x = (x << 1) + (x << 3) + (*S++ ^ 48);
val = f ? -x : x; S++;//忽略空格换行
return *this;
}
inline CInBuff& operator>>(long long& val) {
FileToBuf();
long long x(0); int f(0);
while (!isdigit(*S))
f |= (*S++ == '-');
while (isdigit(*S))
x = (x << 1) + (x << 3) + (*S++ ^ 48);
val = f ? -x : x; S++;//忽略空格换行
return *this;
}
template<class T1, class T2>
inline CInBuff& operator>>(pair<T1, T2>& val) {
*this >> val.first >> val.second;
return *this;
}
template<class T1, class T2, class T3>
inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {
*this >> get<0>(val) >> get<1>(val) >> get<2>(val);
return *this;
}
template<class T1, class T2, class T3, class T4>
inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {
*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);
return *this;
}
template<class T = int>
inline CInBuff& operator>>(vector<T>& val) {
int n;
*this >> n;
val.resize(n);
for (int i = 0; i < n; i++) {
*this >> val[i];
}
return *this;
}
template<class T = int>
vector<T> Read(int n) {
vector<T> ret(n);
for (int i = 0; i < n; i++) {
*this >> ret[i];
}
return ret;
}
template<class T = int>
vector<T> Read() {
vector<T> ret;
*this >> ret;
return ret;
}
private:
inline void FileToBuf() {
const int canRead = m_iWritePos - (S - buffer);
if (canRead >= 100) { return; }
if (m_bFinish) { return; }
for (int i = 0; i < canRead; i++)
{
buffer[i] = S[i];//memcpy出错
}
m_iWritePos = canRead;
buffer[m_iWritePos] = 0;
S = buffer;
int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);
if (readCnt <= 0) { m_bFinish = true; return; }
m_iWritePos += readCnt;
buffer[m_iWritePos] = 0;
S = buffer;
}
int m_iWritePos = 0; bool m_bFinish = false;
char buffer[N + 10], * S = buffer;
};
class CUnionFind
{
public:
CUnionFind(int iSize) :m_vNodeToRegion(iSize)
{
for (int i = 0; i < iSize; i++)
{
m_vNodeToRegion[i] = i;
}
m_iConnetRegionCount = iSize;
}
CUnionFind(vector<vector<int>>& vNeiBo) :CUnionFind(vNeiBo.size())
{
for (int i = 0; i < vNeiBo.size(); i++) {
for (const auto& n : vNeiBo[i]) {
Union(i, n);
}
}
}
int GetConnectRegionIndex(int iNode)
{
int& iConnectNO = m_vNodeToRegion[iNode];
if (iNode == iConnectNO)
{
return iNode;
}
return iConnectNO = GetConnectRegionIndex(iConnectNO);
}
void Union(int iNode1, int iNode2)
{
const int iConnectNO1 = GetConnectRegionIndex(iNode1);
const int iConnectNO2 = GetConnectRegionIndex(iNode2);
if (iConnectNO1 == iConnectNO2)
{
return;
}
m_iConnetRegionCount--;
if (iConnectNO1 > iConnectNO2)
{
m_vNodeToRegion[iConnectNO1] = iConnectNO2;
}
else
{
m_vNodeToRegion[iConnectNO2] = iConnectNO1;
}
}
bool IsConnect(int iNode1, int iNode2)
{
return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
}
int GetConnetRegionCount()const
{
return m_iConnetRegionCount;
}
//vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
//{
// const int iNodeSize = m_vNodeToRegion.size();
// vector<int> vRet(iNodeSize);
// for (int i = 0; i < iNodeSize; i++)
// {
// vRet[GetConnectRegionIndex(i)]++;
// }
// return vRet;
//}
std::unordered_map<int, vector<int>> GetNodeOfRegion()
{
std::unordered_map<int, vector<int>> ret;
const int iNodeSize = m_vNodeToRegion.size();
for (int i = 0; i < iNodeSize; i++)
{
ret[GetConnectRegionIndex(i)].emplace_back(i);
}
return ret;
}
private:
vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
int m_iConnetRegionCount;
};
class CParents
{
public:
CParents(vector<int>& vParent, long long iMaxDepth)
{
int iBitNum = 0;
for (; iMaxDepth; iBitNum++) {
const auto mask = 1LL << iBitNum;
if (mask & iMaxDepth) { iMaxDepth = iMaxDepth ^ mask; }
}
const int n = vParent.size();
m_vParents.assign(iBitNum + 1, vector<int>(n, -1));
m_vParents[0] = vParent;
//树上倍增
for (int i = 1; i < m_vParents.size(); i++)
{
for (int j = 0; j < n; j++)
{
const int iPre = m_vParents[i - 1][j];
if (-1 != iPre)
{
m_vParents[i][j] = m_vParents[i - 1][iPre];
}
}
}
}
int GetParent(int iNode, int iDepth)const
{
int iParent = iNode;
for (int iBit = 0; iBit < m_vParents.size(); iBit++)
{
if (-1 == iParent)
{
return iParent;
}
if (iDepth & (1 << iBit))
{
iParent = m_vParents[iBit][iParent];
}
}
return iParent;
}
int GetLeve(int node)const {
int leve = 0;
for (int i = m_vParents.size() - 1; i >= 0; i--) {
if (-1 == m_vParents[i][node]) { continue; }
node = m_vParents[i][node];
leve += (1 << i);
}
return leve;
}
inline int GetBitCnt()const { return m_vParents.size(); };
inline const int& GetPow2Parent(int iNode, int n)const {
return m_vParents[n][iNode];
}
//在leftNodeExclude的1到rightLeve级祖先中查找符合pr的最近祖先
template<class _Pr>
int FindFirst(int leftNodeExclude, int rightLeve, _Pr pr) {
for (int iBit = GetBitCnt() - 1; iBit >= 0; iBit--) {
const int iMask = 1 << iBit;
if (!(iMask & rightLeve)) { continue; }
if (pr(m_vParents[iBit][leftNodeExclude])) {
return BFindFirst(leftNodeExclude, iBit, pr);
}
leftNodeExclude = m_vParents[iBit][leftNodeExclude];
}
return -1;
}
//在node的0到rightLeve级祖先中查找符合pr的最远祖先比node高多少层次,这些层次必须存在
template<class _Pr>
int FindEnd(int node, int rightLeve, _Pr pr) {
int leve = 0;
for (int iBit = GetBitCnt() - 1; iBit >= 0; iBit--) {
const int iMask = 1 << iBit;
if (!(iMask & rightLeve)) { continue; }
if (!pr(m_vParents[iBit][node])) {
return leve + BFindEnd(node, iBit, pr);
}
node = m_vParents[iBit][node];
leve = leve ^ iMask;
}
return leve;
}
protected:
//在leftNodeExclude的1到2^pow^级祖先中查找符合pr的最近祖先
template<class _Pr>
int BFindFirst(int leftNodeExclude, int pow, _Pr pr) {
while (pow > 0) {
const int& mid = m_vParents[pow - 1][leftNodeExclude];
if (pr(mid)) {
}
else {
leftNodeExclude = mid;
}
pow--;
}
return m_vParents[0][leftNodeExclude];
}
//在node的[0,2^pow^-1]级祖先中寻找符合的最后一个
template<class _Pr>
int BFindEnd(int node, int pow, _Pr pr) {
int leve = 0;
while (pow > 0) {
pow--;
const int& mid = m_vParents[pow][node];
if (pr(mid)) {
node = mid;
leve = leve ^ (1 << pow);
}
else {
}
}
return leve;
}
vector<vector<int>> m_vParents;
};
template<class WT = int, class _Pr = greater<int> >
class CReconstructionTree
{
public:
CReconstructionTree(const int N, const vector<tuple<int, int, WT>>& edge,WT defaultW): m_weight(2*N-1, defaultW), m_actNodeCnt(2*N-1,1){
m_vEdgeToPoint.assign(edge.size(), -1);
vector<int> vRoot(N), vPar(2*N-1,-1),inxs(edge.size());
iota(vRoot.begin(), vRoot.end(), 0);
iota(inxs.begin(), inxs.end(), 0);
sort(inxs.begin(), inxs.end(), [&](const int& i1, const int& i2) { return _Pr()(get<2>(edge[i1]), get<2>(edge[i2])); });
int cnt = 0;
CUnionFind uf(N);
for (int inx : inxs) {
auto& [u, v, w] = edge[inx];
const int g1 = uf.GetConnectRegionIndex(u);
const int g2 = uf.GetConnectRegionIndex(v);
if (g1 == g2) { continue; }
vPar[vRoot[g1]] = vPar[vRoot[g2]] = N + cnt;
m_actNodeCnt[N + cnt] = m_actNodeCnt[vRoot[g1]] + m_actNodeCnt[vRoot[g2]];
uf.Union(u, v);
const int g = uf.GetConnectRegionIndex(u);
vRoot[g] = N + cnt;
m_weight[N + cnt] = w;
m_vEdgeToPoint[inx] = N + cnt;
cnt++;
}
m_mp = new CParents(vPar, 2*N - 1);
}
int GetRegionSize(int node, WT w) {
auto Check = [&](int node) {return _Pr()(m_weight[node], w) || (m_weight[node] == w); };
int leve = m_mp->FindEnd(node, m_mp->GetLeve(node), Check);
int gp = m_mp->GetParent(node, leve);
return m_actNodeCnt[gp];
};
void ChangeWeight(int edge, int w) {
const int pt = m_vEdgeToPoint[edge];
if (-1 == pt) { return; }//此边被忽略
m_weight[pt] = w; //边权的相对大小不能变，否则需要重新建立树
}
protected:
vector<WT> m_weight;
CParents* m_mp;
vector<int> m_actNodeCnt,m_vEdgeToPoint;
};
class Solution {
public:
vector<int> Ans(const int N, vector<tuple<int, int,int>>& edge, vector<tuple<int, int, int>>& ope) {
for (auto& [u, v, w] : edge) { u--, v--; }
CReconstructionTree<> rt(N, edge, INT_MAX / 2);
int iMin = 0;
vector<int> ans;
vector<pair<int, int>> newEdge;
for (auto [kind, x, y] : ope) {
if (1 != kind) { x--; };
if (1 == kind) {
iMin = x;
for (const auto& [x, y] : newEdge) {
rt.ChangeWeight(x, y);
}
newEdge.clear();
}
else if (2 == kind) {
ans.emplace_back(rt.GetRegionSize(x,iMin));
}
else if (3 == kind) {
newEdge.emplace_back(x, y);
}
}
return ans;
}
};
int main() {
#ifdef _DEBUG
freopen("a.in", "r", stdin);
#endif // DEBUG
ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
int N, M, Q;
cin >> N >> M >> Q;
auto edge = Read<tuple<int, int, int>>(M);
vector< tuple<int, int, int>> ope;
int kind, x, y;
for (int i = 0; i < Q; i++) {
cin >> kind >> x;
if (3 == kind) {
cin >> y;
}
else {
y = 0;
}
ope.emplace_back(kind, x, y);
}
#ifdef _DEBUG
printf("N=%d", N);
//Out(xy, ",xy=");
Out(edge, ",edge=");
Out(ope, ",ope=");
#endif // DEBUG
auto res = Solution().Ans(N,edge,ope);
for (const auto& i : res) {
cout << i << "\n";
}
return 0;
}
单元测试
int N, M;
vector<tuple<int, int, int>> edge, ope;
TEST_METHOD(TestMethod11)
{
N = 4, edge = { {1,2,156},{1,4,42},{2,3,0} }, ope = { {1,26963,0},{3,3,40},{2,4,0} };
auto res = Solution().Ans(N, edge,ope);
AssertV({ 1 }, res);
}
TEST_METHOD(TestMethod12)
{
N = 7, edge = { {1,2,292},{1,3,274},{1,4,221},{1,5,156},{3,4,42},{3,6,40} }, ope = { {1,30,0},{3,4,50},{2,6,0},{3,3,250},{3,1,298},{1,280,0},{2,1,0} };
auto res = Solution().Ans(N, edge, ope);
AssertV({ 6,2 }, res);
}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 员工说：技术至上，老板不信；投资人的代表说：技术至上，老板会信。 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
版权声明：本文标题：【重构树】P9638 「yyOI R1」youyou 的军训|省选- 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1765987674a3429767.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论