数据结构：
1，栈：
栈是一种线性数据结构（LIFO）
栈可以用数组模拟，STL也有
数组模拟：
int skt[N];
int tt;
skt[++tt]=x;//插入元素X
while(tt>0)
tt--;//当不空时，弹出；
skt[tt];//栈顶；
STL:
#include<stack>
stack<int>stk1;
stk1.top();//返回栈顶
stk1.push();//向栈顶插入元素
while(!stk1.empty())==while(stk1.size()!=0)
stk1.pop();//弹出栈顶
然后就没什么了，RT：
题目描述：给出两个序列，第一个序列入栈，判断出栈序列是否可能是第二个
思路：这个还是非常容易想到的，因为LIFO，所以出栈顺序就是入栈顺序调过来，可以通过数组模拟，STL也可，我是混着写的；
#include<iostream>
#include<stack>
using namespace std;
stack<int>a;
int T,tt;
int poped[1000001],pushed[1000001];
int main()
{
cin>>T;
while(T--)
{
int n;
int num=1;
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>pushed[i];
}
for(int i=1;i<=n;++i)
{
cin>>poped[i];
}
for(int i=1;i<=n;++i)
{
a.push(pushed[i]);
while(a.top()==poped[num])//因为a是实时加入元素
{
a.pop(),num++;
if(a.empty())
break;
}
}
if(a.empty())
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
while(!a.empty())
a.pop();
}
return 0;
}
这个是板子题，然后引入单调栈:
顾名思义，就是满足单调性的栈结构，以单调-为例:
栈中元素初始为81,45,11，0，插入14，那么14>0&&14>11，破坏了我们的单调栈，所以0,11就要让路，让14进去
代码：
stack<int>a;
int x;//插入元素
while(!a.empty()&&a.top()<x)
a.pop();
a.push(x);
思路：维护一个单调递减栈，因为需要一个数后面的一个数为答案，那么我们就要从后向前遍历，最后倒序输出，
我们stack一个q，是我们需要维护的栈，因为是要正序输出，而我们倒叙遍历，那就开一个f[]，来存答案，然后就把上面那个单调栈板子糊上去就行了，注意是输出下标；
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
const int N=1e7;
int f[N],a[N];
stack<int>q;
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=n;i>=1;i--)
{
while(!q.empty()&&a[q.top()]<=a[i])
q.pop();
if(q.empty())
f[i]=0;
else
f[i]=q.top();
q.push(i);
}
for(int i=1;i<=n;++i)
printf("%d ",f[i]);
return 0;
}
嫦娥六号任务计划5月3日发射，对此，作为一个具有强烈家国意识的hsez人，我们感到无比的骄傲和自豪，
水绿题，也是用到单调栈，我们维护一个高度的单调栈，如果说我们将要入栈的元素大于了栈顶元素，那要入栈的元素的后面的元素就不会接收到栈顶的能量了，那将要入栈的那个元素就会接收到栈顶元素的能量，然后将栈顶弹出，如果栈中元素没弹空，那就说明当前处理后的栈顶元素就满足单调性了，即大于入栈元素，那栈顶元素就会接收到入栈元素的能量，对应都存在a[]中，最后遍历一遍取max，
代码：
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
stack<int>q;
const int N=1e7;
int v[N],h[N];
int a[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;++i)
scanf("%d%d",&h[i],&v[i]);
for(int i=1;i<=n;++i)
{
while(!q.empty()&&h[q.top()]<h[i])
a[i]+=v[q.top()],q.pop();
if(!q.empty())
a[q.top()]+=v[i];
q.push(i);
}
int maxx=0;
for(int i=1;i<=n;++i)
maxx=max(maxx,a[i]);
printf("%d",maxx);
}
2，队列：
队列是一种具有先进先出性质的表（FIFO）
和栈一样，可以用数组模拟，STL也有
数组：
int q[];
int be=1,en;//队首和队尾
int x;//插入的元素
q[++en]=x;//插入元素，队尾
be++;//删除队首元素
be=1,en=0;//清空队列
STL:
#include<queue>
queue<int>q;
q.front()//返回队首元素
q.back()//返回队尾元素
int x;
q.push(x);//插入
q.pop();//弹出队首
q.empty();//队列是否为空
q.size();//元素数量
还有一种冷门写法，双栈模拟队列，有兴趣自己去看；
还有双端队列，顾名思义，支持双端操纵的队列，支持队首和队尾的插入和删除操作，那么我们用数组模拟就和上面一样了，但是STL中也有：
deque<int>q;
q.front()//返回队首
q.back()//返回队尾
int x;//插入的元素
q.push_back(x)//在队尾插入元素
q.push_front(x)//在队首插入元素
q.pop_back()//弹出队尾元素
q.pop_front()//弹出队首元素
int pos,n,elem,be,en;
q.insert(pos,elem)//在pos位置插入一个elem元素，返回新数据位置
q.insert(pos,n,elem)//在pos位置插入n个elem元素，无返回值
q.insert(pos,be,en)//在pos位置插入【be,en）区间的数据，无返回值
q.clear()//清空
q.erase(be,en)//删除【be,en）区间的数据，返回下一个数据的位置
q.erase(pos)//删除pos位置数据，返回下一个数据位置
引入单调队列：
和单调栈一样，就不举例子了，
滑动窗口，单调队列的典：
思路：对于最大值和最小值，分别维护一个单增和单减的单调队列，输出队首就x刑了：
代码：
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e7;
int a[N],q[N];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
int hh=1,tt=0;
for(int i=1;i<=n;++i)
{
while(hh<=tt&&i-k>=q[hh])
hh++;
while(hh<=tt&&a[q[tt]]>=a[i])
tt--;
q[++tt]=i;
if(i>=k)
printf("%d ",a[q[hh]]);
}
puts(" ");
hh=1,tt=0;
for(int i=1;i<=n;++i)
{
while(hh<=tt&&i-k>=q[hh])
hh++;
while(hh<=tt&&a[q[tt]]<=a[i])
tt--;
q[++tt]=i;
if(i>=k)
printf("%d ",a[q[hh]]);
}
}
应该还有，但我只做了这两道
思路：将所有水滴按照x 坐标排序之后，题意可以转化为求一个 x 坐标差最小的区间使得这个区间内 y坐标的最大值和最小值之差至少为 D;
我们还是用单调队列，维护一个单增和单减队列，然后在【L,R】中，固定L，我们发现随着R的右移，单增中的最大值越来越大，单减的同理，所以我们要找到第一个R，使得单增最大-单减最小>=D
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,d;
const int N=1e8;
struct node{
int x,y;
}a[N];
int qz[N],qj[N];
const int inf=1e9;
bool cmp(node b,node c)
{
return b.x<c.x;
}
int main()
{
cin>>n>>d;
for(int i=1;i<=n;++i)
scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+1+n,cmp);
int sz=1,sj=1,ez=0,ej=0;
int ans=inf;
for(int i=1,r=0;i<=n;++i)
{
while(sz<=ez&&qz[sz]<i)
sz++;
while(sj<=ej&&qj[sj]<i)
sj++;
while(a[qj[sj]].y-a[qz[sz]].y<d&&r<n)
{
r++;
while(sz<=ez&&a[qz[ez]].y>a[r].y)
ez--;
qz[++ez]=r;
while(sj<=ej&&a[qj[ej]].y<a[r].y)
ej--;
qj[++ej]=r;
}
if(a[qj[sj]].y-a[qz[sz]].y>=d)
ans=min(ans,a[r].x-a[i].x);
}
if(ans==inf)
cout<<-1;
else
cout<<ans;
return 0;
}
3,并查集
并查集是一种用于管理元素所属集合的数据结构；
并查集有两种操作，合并和查询：
查询：
int find(int x)
{
if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
合并：
if(find(x)!=find(y))
p[find(x)]=find(y);
还有初始化！！！：
for(int i=1;i<=n;++i)
p[i]=i;
先上一道板子：
思路非常简单，用并查集，然后按照题目要求写就行了：
#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int z,x,y;
int p[100001];
int find(int x)
{
if(p[x]!=x)
p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
p[i]=i;
while(m--)
{
cin>>z>>x>>y;
if(z==1)
{
if(find(x)!=find(y))
p[find(x)]=find(y);
}
else
{
if(find(x)==find(y)){
printf("Y");
puts(" ");
}
else
{
printf("N");
puts(" ");
}
}
}
return 0;
}
思路：首先,考虑暴力做法，两个for循环，按题目描述来写，应该是O($n^{2}$)肯定是会T的，考虑优化，我们可以先将b之前的素数筛出来，在筛的过程中，j因为是i的倍数所以GCD（i,j）==i，那么只需要i大于mod，那么就可以i,j所在集合合并，然后从a遍历到b，将i的父节点放入set中，这样就会自动去重，最后输出集合中元素个数；
代码：
#include<iostream>
#include<set>
using namespace std;
const int N=1e7;
int a,b,mod;
int p[N],prime[N];
set<int>q;
int find(int x)
{
if(p[x]!=x)
p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>a>>b>>mod;
for(int i=1;i<=b;++i)
p[i]=i;
for(int i=2;i<=b;++i)
{
if(!prime[i])
{
for(int j=2*i;j<=b;j+=i)
{
prime[j]=1;
if(i>=mod&&find(i)!=find(j))
p[find(i)]=find(j);
}
}
}
for(int i=a;i<=b;++i)
q.insert(find(i));
cout<<q.size();
return 0;
}
思路：为了保住局长的乌纱帽，我们必须知道，敌人的敌人就是朋友，我们需要让一对敌人中的两人各自去和对方的敌人去一个监狱，为了是最大怒气值最小，先将怒气值从大到小排序，然后先让怒气值大的避开，然后看一对敌人中两人，在和之前安排不冲突情况下，我们能将二人分开就分开，如果两人已经安排在一个监狱了，那就冲突了，不冲突就将各自与对方仇人安排在一起；
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
const int N=1e7;
int vis[N];
struct node{
int a,b,val;
}q[N];
int p[N];
int find(int x)
{
if(p[x]!=x)
p[x]=find(p[x]);
return p[x];
}
bool cmp(node w,node e)
{
return w.val>e.val;
}
void h(int x,int z)
{
if(find(x)!=find(z))
p[find(x)]=find(z);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
p[i]=i;
for(int i=1;i<=m;++i)
scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].val);
sort(q+1,q+1+m,cmp);
for(int i=1;i<=m+1;++i)
{
if(find(q[i].a)==find(q[i].b))
{
printf("%d",q[i].val);
return 0;
}
if(vis[q[i].a]==0)
vis[q[i].a]=find(q[i].b);
else
h(vis[q[i].a],q[i].b);
if(vis[q[i].b]==0)
vis[q[i].b]=find(q[i].a);
else
h(vis[q[i].b],q[i].a);
}
return 0;
}
注意是m+1，提防0的情况，因为如果前面就2组数据，那就没进行合并操作，就没有输出，到m+1就可以了（只有第一组是0）
4,哈希表：
哈希表又称散列表，一种以[key-value]形式存储数据的数据结构。
大家都会字符串哈希，就是给每个字符串以一种特殊命名方式来赋予身份，一般情况下都是一样对应的，哈希表也差不多，
图：
我们需要定义一个哈希函数，来给每个key赋值，假设我们用数组 a 存放数据，哈希函数是 f，那键值对 (key, value) 就应该放在 a[f(key)] 上。不论键值是什么类型，范围有多大，f(key) 都是在可接受范围内的整数，可以作为数组的下标。
比较常见的是key为整数，当key较小时，可以直接把key作为数组下标，范围较大时，就把key%一个较大质数。还比较常见的是key为字符串，我们直接计算出key的哈希值，然后作为下标；
但是有时会发生碰撞，
5，ST表：
ST表是用于解决可重复贡献问题的数据结构：
ST表是基于倍增思想，以板子为例：
ST表:
给定一个长度为N的数列，和M次询问，求每一次询问区间的最大值：
思路：首先，他给的区间是有重复的（左右端点），那么肯定会有重复最大值，那么就是可重复贡献问题，那么就用ST表写上面说了，基于倍增思想，也就是每次跳2的几次方，以第一篇题解的图为例，我们就推出了转移方程，完成了预处理，接着求最值
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=1e6+10;
int n,m,l,r;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int f[N][25];
int q(int l,int r)
{
int k=log2(r-l+1);
return max(f[l][k],f[r+1-(1<<k)][k]);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;++i)
f[i][0]=read();
for(int j=1;j<=21;++j)
{
for(int k=1;k-1+(1<<j)<=n;++k)
{
f[k][j]=max(f[k][j-1],f[k+(1<<(j-1))][j-1]);
}
}
for(int i=1;i<=m;++i)
{
l=read(),r=read();
printf("%d",q(l,r));
puts(" ");
}
}
6，树状数组:
树状数组是一种支持单点修改和区间查询的，主要代码量小:
也是以板子题为例：
树1，树2：
这个是单点修改，区间查询，暴力做法单点修改O(1)，区间查询O($n^{2}$),一般是会T的，而对于树状数组来说，时间复杂度可以降到O(nlogn)；
接下来是原理：
我们可以发现，节点x的父节点为x+lowbit(x)，例如，t[6]=t[5+lowbit(5)],t[8]=t[7+lowbit(7)]=t[6+lowbit(6)]......；
那么单点修改就简单了，如果我们对啊a[1]+k,那么他的父节点都需被更新，也就是i+lowbit(i)：
void add(int x,int k)
{
for(int i=x;i<=n;i+=lowbit(i))
t[i]+=k;
}
区间查询：
由图可得，例如前7项的和，那么s[7]=t[7]+t[6]+t[4],我们发现，6=7-lowbit(7),4=6-lowbit(6),那么这只是[1,R]的和，我们是要求[L,R]的和，只需要用[1,R]-[1,L-1]就可以了，
void query(int x,int y)
{
for(int i=x-1;i;i-=lowbit(i))
ans-=t[i];
for(int i=y;i;i-=lowbit(i))
ans+=t[i];
}
那么这道题就解决了：
#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int ans;
int t[100000001];
#define lowbit(x) x&(-x)
void add(int x,int k)
{
for(int i=x;i<=n;i+=lowbit(i))
t[i]+=k;
}
void query(int x,int y)
{
for(int i=x-1;i;i-=lowbit(i))
ans-=t[i];
for(int i=y;i;i-=lowbit(i))
ans+=t[i];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
{
int q;
cin>>q;
add(i,q);
}
while(m--)
{
int op,x,y,k;
cin>>op;
if(op==1)
{
cin>>x>>k;
add(x,k);
}
else
{
cin>>x>>y;
ans=0;
query(x,y);
cout<<ans;
puts(" ");
}
}
return 0;
}
接下来看区间修改，单点查询，
区间修改就需要用到查分数组，例如对[L,R]+k，那么我们只需更新差分数组add(L,K),add(R+1,-k)，这是差分数组的性质；
那么单点查询就求出差分数组的前缀和，这也是差分数组一个性质;
也就是说，这道题的关键，就是用树状数组维护一个差分数组；
#include<iostream>
#include<cstdio>
using namespace std;
#define lowbit(x) x&(-x)
const int N=1e8;
int a[N],b[N],c[N];
int ans;
int n,m;
void add(int x,int k)
{
for(int i=x;i<=n;i+=lowbit(i))
a[i]+=k;
}
void query(int cnt)
{
for(int i=cnt;i;i-=lowbit(i))
ans+=a[i];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
{
cin>>b[i];
c[i]=b[i]-b[i-1];
add(i,c[i]);
}
while(m--)
{
int op,x,y,k;
cin>>op;
if(op==1)
{
cin>>x>>y>>k;
add(x,k);
add(y+1,-k);
}
else
{
cin>>x;
ans=0;
query(x);
cout<<ans;
puts(" ");
}
}
return 0;
}
例题：
逆序对：
思路：这道题就是求给出的序列中，在x 前面且比x大的数有几个，然后累加，首先这道题数据比较大，我们需要离散化，我们将原序列按照值的从小到大排，然后枚举序列中每个位置的数，统计有多少比他的大的数出现，然后累加，就可以了，也就是树1单点查询+区间修改的模板；
#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
const int N=1e7;
struct node{
int val,num;
}a[N];
int r[N];//离散化用
int n;
int t[N];
int ans;
#define lowbit(x) x&(-x)
void add(int x)
{
for(int i=x;i<=n;i+=lowbit(i))
t[i]++;
}
int query(int x)
{
int ans=0;
for(int i=x;i;i-=lowbit(i))
ans+=t[i];
return ans;
}
bool cmp(node q,node w)
{
if(q.val==w.val)
return q.num<w.num;
return q.val<w.val;
}
signed main()
{
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>a[i].val;
a[i].num=i;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;++i)
r[a[i].num]=i;//离散化
for(int i=1;i<=n;++i)
{
ans+=query(n)-query(r[i]);
add(r[i]);
}
cout<<ans;
}
7，堆：
堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆，priority_queue就是大根堆
二叉堆：
从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存有一个元素（或者说，有个权值）。
堆性质：父亲的权值不小于儿子的权值（大根堆）。同样的，我们可以定义小根堆。本文以大根堆为例。
由堆性质，树根存的是最大值，所以取最大值时拿出堆顶就行了；
过程：
插入：
最简单方法就是，从最下层最右边叶子后插入，如果最下层已满，就另起一层，这时，我们无法保证要插入的数是小于等于父节点的，所以说，我们需要向上调整，顾名思义，就是向上换，知道满足堆得性质后，停止，动图，向上调整的时间复杂度是O(logn)的。
删除：
删除最大值，也就是删除堆顶，那删之后就会变成两个堆，不可取，我们考虑插入的逆过程，将堆顶与最后一个节点交换，然后删除最后一个节点，但是我们发现，操作后，它又不满足大根堆的性质了，所以我们还需要向下调整（时间复杂度O(logn)），也就是将当前节点与子节点中最大的换，为什么是最大的呢，因为我们需要保证，换完后，父节点是大于子节点的，所以说删除操作就完成了；
增加某个点的权值：
这个不难操作，只需要修改后，向上或向下调整即可，时间复杂度也是O(logn)的
先看 板子：
堆：
这道题需要维护一个小根堆，因为它都是对最小值操作：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int heap[1000001];
int size;
void insert(int x)
{
heap[++size]=x;
int now=size;
while(now)
{
int nxt=now>>1;
if(heap[nxt]>heap[now])
swap(heap[nxt],heap[now]);
else
break;
now=nxt;
}
}
void del()
{
swap(heap[1],heap[size]);
size--;
int now=1;
while(now*2<=size)
{
int nxt=now<<1;
if(nxt+1<=size&&heap[nxt+1]<heap[nxt])
nxt++;
if(heap[nxt]<heap[now])
swap(heap[nxt],heap[now]);
else
break;
now=nxt;
}
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int op,x;
scanf("%d",&op);
if(op==1)
{
scanf("%d",&x);
insert(x);
}
else if(op==2)
{
printf("%d",heap[1]);
puts(" ");
}
else
del();
}
return 0;
}
维护一个序列，支持两种操作：
- 向序列中插入一个元素
- 输出并删除当前序列的中位数（若序列长度为偶数，则输出较小的中位数）
关键就是，动态维护一个序列上第k大的数，k随时变，这就需要引入对顶堆这一操作，对顶堆由一个大根堆和一个小根堆组成，对于这道题，我们需要开一个大根堆，维护前一半元素，即较小部分的值，小根堆维护后一半元素，即较大部分的值，对顶堆支持以下几种操作：
维护：当小根堆的大小小于k时，将大根堆堆顶取出并插入小根堆，知道小根堆大小为K，那么当小根堆大小大于k时，就不断将小根堆堆顶取出，并插入大根堆，直到小根堆大小等于k；
插入元素：若插入的元素大于等于小根堆堆顶元素，则将其插入小根堆，否则将其插入大根堆，然后维护对顶堆
查询第k大元素即为取出小根堆堆顶，删除第k大元素同理；
这道题用对顶堆做就完全没问题了：
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
priority_queue<int,vector<int>,less<int> >maxx;//大根堆
priority_queue<int,vector<int>,greater<int> >minn;//小根堆
int n;
while(scanf("%d",&n)&&n!=0)
{
if(n==-1)
{
printf("%d",maxx.top());
puts(" ");
maxx.pop();
}
else
{
if(maxx.empty()||n<=maxx.top())
{
maxx.push(n);
}
else
{
minn.push(n);
}
}
/*维护对顶堆*/
int size=(maxx.size()+minn.size()+1)/2;
if(maxx.size()>size)
{
minn.push(maxx.top());
maxx.pop();
}
else if(maxx.size()<size)
{
maxx.push(minn.top());
minn.pop();
}
}
}
return 0;
}
左偏树:
左偏树是一种可并堆，具有堆的性质，可以快速merge。
这里需要引入dist：对于一颗二叉树，我们定义外节点为左儿子或右儿子为空的节点，我们定义一个外节点的dist为1，空节点的dist为0，一个不是外节点的dist为其到子树中最近外节点的距离+1。(有点官方)
左偏树是一颗二叉树，它不仅具有堆的性质，并且是左偏的（左偏即每个节点的左儿子的dist都大于右儿子的dist）。
我们上面提到过，用它就是看中它的merge操作了，所以核心是如何merge:以合并后小根堆为例讲：
合并后需满足堆的性质，所以要取两根中较小的为根，然后以这个根的左儿子作为合并后堆的左儿子，按照上述规则将此根的右节点与另一个堆合并，因为需要满足左偏，所以合并后用swap来保证；
实现：
int merge(int x, int y) {
if (!x || !y) return x | y; // 若一个堆为空则返回另一个堆
if (t[x].val > t[y].val) swap(x, y); // 取值较小的作为根
t[x].rs = merge(t[x].rs, y); // 递归合并右儿子与另一个堆
if (t[t[x].rs].d > t[t[x].ls].d)
swap(t[x].ls, t[x].rs); // 若不满足左偏性质则交换左右儿子
t[x].d = t[t[x].rs].d + 1; // 更新dist
return x;
}
也可以在合并时将dist大的作为左儿子，小的作为右儿子，就不需要在swap了；
左偏树除了merge操作，别的也不太一样：
插入：单个节点视为一个堆，合并即可。
删除根节点：合并根的左右儿子，把它父亲跳过去就行了；
板子(luogu上的操作不全，看acwing上的)
``
左偏树还会额外维护一个dis[x],就是x到最近的空节点的距离，边界是叶子dis定义为1，父节点为左右儿子最小值+1，并且严格要求左儿子dis大于右儿子dis，那么父节点的dis显然就是右节点的dis+1了，也就是顾名思义，左偏。
维护左偏树时，还需要维护一个与他对应的并查集，我们以树的根节点作为并查集代表元素；这样的话我们在第二个操作中就可以找x,y分别 在并查集中的代表元素，看是否在同一树中，然后进行操作。那么第三个操作也就更简单了，我们找到x所在并查集中代表元素，也就是根节点，那么它也就是最小值。但是最后一个操作就有问题了，因为在左偏树中，删除根节点很容易，就把这个点的左右节点合并就行了，但并查集不支持删除，那就先不删，把两棵树合并后产生的新的根节点换成并查集的根，也就是将并查集之前的根指向我们合并后的那个元素，然后把将这个元素指向自己，就完成了换根操作。第一个操作就是插入一个左偏树。
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6;
const int inf=2e9;
int val[N],p[N],n,idx,l[N],r[N];
int dis[N];
int find(int x)
{
if(p[x]!=x)
p[x]=find(p[x]);
return p[x];
}
bool cmp(int x,int y)//双关键字排序
{
if(val[x]!=val[y])
return val[x]<val[y];
return x<y;
}
int merge(int x,int y)
{
if(!x||!y)
return x+y;//如果有空集合，直接出输出空集合；
if(cmp(x,y))//x是较小值，也就是作为根节点
r[x]=merge(r[x],y);//将右节点与另一颗树合并
if(dis[r[x]]>dis[l[x]])
swap(r[x],l[x]);//保证满足左偏性质
dis[x]=dis[r[x]]+1;//满足性质后就是右节点最小了，然后dis+1
return x;
}
int main()
{
cin>>n;
val[0]=inf;//在第4个操作用
while(n--)
{
int op,x,y;
scanf("%d",&op);
if(op==1)
{
scanf("%d",&x);
val[++idx]=x;
dis[idx]=1;
p[idx]=idx;//更新
}
else if(op==2)
{
scanf("%d%d",&x,&y);
x=find(x),y=find(y);//先找代表元素
if(x!=y)//不在一颗树里
{
if(!cmp(x,y))
swap(x,y);//保证x最小，做根节点
p[y]=x;
merge(x,y);
}
}
else if(op==3)
{
scanf("%d",&x);
printf("%d",val[find(x)]);//我们一直所维护的根节点最小值
puts(" ");
}
else
{
scanf("%d",&x);
x=find(x);
if(!cmp(l[x],r[x]))
swap(l[x],r[x]);//保证左子树的根做根节点
p[x]=l[x],p[l[x]]=l[x];//换根
merge(l[x],r[x]);
}
}//前面赋的inf是防止空节点作为根节点，因为空节点权值是0，比任何数都小，所以赋极大值以绝后患。
return 0;
}
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
const int N=1e6;
int l[N],r[N],dis[N],val[N],p[N];
int find(int x)
{
if(x!=p[x])
p[x]=find(p[x]);
return p[x];
}
bool cmp(int x,int y)
{
if(val[x]!=val[y])
return val[x]<val[y];
return x<y;
}
int merge(int x,int y)
{
if(!x||!y)
return x+y;
if(!cmp(x,y))
swap(x,y);
r[x]=merge(y,r[x]);
if(dis[l[x]]<dis[r[x]])
swap(l[x],r[x]);
dis[x]=dis[r[x]]+1;
return x;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;++i)
{
int q;
scanf("%d",&q);
dis[i]=1;
val[i]=q;
p[i]=i;
}
while(m--)
{
int op,x,y;
scanf("%d",&op);
if(op==1)
{
scanf("%d%d",&x,&y);
if(!dis[x]||!dis[y])
continue;
x=find(x),y=find(y);
if(x!=y)
{
if(!cmp(x,y))
swap(x,y);
p[y]=x;
merge(x,y);
}
}
else
{
scanf("%d",&x);
if(!dis[x])
{
printf("-1");
puts(" ");
continue;
}
else
{
x=find(x);
printf("%d",val[x]);
puts(" ");
dis[x]=0;
if(r[x]&&!cmp(l[x],r[x]))
swap(l[x],r[x]);
p[x]=l[x],p[l[x]]=l[x];
merge(l[x],r[x]);
}
}
}
return 0;
}
8，线段树：
线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。
线段树是一个满二叉树（画图举个栗子......），所以可以用一个一位数组来存整棵树，标号是x的父节点，就是,左儿子就是2x,右儿子为2x+1，
常见（简单）4个操作：
1，pushup，操作，
2，build操作，将一段区间，初始化为线段树
3，modify，修改单点，修改区间
4，query,查询
板子：
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
const int N=1e7;
int n,m,ans[N],tag[N],a[N];
inline int ls(int x)
{
return 2*x;
}
inline int rs(int x)
{
return 2*x+1;
}
inline void push_up(int p)
{
ans[p]=ans[ls(p)]+ans[rs(p)];
}
inline void build(int p,int l,int r)
{
tag[p]=0;
if(l==r)
{
ans[p]=a[l];
return;
}
int mid=(l+r)/2;
build(ls(p),l,mid);
build(rs(p),mid+1,r);//递归建槊
push_up(p);
}
inline void f(int p,int l,int r,int k)
{
tag[p]+=k;
ans[p]+=k*(r-l+1);
}
inline void push_down(int p,int l,int r)
{
int mid=(r+l)/2;
f(ls(p),l,mid,tag[p]);
f(rs(p),mid+1,r,tag[p]);
tag[p]=0;
}
inline void update(int nl,int nr,int l,int r,int p,int k)
{
if(nl<=l&&nr>=r)
{
f(p,l,r,k);
return;
}
push_down(p,l,r);
int mid=(l+r)/2;
if(nl<=mid)
update(nl,nr,l,mid,ls(p),k);
if(nr>mid)
update(nl,nr,mid+1,r,rs(p),k);
push_up(p);
}
inline int query(int x,int y,int l,int r,int p)
{
int res=0;
if(x<=l&&y>=r)
return ans[p];
int mid=(l+r)/2;
push_down(p,l,r);
if(x<=mid)
res+=query(x,y,l,mid,ls(p));
if(y>mid)
res+=query(x,y,mid+1,r,rs(p));
return res;
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]);
build(1,1,n);
while(m--)
{
int op,x,y,k;
scanf("%lld",&op);
if(op==1)
{
scanf("%lld%lld%lld",&x,&y,&k);
update(x,y,1,n,1,k);
}
else
{
scanf("%lld%lld",&x,&y);
printf("%lld",query(x,y,1,n,1));
puts(" ");
}
}
return 0;
}
