链表
链表是一种本身并不常用的数据结构。
然而其衍生出的许多数据结构如块状链表和链式前项星等却十分甚至九分的常用。
链表
简介
顾名思义，链表就是使用链连接在一起的数组。
可以实现\(O(1)\)的插入,\(O(1)的删除\)和\(O(n)\)的查询。
实现
我们使用一个结构体来实现链表：
struct point{
int val,to;
}
其中\(val\)表示节点的存值，\(to\)表示索引的链。
为了防止无限遍历，我们通常在链表的末端添加一个\(to=-1\)（特殊值）来结束输入。
遍历时，我们跳\(to\)即可。
删除时，我们用这个节点的链连给下一个节点的链。
插入时，我们先动态开点，再将新节点的链连给下一节点，最后用该节点的链连给新节点。
双向链表同理，这里略过。
例题
以下是一个例题：
Vessels
我们考虑建立一个链表来维护每个沙漏，当沙漏装满了之后，就无法承受更多的水，删除这个沙漏即可。
分类讨论：
\(1.\)如果删除：\(O(1)\)均摊。
\(2.\)如果不删除：\(O(1)\)。
综上，总复杂度为\(O(m)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+100;
int n,m;//同题意
int a[N];//初始容量
struct point{
int val,to;
}p[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
p[i].val=a[i];
if(i==n)
p[i].to=-1;
else
p[i].to=i+1;
}
cin>>m;
while(m--)
{
int op;
cin>>op;
if(op==1)
{
int x,y;
cin>>x>>y;
if(p[x].val>=y)
{
p[x].val-=y;
continue;
}
else
{
y-=p[x].val;
p[x].val=0;
}
while(p[x].to!=-1&&y!=0)
{
if(p[p[x].to].val<=y)
{
y-=p[p[x].to].val;
p[p[x].to].val=0;
int ox=x;
x=p[x].to;
p[ox].to=p[x].to;
}
else
{
p[p[x].to].val-=y;
break;
}
}
}
else
{
int x;
cin>>x;
cout<<a[x]-p[x].val<<'\n';
}
}
return 0;
}
块状链表
简介
我们知道，链表拥有\(O(1)\)的插入,\(O(1)的删除\)和\(O(n)\)的查询。
可\(O(n)\)的查询，实在太大了，有没有办法优化呢？
于是，块状链表诞生了。
它十分巧妙的将分块与链表结合。用链表形式连接每一个块。使用合并与分裂维护。实现\(O(\sqrt n )\)的插入,\(O(\sqrt n)的删除\)和\(O(\sqrt n)\)的查询。
最重要的是：
它有\(STL\)啊！！！
实现
块状链表的实现代码冗长，但是我们可以使用\(STL\ rope\)实现。
引用：
#include<ext/rope>
using namespace __gnu_cxx;
rope<type>x;
函数：
\(a.substr(pos,x)\):返回一个\(rope\)类型，而且等于\(a[pos~(pos+x-1)]\)，且两者互不相干。
\(a.erase(pos,x)\)删除\(a[pos~(pos+x-1)]\)，并且把两端拼至一起。
\(a.at(x)\)返回\(a[x]\)(也可以直接索引下标)
\(a.insert(pos,char)\)在\(pos\)位置插入一个字符或者字符数组(\(int\)也可以)。
\(a.replace(pos,x,char)\)把\(a[pos~(pos+x-1)]\)替换为\(char\)(可以是字符数组也可以是\(int\))。
例题
块状链表在实现平衡树和主席树上很有建树。
以下是有关主席树的例题。（可以暴力72分）
P3919 【模板】可持久化线段树 1（可持久化数组）
代码：
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int N=1e6+100;
int n,m;
int a[N];
int l;
rope<int>p[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
p[0].push_back(a[i]);
}
while(m--)
{
int w,op;
cin>>w>>op;
if(op==1)
{
int loc,val;
cin>>loc>>val;
p[++l]=p[w];
p[l].replace(loc-1,1,val);
}
else
{
int loc;
cin>>loc;
p[++l]=p[w];
cout<<p[l].at(loc-1)<<'\n';
}
}
return 0;
}
记录：
link
栈
栈
简介
栈是一种后进先出的数据结构。可以说是数据结构中最为朴实的了。
实现
栈的实现有两种。
一：
一是可以使用\(STLstack\)实现。
\(stack\)的函数有以下几种：
\(push(x)：\)向栈中加入一个数 \(x\)。
\(pop()：\)将栈顶弹出。
\(query()：\)输出栈顶元素。
\(size()：\)输出此时栈内元素个数。
二：
二是手写栈。
只需要一个栈顶指针\(l\)。
以及数组\(z\)即可实现。
模板
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=1e6+100;
int l,t,q;
ull a[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
l=0;
cin>>q;
while(q--)
{
string s;
cin>>s;
if(s=="push")
{
ull x;
cin>>x;
a[++l]=x;
}
if(s=="pop")
{
if(l==0)
cout<<"Empty"<<'\n';
else
l--;
}
if(s=="query")
{
if(l==0)
cout<<"Anguei!"<<'\n';
else
cout<<a[l]<<'\n';
}
if(s=="size")
{
cout<<l<<'\n';
}
}
}
return 0;
}
单调栈
简介
单调栈旨在维护前缀的后缀最值。
实现
单调栈的实现旨在维护一个储存前缀的后缀最值的栈。
当新的元素破坏了最值之后，弹出被破坏的值。
任在栈内的元素即为当前前缀的后缀随值。
模板
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
int n;
ull a[1000001];
ull ans;
stack<int>z;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
while(z.size()!=0&&a[i]>=a[z.top()])
{
ans^=z.top();
z.pop();
}
z.push(i);
ans^=i;
cout<<ans<<endl;
}
return 0;
}
队列
队列
简介
队列是一种非常简单的数据结构，本质上是一个先进先出的数组。
实现
队列的实现十分甚至九分的简单。
我们使用\(STL\ queue\)。
queue<type>q;
q.push(x);//入队
q.pop(x);//出队
q.front();查询队首
q.size();查询队列元素数量
没了。
例题
代码：
B3616 【模板】队列
代码：
#include<bits/stdc++.h>
using namespace std;
queue<int>q;
int n;
int main()
{
cin>>n;
while(n--)
{
int op;
cin>>op;
if(op==1)
{
int x;
cin>>x;
q.push(x);
}
if(op==2)
{
if(q.size()!=0)
q.pop();
else
cout<<"ERR_CANNOT_POP"<<'\n';
}
if(op==3)
{
if(q.size()!=0)
cout<<q.front()<<'\n';
else
cout<<"ERR_CANNOT_QUERY"<<'\n';
}
if(op==4)
{
cout<<q.size()<<'\n';
}
}
return 0;
}
双端队列
简介
双端队列的特点是可以两边入队，两边出队。
实现
我们通常使用\(STLdeque\)实现。
该\(STL\)有以下函数：
\(push\_back(x)：\)在双端队列中从尾部插入一个元素 \(x\)；
\(pop\_back()：\)在双端队列中从尾部弹出一个元素。
\(push\_front(x)：\)在双端队列中从头部插入一个元素 \(x\)；
\(pop\_front()：\)在双端队列中从头部弹出一个元素。
\(size()：\)查询双端队列的元素个数；
\(front()：\)查询双端队列的队首元素；
\(back()：\)查询双端队列的队尾元素；
额外的：
如果只需使用上面的操作我们可以使用\(list\)代替\(deque\)，速度更快，空间更小。（尽管他是双向链表）
模板
B3656 【模板】双端队列 1
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
list<int>que[N];
int q;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>q;
while(q--)
{
string op;
cin>>op;
if(op=="push_back")
{
int x,y;
cin>>x>>y;
que[x].push_back(y);
}
if(op=="pop_back")
{
int x;
cin>>x;
if(!que[x].empty())
que[x].pop_back();
}
if(op=="push_front")
{
int x,y;
cin>>x>>y;
que[x].push_front(y);
}
if(op=="pop_front")
{
int x;
cin>>x;
if(!que[x].empty())
que[x].pop_front();
}
if(op=="size")
{
int x;
cin>>x;
cout<<que[x].size()<<'\n';
}
if(op=="front")
{
int x;
cin>>x;
if(!que[x].empty())
cout<<que[x].front()<<'\n';
}
if(op=="back")
{
int x;
cin>>x;
if(!que[x].empty())
cout<<que[x].back()<<'\n';
}
}
return 0;
}
单调队列
简介
单调队列是基于双端队列实现的数据结构，旨在维护区间后缀最值。
思路与单调栈类似，不同的是，因为维护的是区间，所以还要考虑左端点的范围限制，这里不再赘述。
模板
B3667 求区间所有后缀最大值的位置
(扶苏的模板就是好，总是能揭示算法本质。不像某k，某zhe的模板，一堆诈骗)
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=1e6+100;
int n,k;
ull a[N];
list<int>que;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<k;i++)
{
while(!que.empty()&&a[i]>=a[que.back()])
que.pop_back();
que.push_back(i);
}
for(int i=k;i<=n;i++)
{
if(!que.empty()&&que.front()<=i-k)
que.pop_front();
while(!que.empty()&&a[i]>=a[que.back()])
que.pop_back();
que.push_back(i);
cout<<que.size()<<'\n';
}
return 0;
}