一，链表（链式存储结构）
是由一系列结点组成是用一组非连续的储存单元来存储节点数据并且链表的长度不是固定的。
每个结点包含两个部分（数据域和指针域）
1、单链表（以下都是用数组模拟，仅供参考）
定义：
void init(){
r[0]=1;
idx=1;
}
插入：
void add(int x){
e[idx]=x;
r[idx-1]=idx;
r[idx]=-1;
idx++;
}
删除：
void dele(int id){
r[id]=r[r[id]];
}
遍历：
int u=0;
while(r[u]!=-1){
…
u=r[u];
}
2、循环链表（顾名思义就是整个链表是“连着”的）
变成循环链表：
r[1]=0;
3、双向链表：
双向链表每个节点有两个指针域和若干个数据域，其中一个指针域指向他的前驱结点，另外一个指向他的后继结点。
定义：
void init(){
r[0]=1;
l[1]=0;
idx=2;
}
插入：
void add(int k,int x){
e[idx]=x;
r[idx]=r[k];
l[idx]=k;
l[r[k]]=idx;
r[k]=idx;
idx++;
}
删除：
void dele(int k){
r[l[k]]=r[k];
l[r[k]]=l[k];
}
遍历：
int u=0;
while(r[u]!=-1){
…
u=r[u];
}
二：数据结构与STL:
c++提供了标准模板库（STL）其中封装了非常实用的容器，十分方便。以下是其中的一些容器。
1、栈：
又称为堆栈是只在某一端插入和删除的特殊线性表，具有先进后出的特性。
定义：
stack name;
例如stack a;
基本函数：
push(x):将x入栈。
pop():弹出栈顶元素。
top():获取栈顶元素。
empty():判断是否为空，true为空，false为非空。
size():返回栈内元素个数。
2、队列：
遵循先进先出的原则，队列是线性表的一种在操作数据元素时，和栈一样，有自己的规则使用队列存取元素时，数据元素只能从表的一端进入队列，另一端出队列。
定义：
queue name;
例如queue q;
基本函数：
push(x):将x入队。
pop():将队首元素出队。
front():获取队首元素。
back():获取队尾元素。
empty():判断是否为空，true为空，false为非空。
size():返回队列内元素个数。
优先队列：
队列中优先级最大的永远位于队首。
定义：
priority_queue<int,vector,greater >q;//注意greater后面有空格
priority_queue<int,vector,lesss >q;=priority_queue q//注意less后面有空格
//递增greater函数排序：q.top()可访问队列最小值
//递增less函数排序：q.top()可访问队列最大值
基本函数：
push(x):将x入队。
pop():将队首元素出队。
top():获取队首元素。
empty():判断是否为空，true为空，false为非空。
size():返回队列内元素个数。
3、动态数组vector:(长度可以根据需要而改变)
定义:
vector name;
例如vector a;
vector一般有两种访问方式：
通过下标：
for(int i=0;i<a.size();i++){
cout<<a[i];
}
通过迭代器：
for(vector::iterator it=a.begin();it!=a.end();it++){
cout<<*it;
}
常见函数请向下翻
4、集合set：(自动去重，自动排序)
定义：
set name;
例如set a;
set只能通过迭代器访问：
for(set::iterator it=a.begin();it!=a.end();it++){
cout<<*it;
}
常见函数请向下翻
5、映射map:(他可以将任何基本类型映射到任何基本类型)
定义：
map<typename,typename> a;
//键 //值
例如map<string,int> a;
map一般有两种访问方式：
通过键访问：
a[“abc”]++;
cout<<a[“abc”]<<endl;
通过迭代器访问：
for(map<string,int>::iterator it=a.begin();it!=a.end();it++){
cout<first<<’ '<second;
//键 值
}
常见函数请向下翻
三、尺取、拆分、前缀和：
1、一维前缀和：
sum[i]=sum[i-1]+a[i];
2、二维前缀和：
sum[i][j]=sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1];
3、一维拆分：
while(m–){
scanf(“%lld%lld%lld”,&a,&b,&c);
d[a]+=c;
d[b+1]-=c;
}
for(int i=1;i<=n;i++){
d[i]=d[i-1]+d[i];
printf("%lld ",d[i]);
}
4、二维拆分：
for(int i=1;i<=m;i++){
cin>>a1>>b1>>c1>>d1;
a[a1][b1]+=1;
a[c1+1][d1+1]+=1;
a[c1+1][b1]-=1;
a[a1][d1+1]-=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];
}
}
5、双指针：
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
while(r<=n){
if(sum<m){
sum+=a[r];
r++;
}
if(sum>m){
sum-=a[l];
l++;
}
if(sum==m){
minn++;
sum-=a[l];
l++;
}
}
cout<<minn<<endl;
return 0;
}
map:
set:
vector:
