并查集
一些常常出现的问题
比如mle
这通常是find()函数写错了爆栈了
错误写法：
int find(int x)
{
if(p[x]!=x)
p[x]=find(x);
return p[x];
}
正确写法：
int find(int x)
{if(p[x]!=x)
p[x]=find(p[x]);
return p[x];
}
同时要注意合并两个集合是一定是祖先合并不能
错误写法：p[a]=b;
正确写法：p[pa]=pb;
例题：格子游戏(模板题) [https://www.acwing.com/problem/content/1252/](https://)
用到了二维降一维的做法
int get(int a,int b)
{
return (a-1)*n+b;
}//将(a,b)坐标转化为对应的一维坐标
并查集也可统计连通块
例题：搭配购买（1252）
当值域太大而数少时离散化就要上场了
(运用map进行离散)
unordered_map<int,int>mp;
int m=0;
ing get(int a)
{
if(!mp.count(a))mp[a]=++m;
return mp[a];
}
unordered_map是无序的。
map会进行排序。
例题 程序自动分析
由于数的值域太大p数组开那么大会爆栈。就用离散化来解决。
边带权并查集
(这是一个难点)
首先先看看模板：
需要的数组有p[N](祖先数组)，d[N](节点x到其根的距离);
//先看0，1边权的(特殊)//
int find(int x)
{
if(p[x]!=x)
{
int root=find(p[x]);
d[x]^=d[p[x]]//其实这里就相当于d[x]+=d[p[x]]
//值得注意的是常犯的错误是写成d[x]^=d[root];root是根所以d[root]一定为0;
p[x]=root;
}
}
且这种0，1边权的有点与传递闭包相似(具有传递性)所以用到了异或;
例题：奇偶游戏（239题)
运用奇数加奇数是偶数，偶数加奇数是奇数可得相同类型的数相减所得为偶数，不相同的相减
则为奇数。所以用1表示两个数不同，用0表示两个数不同。
普通模板：(不再具有传递性)//也不一定，可以模上一个数就能重新有了（比如食物链那道题）
int find(int x)
{
if(p[x]!=x)
{
int root =find(p[x]);
d[x]+=d[p[x]];
p[x]=root;
}
return p[x];
}
//例题食物链(题号：240)
int find(int x)
{
if(p[x]!=x)
{
int root =find(p[x]);
d[x]=(d[x]+d[p[x]]+3)%3;//取模是为了控制大小。
p[x]=root;
}
}
if(pa!=pb&&(d[x]-d[y]+3)%3!=1)//若是没取模d[x]-d[y]即使加上了3也可能是负数所以！=1就会判断错误，当然不取模的话就可以写成(d[x]-d[y]-1)%3这样就算是负数也会判断。
树状数组
这种数据结构是为了把对前缀和的构造和查询都控制在logn的范围内
模板：
int lowbit(int x)
{return x&-x;
}
int ask(int x)
{
int sum=0;
for(int i=x;i>0;i-=lowbit(i))
{
sum+=t[i];
}
return sum;
}
void add(int x,int k)
{
for(int i=x;i<=n;i+=lowbit(i))
{
t[i]+=k;
}
}
最容易犯得错误是写成i+=lowbit(x);
例题：楼兰图腾(题号：241)
边遍历边加入就可以知道自己左边的元素与自己的关系；
但这题不用反着跑一遍了。
然后树状数组最容易用在对差分数组的优化上
比如例题：一个简单的整数问题 1（题号242）
对某一段区间加上减去一个数用差分，但这题还有询问，没次询问要是不优化那就是o(n)级别
那整体最坏时间复杂度就是o(n^2)，这是过不了这题的。
所以用树状数组优化将询问的复杂度降为long(n)，总时间复杂度就是nlongn;
那么如何在此基础上对某一区间求和呢？
例题：一个简单的整数问题2(题号243)
就需要构造所需的数组
迷一样的牛 这道题从后遍历是关键，但其实这道题我觉得有点难的。
//打个星号下次再刷
