树形问题选讲

Treap_Kongzs · 2024-07-24 00:27:54 · 算法·理论

省流：本篇专供冲击NOIP一等的人使用，坐标HN

博客同步

1.ST表&&倍增法求LCA

一对好兄弟。

1.1 ST表

ST表是一种数据结构，不带修（悲），可以处理满足可加性与可重复贡献两条性质的区间信息

• 区间最值（大/小）

• 位运算（按位与/或/非/异或）

• 区间\gcd or \operatorname{lcm}

而且码量小（小到我还是背不下来（悲）），效率高

一般来说，ST表的预处理为O(n\log n)，查询直接一个O(1)震惊百万OIer，太快了。

我们就开始学习吧！！！

首先我们要知道一个常识，如何求对数……？

先把这道题切了，并且欣赏一下我和工程大佬抢最优解的搞笑过程（？）

然后，万事开头难，我们先建个额外的ST[maxn]数组，开始啦！！

然后，我们思考如何做到这么优秀的复杂度。

一般来说，给的数据都是一维的，我们的常规思维是加点维度，让空间承担更多可以提前确定的答案，以减少单次查询的运算。那我们怎么加呢？

诶，这个时候我们就要用到一种叫倍增的思想了

朴素的查找肯定是一个个查，但是倍增就不一样了，一个不行，跳一个再找，还不对，跳两个，还不对，跳四个……还不对？！跳八个！！！（逼急了属于是，OIer做题实录）

所以一个个查肯定是查了O(n)次，而倍增可以只查O(\log_{2}n)次，good

很好的算法，使你不知道怎样用它减小查询次数

那我们就可以考虑拓展ST，把它的大小拓展[maxn][\log_2 maxn]

它的第一维代表起点，第二维代表倍增查找的指数，合起来，就表示起点为i，长度为2^j这段区间的答案。

哦，真就这么简单吗？

啊，是的（

接下来就是激动人心的初始化时间了。

因为2^0=1，所以我们可以直接把原数据塞进ST[i][0]里，以i为起点，长度为2^0=1嘛

然后，我们怎么把数据填满整个表呢？

来，在纸上画一条较长的线段，把左端点涂的明显些，这就代表一个长度为2^j的区间，左端点为i。

然后再复习一个初中知识：

所以最开始的区间显然可以分为两个区间：[i,i+2^{j-1}]和[i+2^{j-1}+1,i+2^{j-1}+2^{j-1}]，我们[i,i+2^{j}]的答案就从这两个子区间转移上来，比如说最大值，答案就是两个子区间答案的最大值。

由于我们要填满整个表，填一次O(1)，所以时间就是O(n\log n)，为表的大小，\therefore 这也是空间复杂度。

好，那接下来怎么查询呢？给定区间[l,r]，我们怎么O(1)搞定答案呢？

首先，由于ST表的答案存储依赖长度，我们先把区间长度len=r-l+1搞到手。然后设k=\log_2len，方便查表，没问题吧。

接下来就是重量级：

其中ans()为你要求的数据的处理函数。

为什么这样可以呢？，首先，你需要读懂那个位运算，这里不做解释。我们从这个区间中的两个地方跳了2^k长度，总长度就是2^{log_2len}=len，长度是没问题的，不会遗漏。

但是，怎么保证l+2^k一定等于r-2^k呢，证明就不放了。不要慌，因为这两个值不需要相等，它们代表的是两个区间的端点，只要两个区间有交集，结果就不会错，这就是可重复贡献的好处，你可以拿最大值的例子套一套。

同样的，区间和这种东西就无法用ST表维护，因为它不能遗漏，也不能有交集，我们在ST表中不关心交集的大小，但在区间和中，被加两次是相当令人头疼的。

因为查询可以直接差分，所以就是O(1)的！

好了，讲完了，接下来把模板题切了吧！

习题1.1.1

P3865 【模板】ST表 && RMQ问题

注意，在O(n\log n)的循环中，我们外循环是枚举长度指数，内循环则是枚举起点，和数组定义是反过来的（当然，你可以试着把数组反过来定义，可能没这么多问题，但我没试过）而且终止条件是i+2^j-1\le n，终止条件是显然的，因为你不能越界。

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
const int log2maxn=25;
#define endl '\n'

int st[maxn][log2maxn];//第一维为数组个数，第二维为数组个数的倍增指数
int logs[maxn];

inline int query(int l,int r)
{
    int k=logs[r-l+1];

    return max(st[l][k],st[r-(1<<k)+1][k]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n=0,m=0,l=0,r=0;
    cin>>n>>m;
    logs[1]=0;
    for(int i=2;i<=n;i++)
    {
        logs[i]=logs[i>>1]+1;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>st[i][0];
    }
    //预处理
    for(int j=1;j<=logs[n];j++)//先枚举区间长度指数
    {
        for(int i=1;i<=n-(1<<j)+1;i++)//再枚举区间起点
        {
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
    }
    for(int i=1;i<=m;i++)
    {
        cin>>l>>r;
        cout<<query(l,r);
        if(i<m)cout<<endl;
    }
    return 0;
}

好了，学会了这个有用但不是很有用的数据结构，我们来看它的一个重要应用。

1.2 倍增法求LCA

本文不涉及tarjan法，因为€€￡的官方教材上估计是觉得CSP 2022 T3级别的数据tarjan都过不去，所以写了一句“实际中几乎完全被取代”。难绷。

LCA是最近公共祖先的英文缩写（废话），指的是树中的两个节点的最近的（距离最小的）公共祖先。比如说，你和你的兄弟姐妹的LCA肯定是爸爸妈妈，但是别的情况我们不涉及（

特别的，如果两个点本身就是一条脉上的，即某个点是另外一个点的祖先，我们规定这两个点的LCA为深度最小的那个点，这跟\gcd(2,4)=2，\operatorname{lcm}(2,4)=4是一个道理。

好，那怎么求出同一棵树上任两个节点的LCA呢？

一个暴力的想法马上就可以写出来，用两个变量当“指针”，指着这两个点，然后依次跳到它们的父亲，一直到这两个指针指到相同节点为止。这个相同节点就是所求的LCA。

由于我们需要一直往上跳，遍历的节点很多，对于n个结点的树进行q次询问的话，暴力做法的复杂度达到了O(nq)，很多题目都无法承受。

那么有什么优化的方法吗？答案是肯定的，我给你在上面暴力流程中画一下关键词：

依次跳到它们的父亲

看到了吧，跟我们之前讲的“一个个查”很类似，那我们也可以异想天开，看看这种树上查询能不能用ST表搞定。

这一回，我们的ST表有实际意义了。对于每个st[i][j]，它表示：从节点i向上跳2^j层所到达的节点。我们这里做个约定，由于储存内容是下表的父亲，我们把st暂时改名叫fa，之前写ST表的对数表用来给节点储存深度，改叫dep。其余不变。

首先搞定fa的初始化，由于这不是线性结构的问题了，我们在树上的预处理受到树节点连边的限制。所以，我们把预处理放进树的dfs()

我们首先把传入节点的dep初始化为它父亲的+1，然后，它往上跳一层便是它的父亲，所以把fa[传入节点][0]初始化为它的父亲节点编号。

接下来，我们一直往上跳，直到跳到深度限制（对，就是这么夸张），但是我们肯定不能一个一个跳，我们是枚举指数，就像初始化ST表那样。那么，我们怎么做呢？fa[x][i]有什么规律呢？

我们再回到那个初中等式：

有没有什么启发？直接看这个式子显然没有。

但是呢，我们可以将“从起点i跳2^j层”这个过程分成两步，先从i跳2^{j-1}层，再从新起点跳2^{j-1}层。这样，我们就跳了2\times 2^{j-1}=2^{j}层。成功把这个过程等价了。

如果你还没什么感触的话，你应该想到一个式子：

其中，u是最开始的节点。

这下就明白怎么向上更新了吧？但是……请问我们到现在为止，干的事情……跟dfs()有什么关系？

好吧，为了在形式上更像dfs()，我们来考虑一下转移问题。

……还能怎么转移？考虑完了自己的爹，肯定要考虑自己的子孙后代的爹了！（无隐喻）

我们就遍历传入节点的子孙，但是如果你加的是双向边的话，那你就很麻烦，因为搞不好判儿子的时候会指父为子，哦，不敢想象……

我们就判定，对于点i的某条边，如果它指向的不是父亲节点，就以这条边的另一个端点作为传入节点，它的父亲节点就是i。顺便说一句，父亲节点也是在dfs()的形参列表里传进去的。

好，这样我们就完成了每个点的初始化，n个点跳了\log_2 n的高度，总时间复杂度为O(n\log_2 n)，刚好和ST表的预处理一致。

接下来查询，也没什么别的，就是让dep大的那个点一路往上跳，这里的跳是fa[u][i]。然后当两个点dep一致的时候，就一起跳，只是它们俩的跳这下可以基于ST表（fa），越跳越高，乐。当跳到两个节点的fa相同时，就不跳了。

然后，我们返回其中一个节点的fa[u][0]，既然它们的父亲相同了，那再跳一步就到了嘛。

如果第一阶段的单独跳结束后，两个指针刚好重合，那就说明它们在一条脉上，由于已经跳完了，这时返回任意一个节点都可以。记得在一起跳之前判掉。

这样做，你需要O(n\log_2 n)的预处理，q次查询，每次最多查\log_2 n个点，那么查询就是O(q\log_2 n)，总的就是O((n+q)\log_2 n)可能会超时，但是对于我们的目标要求已经够用了

好了，模板题来袭！！！

习题1.2.1

P3379 【模板】最近公共祖先（LCA）

本题用了邻接表存树，你用链式前向星也可以。

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7;
const int log2maxn=25;
#define endl '\n'

vector<int> tree[maxn];
int fa[maxn][30];
int dep[maxn];

inline void adde(int u,int v)
{
    tree[u].push_back(v);
}

void dfs(int u,int father)
{
    dep[u]=dep[father]+1;
    fa[u][0]=father;
    for(int i=1;i<=log2maxn;i++)
    {
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int i=0;i<tree[u].size();i++)
    {
        if(tree[u][i]!=father)dfs(tree[u][i],u);
    }
}

int lca(int u,int v)
{
    if(dep[u]<dep[v])
    {
        swap(u,v);
    }
    for(int i=log2maxn;i>=0;i--)
    {
        if(dep[fa[u][i]]>=dep[v])
        {
            u=fa[u][i];
        }
    }
    if(u==v)return v;
    for(int i=log2maxn;i>=0;i--)
    {
        if(fa[u][i]!=fa[v][i])
        {
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n=0,m=0,root=0,u=0,v=0,l=0,r=0;
    cin>>n>>m>>root;
    for(int i=1;i<=n-1;i++)
    {
        cin>>u>>v;
        adde(u,v);
        adde(v,u);
    }
    dfs(root,0);
    for(int i=1;i<=m;i++)
    {
        cin>>l>>r;
        cout<<lca(l,r);
        if(i<m)cout<<endl;
    }
    return 0;
}

2. 线段树

众所周知，ST表虽然能上树，但是它终究是个静态的东西，不带修让人很难受，我们现在就开始学习一种OIer根本无法绕开不学的数据结构——线段树！！！（Segment Tree，SGT），它支持动态修改和点查/区查，并且全是O(\log_2 n)级别的，相当的快啊。

而且还有很多变种：

• 按值域分的权值线段树

• 区间第k小的可持久化线段树（主席树）

• 看上去好像是计算几何的李超线段树

• 卡常大师zkw线段树

• 解决区间历史问题的吉司机线段树

• 线段树从隔壁平衡树学的的合并与分裂

• 在树套树的战场共襄盛举

但是这些东西本文基本上都不学……

权值线段树会讲，zkw本来想讲，但是发现没必要（

我们省选再见好吧。

2.1 普通线段树

线段树确实是树形的，但是它维护的还是一个线性序列的信息，它的节点事实上是维护一个区间的信息。

所以，我们可以从根节点开始，一步步递归，分治，把每个节点所代表的区间端点传递下去。为什么可以递归呢？这里引入一个小结论，我们暂时不予证明：

对于一棵二叉树，节点x的左儿子为2x，右儿子为2x+1，写成位运算的形式为x<<1和(x<<1)|1

做了这么多题，你应该对下表和信息存储之间的关系有些想法了。现在让我们来看看具体怎么递归。

首先，我们把信息读入原线性数组arr，设其长度为n，然后进行线段树的初始化。根节点所代表的区间自然是[1,n]，如果没有到叶子节点，我们就别停，设当前传递到了区间[l,r]，我们取mid=\lfloor \frac{l+r}{2}\rfloor，以[l,mid]和[mid+1,r]两个区间分别递归。

哦，什么时候停呢，不是叶子节点就递归，那是叶子节点就停呗！什么节点算叶子节点呢？当然是分无可分的时候，即l==r，分不出来了。这个时候，我们就设tree[pos]=arr[l]，代表[l,l]，当然就是arr[l]嘛！其中pos为当前递归位置，也可以认为是当前节点个数，不过就不利于理解下面的知识了（

当然，在递归建树完成后，我们还要进行一些小操作，每个节点既然代表了区间信息，那我们总得把信息拉到上面的节点来吧，不能沉在底下的叶子吧，你在ST表那里也干了这种活。

比如说区间和，我们可以直接把节点i的左右儿子的答案加在一起，作为节点i的答案。为什么呢？有没有发现，我们递归建树时，刚好把[l,r]对半切开，无缝分成两个儿子所代表的区间？所以我们统计该节点的答案时，只要把它儿子们的答案相加就可以了。我们把这个操作叫做pushup()，很形象吧，把底下的答案拉上去。

在每个节点的两个儿子的递归都跑完了后，我们就把答案pushup()上来，如果有目的的话，就是方便查询）

初始化完了，我们来讨论区修和区查，单点就是特殊情况嘛。

首先谈谈区间修改，我们怎么做呢，就是把待修改区间传递下去，对于每个节点i，如果它所代表的区间能够被我们所要修改的区间包括的话，那我们肯定传到足够小的区间了，把这个节点的答案更新，然后直接返回，跑。

不然的话，那就说明区间还分的不够小，我们取熟悉的mid，但是是这个节点的左右端点。然后判断一下，如果传入的左端点在中间值左边，那就说明在这个节点代表区间的左半边有贡献，左半边怎么表示？左儿子嘛！同理，右端点比中间值大的话，右半边就也需更改，就是右儿子嘛！最后改完了，别忘了pushup()

查询也是很简单，在修改的基础上改一下：

• 如果传入区间大于等于该节点区间，那就查到头了，直接将该节点的内容返回即可。

• 不然再计算一下该区间的mid，传入区间的左端点小的话，就去统计左儿子的贡献，右端点比mid大的话，就统计右儿子的贡献

• 最后返回答案就可以了，不需要pushup()

关于这些区间左右儿子，怎么体现呢？在修改和查询的函数里都加个pos参数，直接传儿子编号就行了，和初始化一样。最初调用时，我们赋1就可以，从根开始搜嘛。

这就是线段树的基本操作了，下面先来写道模板题。

习题2.1.1

P3372 【模板】 线段树 1

首先，线段树的数组要开4倍空间，严谨证明？从没给过好吧。

这里再了解一个知识：懒标记（lazytag）

说是能延迟修改，但是我没看出来（

反正如果要继续向下修改/查询的话，就要把左右儿子的懒标记加上父亲的，同时改掉左右儿子的答案，最后把父亲的懒标记清空（传下去了，不要了）。这个操作叫pushdown()，就是把懒标记传下去。这个如果改到了叶子，那就直接加上懒标记就行了。

好了，你已经了解完了，可以先试试，我没有能力搞来好图片演示，靠干讲实在不太行。可以对着我的代码调（

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
#define int long long

int arr[maxn];
struct node
{
    int l;
    int r;
    int sum;
    int lazy;
};
node tree[maxn*4];

inline int lson(int pos)
{
    return pos<<1;
}

inline int rson(int pos)
{
    return (pos<<1)|1;
}

inline void pushup(int pos)
{
    tree[pos].sum=tree[lson(pos)].sum+tree[rson(pos)].sum;
}

inline void pushdown(int pos)
{
    if(tree[pos].lazy!=0)
    {
        tree[lson(pos)].lazy+=tree[pos].lazy;
        tree[rson(pos)].lazy+=tree[pos].lazy;
        tree[lson(pos)].sum+=tree[pos].lazy*(tree[lson(pos)].r-tree[lson(pos)].l+1);
        tree[rson(pos)].sum+=tree[pos].lazy*(tree[rson(pos)].r-tree[rson(pos)].l+1);
        tree[pos].lazy=0;
    }
}

void build(int pos,int l,int r)
{
    tree[pos].l=l;
    tree[pos].r=r;
    tree[pos].lazy=0;
    if(l==r)
    {
        tree[pos].sum=arr[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson(pos),l,mid);
    build(rson(pos),mid+1,r);
    pushup(pos);
    return;
}

int query(int L,int R,int pos)
{
    if(tree[pos].l>=L&&tree[pos].r<=R)
    {
        return tree[pos].sum;
    }
    pushdown(pos);
    int mid=(tree[pos].l+tree[pos].r)>>1;
    int sum=0;
    if(L<=mid)sum+=query(L,R,lson(pos));
    if(R>mid)sum+=query(L,R,rson(pos));
    return sum;
}

void update(int L,int R,int pos,int val)
{
    if(tree[pos].l>=L&&tree[pos].r<=R)
    {
        tree[pos].sum+=val*(tree[pos].r-tree[pos].l+1);
        tree[pos].lazy+=val;
        return;
    }
    else
    {
        pushdown(pos);
        int mid=(tree[pos].l+tree[pos].r)>>1;
        if(L<=mid)update(L,R,lson(pos),val);
        if(R>mid)update(L,R,rson(pos),val);
        pushup(pos);
    }
}

signed main()
{
    int n=0,m=0,op=0,x=0,y=0,k=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        cin>>op>>x>>y;
        if(op==1)
        {
            cin>>k;
            update(x,y,1,k);
        }
        else
        {
            cout<<query(x,y,1);
            if(i<m)cout<<endl;
        }
    }
    return 0;
}

习题2.1.2

P3373 【模板】 线段树 2

这里有两个懒标记那就开两个呗（，传递时改区间答案，记得先乘上乘法的lztag，再加上加法的。主要是为了符合运算律。主要是加法tag更新时要乘上乘法的tag，这一点很麻烦。可以像下面一样写个专门的函数计算。

而且乘法懒标记要赋为1！赋0就改不动了！

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
#define int long long

int arr[maxn];
struct node
{
    int l;
    int r;
    int sum;
    int add;
    int mul;
};
node tree[maxn*4];

inline int lson(int pos)
{
    return pos<<1;
}

inline int rson(int pos)
{
    return (pos<<1)|1;
}

inline void calc(int pos,int add,int mul,int mod)
{
    tree[pos].sum=(tree[pos].sum*mul+(add*(tree[pos].r-tree[pos].l+1)))%mod;
    tree[pos].mul=(mul*tree[pos].mul)%mod;
    tree[pos].add=(tree[pos].add*mul+add)%mod;
}

inline void pushup(int pos)
{
    tree[pos].sum=tree[lson(pos)].sum+tree[rson(pos)].sum;
}

inline void pushdown(int pos,int mod)
{
    calc(lson(pos),tree[pos].add,tree[pos].mul,mod);
    calc(rson(pos),tree[pos].add,tree[pos].mul,mod);
    tree[pos].add=0;
    tree[pos].mul=1;
}

void build(int pos,int l,int r)
{
    tree[pos].l=l;
    tree[pos].r=r;
    tree[pos].add=0;
    tree[pos].mul=1;
    if(l==r)
    {
        tree[pos].sum=arr[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson(pos),l,mid);
    build(rson(pos),mid+1,r);
    pushup(pos);
    return;
}

int query(int L,int R,int pos,int mod)
{
    if(tree[pos].l>=L&&tree[pos].r<=R)
    {
        return tree[pos].sum;
    }
    pushdown(pos,mod);
    int mid=(tree[pos].l+tree[pos].r)>>1;
    int sum=0;
    if(L<=mid)sum+=query(L,R,lson(pos),mod)%mod;
    if(R>mid)sum+=query(L,R,rson(pos),mod)%mod;
    return sum;
}

void update(int L,int R,int pos,int add,int mul,int mod)
{
    if(tree[pos].l>=L&&tree[pos].r<=R)
    {
        calc(pos,add,mul,mod);
        return;
    }
    else
    {
        pushdown(pos,mod);
        int mid=(tree[pos].l+tree[pos].r)>>1;
        if(L<=mid)update(L,R,lson(pos),add,mul,mod);
        if(R>mid)update(L,R,rson(pos),add,mul,mod);
        pushup(pos);
    }
}

signed main()
{
    int n=0,m=0,mod=0,op=0,x=0,y=0,k=0;
    cin>>n>>m>>mod;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        cin>>op>>x>>y;
        if(op==1)
        {
            cin>>k;
            update(x,y,1,0,k,mod);
        }
        else if(op==2)
        {
            cin>>k;
            update(x,y,1,k,1,mod);
        }
        else
        {
            cout<<query(x,y,1,mod)%mod;
            if(i<m)cout<<endl;
        }
    }
    return 0;
}

习题2.1.3

P8856 [POI2002]火车线路

来看一道线段树的初级应用，这里也讲解一下，线段树如何解RMQ问题。

思路很简单，把时间轴看成是原线性数组，初始每个元素都为s，，然后初始化。每次查询在这段时间里的座位数的最小值，如果大于需要的座位，那就可以买，整段区间减掉座位，不然就不可以总司令（

用线段树求这种动态RMQ问题和求区间和有什么区别呢？

……

没有什么区别（

• pushup()$里的加和改成$\min$ or $\max

• 查询函数里的累加改成\min or \max

结束。额……确实只有这种区别（

哦，数据表明，到第D天，人家下车了，不占座位了，所以所有查询和修改的区间都应为[O,D) or [O,D-1]

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;

struct node
{
    int l;
    int r;
    int val;
    int lazy;
};
node tree[maxn*4];

inline int lson(int pos)
{
    return pos<<1;
}

inline int rson(int pos)
{
    return (pos<<1)|1;
}

inline void pushup(int pos)
{
    tree[pos].val=min(tree[lson(pos)].val,tree[rson(pos)].val);
}

inline void pushdown(int pos)
{
    if(tree[pos].lazy)
    {
        tree[lson(pos)].lazy+=tree[pos].lazy;
        tree[rson(pos)].lazy+=tree[pos].lazy;
        tree[lson(pos)].val+=tree[pos].lazy;
        tree[rson(pos)].val+=tree[pos].lazy;
        tree[pos].lazy=0;
    }
}

void build(int pos,int l,int r,int s)
{
    tree[pos].l=l;
    tree[pos].r=r;
    tree[pos].lazy=0;
    if(l==r)
    {
        tree[pos].val=s;
        return;
    }
    int mid=(l+r)>>1;
    build(lson(pos),l,mid,s);
    build(rson(pos),mid+1,r,s);
    pushup(pos);
    return;
}

void change(int pos,int l,int r,int val)
{
    if(tree[pos].l>=l&&tree[pos].r<=r)
    {
        tree[pos].val+=val;
        tree[pos].lazy+=val;
        return;
    }
    else
    {
        pushdown(pos);
        int mid=(tree[pos].l+tree[pos].r)>>1;
        if(l<=mid)change(lson(pos),l,r,val);
        if(r>mid)change(rson(pos),l,r,val);
        pushup(pos);
    }
}

int query(int pos,int l,int r)
{
    if(tree[pos].l>=l&&tree[pos].r<=r)
    {
        return tree[pos].val;
    }
    pushdown(pos);
    int mid=(tree[pos].l+tree[pos].r)>>1;
    int res=0x3f3f3f3f;
    if(l<=mid)res=min(query(lson(pos),l,r),res);
    if(r>mid)res=min(query(rson(pos),l,r),res);
    return res;
}

int main()
{
    int n=0,num=0,m=0,l=0,r=0,k=0;
    cin>>n>>num>>m;
    build(1,1,n,num);
    for(int i=1;i<=m;i++)
    {
        cin>>l>>r>>k;
        if(query(1,l,r-1)>=k)
        {
            cout<<"T";
            change(1,l,r-1,-k);
        }
        else cout<<"N";
        if(i<m)cout<<endl;
    }
    return 0;
}

比分块来说，SGT可能更优，但也更容易被卡（，而且确实没有分块好写。

2.2 权值线段树

权值线段树肯定是沿袭了线段树的基本框架，但是原线性数组已被确定为题目所给值域，所以不用初始化了。

所以我们tree数组就可以确定为int类型，表示每个数值出现的次数，当然你硬是要用node类型也可以，但值域不大，不用优化时，我们显然可以偷懒，直接写成int，降低编码难度。

如果不用初始化，那我们修改和查询的区间传什么呢？你……肯定是在整个线性数组范围内查找啊，之前线段树是[1,n]，那我们现在变成以值域作为线性数组，那最初传入的区间就是值域嘛！即[-maxn,maxn]。如果题目中没有给负数，那就[0,maxn]，如果0也不给，那你照着写呗，总不能都是我给结论吧（

好，接下来我们了解一下权值线段树的功能：

• 插入/删除一个数

相当于在线性数组上加减一个数，出现次数\pm 1嘛

• 查询这个数在全局范围内多大

比它小的数有多少个，加上它自己1个。

• 查询现在第k小的数

因为线段树的每个叶子都是线性序列上的节点，所以我们只要找到第k小的叶子就可以了。

区间第k小请转向主席树 or 树套树

• 查全局前驱后继

查查自己多大，再查查自己前后面是谁，搞定。

现在我们来一步步实现这些操作。

首先，把前面线段树的修改函数先拷过来。然后l==r的那个判叶子代码改成tree[pos]++或tree[pos]--，就表示我们在这个位置添加或者删除一个数了，pushup()还是要的，毕竟还要把每个区间的数据逐级拉上来。

我们的mid取传入区间的中间值，如果我们要修改的数比中间值小，显然要找左儿子，否则就找右儿子。

关于查询第k小的数呢，我们直接以k为基础判断，对于当前节点，如果k小于等于它的左边界，那不行，找找左儿子，显然传这个区间的一半作为值域，mid是老朋友了。不然的话，就说明整个左子树都小于k，那么我们就找右子树，但是右子树要减掉左子树的大小，因为左子树占了名额嘛。如果找到合适的叶子了，我们就返回叶子的边界（也就是第k小的数嘛）

那么，我们怎么进行这个逆操作，即查询一个数是多大呢？先把刚写的第k小拷过来，然后略作改动。具体就是如果这个数小于我们的老朋友mid，那就查左子树，反之，就查它在右子树中的排名，然后加上左子树的大小，左子树也占了名额嘛。

有了这两个互逆操作，我们查前驱后继就简单多了，首先，看看自己要传入的数是第几小，然后再查第（几-1）或（几+1）的数就可以了。

事实上，这几个功能跟我们接下来要讲的平衡树极为接近，所以我们可以找平衡树的板子来练习权值线段树。

习题2.2.1

P3369 【模板】普通平衡树

当你学了平衡树后，你肯定会觉得还是权值线段树好写，而且平衡树不一定能跑得比权值线段树快，只是权值线段树的区间比较大（虽然也没看到题目卡），比如说本题的值域就为\pm 1e7，加上线段树的四倍空间，我们可以把数组开到8 \times 10^7，要通过本题很有点困难，我们来介绍权值线段树（其实普通线段树也可以）的一种空间优化：动态开点。

什么是动态开点呢？我们给线段树开四倍空间，这些空间不管你用不用都要开在那里，很没必要。动态开点就是需要修改（在权值线段树里体现在添加或删除一个数）时才开这个点，如果有数从来没出现过，我们就不开这个点了，这样就可以把实际空间节省到点数\times 4，当然你开4倍空间时还是要写1e7这个值域的。

区别主要体现在插入和删除上，我们设一个变量root表示根节点并赋0，将传入的pos改为引用传递（在函数里的修改是改你传进来的变量，所以不能传一个数），然后先把pos传进去。再设一个tot表示总点数。

在添删的操作里，如果传入的pos为空，那我们就直接把tot加一，然后把root赋成新的tot。因为传进来的都是左右儿子，如果他们为空，那肯定要新加点。

加了动态开点以后，节点的左右边界会变得不确定（因为省了一些点），建议直接开个结构体存着。这里的root是传了个引用，一开始赋成0，后面会自动改的，即根节点的编号。

然后就没了，没了？没了。

下面没给朴素写法（朴素写法又不是AC Code），直接加了动态开点，以供对照。

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;//询问数
const int maxn2=1e7+5;//值域

int tree[maxn*4];//每个节点储存内容
struct interval
{
    int l;
    int r;
};
interval node[maxn*4];//每个点所代表的边界
int tot=0;//点数

inline void pushup(int pos)
{
    tree[pos]=tree[node[pos].l]+tree[node[pos].r];
}

void ins(int &pos,int l,int r,int val)//插入
{
    if(!pos)pos=++tot;//新增一个点
    if(l==r)//只有叶子值域才会缩成一个点
    {
        tree[pos]++;//rp++
        return;//要是不返回你就死定了
    }
    int mid=(l+r)>>1;//二分
    if(val<=mid)ins(node[pos].l,l,mid,val);//插入的数比当前节点代表的区间的中间值还小，那就往左边找
    else ins(node[pos].r,mid+1,r,val);//要不还是往右边找吧
    pushup(pos);//别忘了把这个数汇报给上级
}

void del(int &pos,int l,int r,int val)//删除，和插入基本一致
{
    if(!pos)pos=--tot;//关于这个点，它死了。别忘了把这个点销户
    if(l==r)
    {
        tree[pos]--;
        return;
    }
    int mid=(l+r)>>1;
    if(val<=mid)del(node[pos].l,l,mid,val);
    else del(node[pos].r,mid+1,r,val);
    pushup(pos);
}

int kth(int pos,int l,int r,int k)//全局第k个
{
    if(l==r)return l;//找到合适的叶子了，很明显叶子的边界就是排名
    int mid=(l+r)>>1;//二分again
    if(k<=tree[node[pos].l])return kth(node[pos].l,l,mid,k);//你要找的数在左子树上
    else return kth(node[pos].r,mid+1,r,k-tree[node[pos].l]);//你要找的数在右子树上，同时，左子树占了名额，把它们都减去
}

int getrank(int pos,int l,int r,int val)//全局排名查询
{
    if(l==r)return 1;//找到了！
    int mid=(l+r)>>1;//二分again again
    if(val<=mid)return getrank(node[pos].l,l,mid,val);//去左边那桌
    else return getrank(node[pos].r,mid+1,r,val)+tree[node[pos].l];//去右边那桌，记得把左边的名额带过来
}

int main()
{
    int n=0,op=0,x=0,root=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>op>>x;
        if(op==1)
        {
            ins(root,-maxn2,maxn2,x);
        }
        if(op==2)
        {
            del(root,-maxn2,maxn2,x);
        }
        if(op==3)
        {
            cout<<getrank(root,-maxn2,maxn2,x);
            if(i<n)cout<<endl;
        }
        if(op==4)
        {
            cout<<kth(root,-maxn2,maxn2,x);
            if(i<n)cout<<endl;
        }
        if(op==5)
        {
            int num=getrank(root,-maxn2,maxn2,x);//前驱肯定是第k-1个数
            cout<<kth(root,-maxn2,maxn2,num-1);
            if(i<n)cout<<endl;
        }
        if(op==6)
        {
            int num=getrank(root,-maxn2,maxn2,x+1);//后继肯定是第k+1个数
            cout<<kth(root,-maxn2,maxn2,num);
            if(i<n)cout<<endl;
        }
    }
    return 0;
}

2.3 树状数组

学了线段树，你可能会被它的码量深深折服（

其实它还有种码量小的对手（当然实际应用中不是这么回事），叫树状数组

二者的思维比较相近，都是把线性结构转为树形结构。但

• 树状数组的额外数组不需要开四倍空间，而只有一倍空间

• 能够做到和线段树一样的修改与查询的时间复杂度，即O(\log_2 n)，相当优秀。

• 当然，它的拓展性极差，而且区间修改和区间查询放到一起就会极麻烦，所以我们就不讲这种情况了（

它是怎么做到的呢？这个问题比较抽象。简单来说，它删掉了一棵普通的二叉树的一些节点，与线段树一样，原数组沉在最底下，然后上面的辅助节点的编号进行二进制展开后最后面的1屁股后面的零坨一样多，零坨越多，转化成树的深度越浅。

似乎很抽象，我们举个例子，假设原数组长度为8

然后我们把1-8展开成二进制：

容易发现，相同颜色标记的数字都满足这个特点。所以，对有8个元素的数组，我们构建树状数组后，应该是如下结构：

• 第一层：tree[8]

• 第二层：tree[4]

• 第三层：tree[2],tree[6]

• 第四层：tree[1],tree[3],tree[5],tree[7]

• 第五层：原数组。

每层有什么节点清楚了……清楚了吗？n个节点都这么推吗？，如何让计算机去数最后面的零坨？

我们在这里介绍一种运算：lowbit()

首先我们先给待求数按位取反，然后+1，由计算机基本原理可知，这个操作相当于直接取负，所以不要怕实现复杂。

然后，我们拿着这个数和原数进行按位与，C++就一个&，我们不管了。

比如说6，我们展示它有内容的字节（int有四个字节嘛），演示一下这个过程：

• 原数：00000110

• 按位取反：11111001

• 加一：11111010

• 按位与：

你看，是不是就拿到了一个数最后一个1和后面的零坨？

数学证明就不要深究了……whk数学能拿多少分，还能看得懂这种证明。（ （无恶意）

我们就规定，树状数组tree[i]储存的是原数组的右端点为i的信息。

？？？

那左端点呢？1吗？nonono，那跟前缀和数组还有什么区别

我们又在这里定义，tree[i]的所储存的区间的长度是lowbit(i)，这样的话，手模一下上面的例子，tree[i]的元素各自存储的区间为：

然后呢？这么规定有什么用？

别急啊，首先，我们思考一下线段树的几个功能

因为前面说了区修区查一起搞很复杂，所以，我们分点修+区查和区修+点查两种情况来讨论。

• 点修+区查

我们考虑对单点进行修改，比如说，我们改arr[1]，那跟tree数组有什么关系呢？一看先前的表，哦，tree[1],tree[2],tree[4],tree[8]都涉及到了arr[1]这个位置，那都要改咯。

但是每一个点都会牵扯到这么多区间吗？我们怎么进行tree[i]更改的转移呢？

我们研究1,2,4,8这四个数的关系，这时，我们就请出我们的利器lowbit()，既然都说了有关系，先拿它试试呗：

哦，似乎有点好玩的事情。

哦！我们在线段树里就发现了，深度越浅的节点区间越大，所以当修改了一个点时，我们要把它的修改值传上去，就可以一直给它的下标+lowbit(它的编号)，这样做可以不重不漏，好耶！

但这只是个孤证啊！没事，我们再改个arr[5]，查表，先改tree[5]，加个lowbit(5)=1，转移到了tree[6]，再加个lowbit(6)=2，就到了tree[8]了！可以证明没有哪个包含arr[5]的区间被落下。

那就这样了，假如我们要修改arr[i]，我们只要修改它对应的tree[i]，然后一路加lowbit()转移，转移一次修改一次，直到tree[n]修改完成，因为tree[n]代表了[1,n]，这肯定是最大的，所以不用再修改了。我们就退出。

那区间查询呢？好像有点不方便。比如我们要查询[1,6]，查表，可以直接返回tree[4]+tree[6]，那查询[3,6]呢？不行了吧。

但是我们可以观察到，查找[1,i]这个区间，基本上就是修改的逆操作，我们可以直接减减减lowbit(),减到tree[1]打止。

那我们有一个构想，对于可差分的信息，比如区间和，[l,r]的答案显然就是[1,r]的答案减去[1,l-1]的答案,那么我们只要查询两次，再把答案相减就可以了，那么不可差分的信息怎么维护？对不起，不好搞，对于我们无法解决的问题，我们就把它扔进限制条件，让后世OIer们受苦吧）

当然，存在一种O(\log^2n)（对你没看错）的做法可以这么做，但我们用不上，所以鸽了，咕咕咕。

由于这种模式下查询时tree下标往前走，修改时往后走，我们可以记成“向前查，向后修”

习题2.3.1

P3374 【模板】树状数组 1

本题为div.点修+区查

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+7;

int treearr[maxn];

inline int lowbit(int x)
{
    return x&-x;
}

void change(int n,int pos,int val)
{
    while(pos<=n)
    {
        treearr[pos]+=val;
        pos+=lowbit(pos);
    }
}

int query(int pos)
{
    int t=0;
    while(pos>0)
    {
        t+=treearr[pos];
        pos-=lowbit(pos);
    }
    return t;
}

int main()
{
    int n=0,m=0,buf=0,op=0,x=0,val=0,l=0,r=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>buf;
        change(n,i,buf);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>op;
        if(op==1)
        {
            cin>>x>>val;
            change(n,x,val);
        }
        else
        {
            cin>>l>>r;
            cout<<query(r)-query(l-1);
            if(i<m)cout<<endl;
        }

    }
    return 0;
}

• 区修+点查

我们前面点查修改一次要从树上爬下去，是O(\log_2 n)的。如果暴力扫的话会是O(n\log_2 n)，题目受不住。

我在这时看了一眼自己的代码……所以为什么要暴力扫？

我们在区间查询时提到了两点：

一次查询，查的是[1,i]

查询和修改刚好方向相反

那么，我们也可以发现，区修实质上可以沿用点修的函数，点修影响了包含这个点的区间，可以认为，在它修改的区间内，最大的是[i,n]（虽然实际上没有改这么多）如果这些区间中有的不能改，我们可以把它改回来就是了。

我们试试这个猜想，对于区间[3,5]，我们修改一下3：

我们发现，实质上，你可以认为修改对[3,8]都产生了影响，但我们只要修改[3,5]，所以应该把[6,8]的影响抵消掉

怎么做？不难发现，以6为起点，数值相反，再做一次区修嘛！6是甚么？右端点5再加一嘛！

好，因为只爬了两次，我们依然只有O(\log_2 n)。

我们居然把O(n\log_2 n)打成了O(\log_2 n)，整整一个n啊！这就是算法的力量！

接下来是最后一关了！点查怎么写？

由于树状数组区修区查奇怪的不相容性质，搭配区修，点查也爬两次会出现一点小错误怎么都算不对。我们在这种情况下读入数据时应直接把数据读入原数组arr，然后点查i结果就是给i的区查函数的结果加上arr[i]。原理我们不予证明，因为树状数组此时的性质已经变为了差分数组。

习题2.3.2

P3368 【模板】树状数组 2

本题为div.区修+点查

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+7;

int treearr[maxn];
int arr[maxn];

inline int lowbit(int x)
{
    return x&-x;
}

void change(int n,int pos,int val)
{
    while(pos<=n)
    {
        treearr[pos]+=val;
        pos+=lowbit(pos);
    }
}

int query(int pos)
{
    int t=0;
    while(pos>0)
    {
        t+=treearr[pos];
        pos-=lowbit(pos);
    }
    return t;
}

int main()
{
    int n=0,m=0,op=0,x=0,val=0,l=0,r=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>op;
        if(op==1)
        {
            cin>>l>>r>>val;
            change(n,l,val);
            change(n,r+1,-val);
        }
        else
        {
            cin>>x;
            cout<<query(x)+arr[x];
            if(i<m)cout<<endl;
        }

    }
    return 0;
}

树状数组比线段树的优点就是码量巨小，好调试，没别的。

3.平衡树选讲

平衡树是一种较为强劲但真的很麻烦的二叉搜索树。

一般平衡树的时间都比权值线段树长，但是空间只需一倍，而不是8倍，但有动态开点后还管什么！平衡树主要还能解决区间翻转，比如所谓“文艺平衡树”，这个权值线段树比较困难，不好实现对应的操作。

多种平衡树的主要作用都是防止二叉查找树退化成链。一般的，当插入的节点过多过密时，线段树基本上就只有一条链有实际信息了。比如想象一下插入{1,4,5}三种元素的其中一个，插1e7次，那查询时肯定有许多冗余区间，而且会把树高退化到O(n)，更不利于查找。平衡树就是通过给每个点一个随机权值，使树高维持在O(\log_2 n)，防止成链。

平衡树基于这两个指标维护树高和查找的操作也是多种多样而且很抽象的，一般来说，平衡树和它们维护树高的操作如下：

是不是只有最后一个最特殊？那就是我们要学的（

一种想法是把集合不再局限在“线性序列”的刻板印象里，而是一棵树，那就好判断了，如果两个点所在的“集合树”的根节点相同，那肯定就在一个集合里，反之亦然。

怎么找根节点？不要讲了吧？既然每个节点的父亲一开始都定义成自己的编号了，如果编号依然等于自己，那就说明这个点掌握了自己的人生（雾），肯定是根节点啊！

一个口胡证明：两棵有根树不可能有公共点，比如考虑以下以邻接表给出的树，无向边会成链，所以是有向边：

5 4
1 2
1 3
4 3
4 5

显然若把1和4当作两个根节点，那这两棵树就可以有一个公共点3，那这样，谁来做代表集合的树根呢（

这样我们就有了集合确定的唯一性，而且因为借助树的结构，我们要判根很容易，极限情况下是O(\log_2 n)（树的最大高度），但是还有更优解，接下来介绍两个并查集的常见优化：

1. 路径压缩

每往上跳一层，我们就把当前节点的父亲改成当前节点的父节点的父亲，如此循环，最后原本在一条链上的节点都和根节点直接相连，下次查找路径就短了。

2. 按秩合并/启发式合并

因为你显然不能保证两棵待合并的“集合树”都已经路径压缩至最优，所以它们的高度肯定是\ge 2的。那为了压查找的时间，我们就可以按树的高度进行抉择，把高度小的树根节点的父节点设为高度大的树的根节点。这种方法就叫按秩合并，要这么做，需要开个rank数组维护每个点所在高度，而且集合合并会变得较为复杂（

因此，我们在赛场上常使用另一种可能不那么稳定，但是好写的多的优化：启发式合并。

讲的很高深，事实上，直观也可以感受到，树的高度越高，节点就应该越多，所以我们可以按两棵树的大小决策，把节点少的树加进节点多的树。这么做一下，可以让单次合并复杂度直接降到O(\alpha(n))。这个数学证明是真的很复杂，所以就不放了QAQ

为什么说不稳定呢？因为如果其中有一棵树路径压缩很彻底，而另一棵就压缩的很少，显然这时可能会将压缩少的树放去压缩多的树，从而跑更长的路。但是问题不大的。

有时因为集合的边维护了某种信息，这时不能简单的路径压缩，我们就只使用按秩合并或启发式合并。

但是呢，一旦合并到一个集合里，就很难在多项式时间里把两个点分开。只是提一嘴，没考过（

关于这个“树”怎么存呢？事实上，只要开个对应的fa数组，维护每个点对应的父亲就可以了。初始化也和暴力一样，初始化为每个元素的对应下标。再开个sz数组维护大小，每个元素的sz初始为1，结束！

习题4.1.1

P3367 【模板】并查集

这就是模板题了。动手吧！

为什么这么多人不喜欢写merge() (

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;

int fa[maxn];
int size[maxn];

void set_make(int len)
{
  for(int i=1;i<=len;i++)
  {
    fa[i]=i;
    size[i]=1;
  }
}

int find(int val)
{
  if(fa[val]==val)return val;
  return fa[val]=find(fa[val]);
}

void merge(int x,int y)
{
  x=find(x);
  y=find(y);
  if(size[x]>size[y])swap(x,y);
  fa[x]=y;
  size[x]+=size[y];
}

int main()
{
  int n=0,m=0,z=0,x=0,y=0;
  cin>>n>>m;
  set_make(n);
  for(int i=1;i<=m;i++)
  {
    cin>>z;
    if(z==1)
    {
      cin>>x>>y;
      //cout<<"Union set "<<x<<" with set "<<y<<endl;
      merge(x,y);
    }
    if(z==2)
    {
      cin>>x>>y;
      //cout<<x<<" is in set "<<find(x)<<endl;
      //cout<<y<<" is in set "<<find(y)<<endl;
      cout<<(find(x)==find(y)?"Y":"N");
      if(i<m)cout<<endl;
    }
  }
  return 0;
}

好像判集合写丑了，汗。

习题4.1.2

P1551 亲戚

看了半天回想，这实在找不出不是双倍经验的理由（

完了，这个判同祖先怎么也写得这么丑（

哦，题目原因，没事）

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;

int fa[maxn];
int size[maxn];

void set_make(int len)
{
  for(int i=1;i<=len;i++)
  {
    fa[i]=i;
    size[i]=1;
  }
}

int find(int val)
{
  if(fa[val]==val)return val;
  return fa[val]=find(fa[val]);
}

void merge(int x,int y)
{
  x=find(x);
  y=find(y);
  if(size[x]>size[y])swap(x,y);
  fa[x]=y;
  size[x]+=size[y];
}

int main()
{
  int n=0,m=0,p=0,mx=0,my=0,px=0,py=0;
  cin>>n>>m>>p;
  set_make(n);
  for(int i=1;i<=m;i++)
  {
    cin>>mx>>my;
    merge(mx,my);
  }
  for(int i=1;i<=p;i++)
  {
    cin>>px>>py;
    cout<<((find(px)==find(py))?"Yes":"No");
    if(i<p)cout<<endl;
  }
  return 0;
}

习题4.1.3

P1525 [NOIP2010 提高组] 关押罪犯

说了要把这道题作为并查集的典题的，差点忘了。

这一题代表一种常考题型，叫做“种类并查集”或者“种族并查集”，主要就是解决这种“敌人”问题

我们假想，对于每个元素i都有一个“共轭”兄弟i'，它们名义上是一个点，但属性截然相反。比如i和j是敌人，那i和j'，i'和j就是好朋友。

我们考虑将关系建模成节点的边，那我们就可以采用简单的贪心策略，将这些边按边权从大到小排序，从最小的开始选，每次选条边，就尝试将边的两个端点各自和对方的“共轭”兄弟合并，如果已经被合并过了，那就说明不能这么安排，此时这条边的边权就是答案。

砹氩这个merge()写的更丑了，有时间要把这些讲解题目的远古代码都重构一遍！！

事实上：咕值++

怎么在程序中表示i'和j'呢？我们可以直接开两倍的fa和sz，然后，对于每个节点k，直接令k+n为k'，好写好记。

而且，既然使用了“边”的概念，那么这道题就可以用些图论的算法过，比如标签里的“tarjan”和“二分图”，这些与本讲无关，所以略去，作为思考。

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;

int n=0,m=0;
int fa[maxn];
int size[maxn];

struct relation
{
  int a,b,c;

  friend bool operator <(const relation &a,const relation &b)
  {
    if(a.c<b.c)return true;
    else return false;
  }

};

relation arr[maxn];

void set_make(int len)
{
  for(int i=1;i<=len;i++)
  {
    fa[i]=i;
    size[i]=1;
  }
}

int find(int val)
{
  if(fa[val]==val)return val;
  return fa[val]=find(fa[val]);
}

bool merge(int x,int y)
{
  int x1=find(x);
  int y1=find(y);
  int x2=find(x+n);
  int y2=find(y+n);
  if(x1==y1)return false;
  fa[x1]=y2;
  fa[y1]=x2;
  return true;
}

int main()
{
  cin>>n>>m;
  set_make(2*n);
  for(int i=1;i<=m;i++)
  {
    cin>>arr[i].a>>arr[i].b>>arr[i].c;
  }
  sort(arr,arr+m+1);
  /*for(int i=1;i<=m;i++)
  {
    cout<<arr[i].c<<' ';
  }
  cout<<endl;*/
  for(int i=m;i>=1;i--)
  {
    //cout<<arr[i].a<<' '<<arr[i].b<<endl;
    if(merge(arr[i].a,arr[i].b)==false)
    {
      cout<<arr[i].c;
      return 0;
    }
  }
  cout<<0;
  return 0;
}

习题4.1.4

P1892 [BOI2003]团伙

这题也是种类并查集的碘

对于这题，如果i和j是敌人，我们就把i和j'，j和i'两对好朋友节点合并，如果i和j本来就是朋友，那就直接合并。

最后统计有多少个集团，也就是集合的个数，输出就可以了。

总算有个优美的merge()了

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
const int maxm=5e3+7;

int fa[maxn*2];
int sz[maxn*2];

void set_make(int n)
{
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        sz[i]=1;
    }
}

int find(int x)
{
    if(fa[x]==x)return fa[x];
    else return fa[x]=find(fa[x]);
}

bool merge(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return false;
    else
    {
        fa[x]=y;
        return true;
    }
}

int main()
{
    int n=0,m=0,u=0,v=0;
    int res=0;
    char order;
    cin>>n>>m;
    set_make(n*2);
    for(int i=1;i<=m;i++)
    {
        cin>>order;
        cin>>u>>v;
        if(order=='E')
        {
            merge(u+n,v);
            merge(v+n,u);
        }
        if(order=='F')
        {
            merge(u,v);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(fa[i]==i)res++;
    }
    cout<<res;
    return 0;
}

2024/8/24 23:32:00 初稿！完结撒花！！！