数据结构、前缀和、差分与离散化
Tobeconfirmed · · 个人记录
链表
简单介绍
链表分为单向链表和双向链表，
单向链表即当前链表只指向下一个元素，
双向链表即对于每个元素，记录其前面一个元素，也记录其后面一个元素。
链表不建议使用 STL 的某些元素进行替代，手写链表更为方便。
单向链表：实现
单向链表：维护每个元素编号，然后维护 nx 指针，表示当前元素的下一个元素是谁加入和删除都是方便的
单向链表：例题
洛谷B3631
单向链表：前项星
本质上前项星是由多个单项链表组成，维护链头数组，然后可以支持每个点加边。
例题
洛谷 P3916 图的遍历
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int xx=1e5+5;
struct node{
int next,to;
}e[xx<<1];
int cnt,h[xx];
void add(int x,int y){
cnt++;
e[cnt]={h[x],y};
h[x]=cnt;
}
int ans[xx],id;
void dfs(int x)
{
if(!ans[x])ans[x]=id;
else return;
for(int i=h[x];i;i=e[i].next)
dfs(e[i].to);
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
add(b,a);
}
for(int i=n;i>=1;i--)id=i,dfs(i);
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
return 0;
}双向链表：实现
每个元素维护前驱 pr 和后继 nx 两个数组，可以实现动态增删的操作
栈
简单介绍
一种结构，维护一个序列，每次从末端加入元素，然后末端弹出元素。
具体维护：使用一个数组，维护一个 tp 指针进行处理：
另一种实现
在搞懂原理之后，我们可以用 STL 简化我们的实现：
例题
洛谷 B3614
单调栈
本质上是用栈维护了单调的结构，例题：
给定一个长度为 n 的数列 ai 然后，对于每个元素，找到在这个元素之后，第一个大于当前元素的下标。
洛谷 P5788
从后往前枚举，栈内维护单调的下标，满足这些下标的值是递减的，id也是递减的，由于满足单调的过程，我们称为单调栈。
我们举例子说明一下：
5
14 2 3 5
8
89 1 8 2 3 3 10
关键性质在于保留对当前状态最优的信息。
队列
简单介绍
一种结构，维护一个序列，每次从末端加入元素，然后前端弹出元素。
具体维护，用一个数组，维护前端后端指针，维护加入删除。
在搞懂原理之后，我们可以用 STL 简化我们的实现：
洛谷 B3616
单调队列
例题：滑动窗口
洛谷 P1866
类比与单调栈，我们也有单调队列，满足这个队列中，（比如求最大值）
权值是递减的，但是 id 是递增的，有单调性质。
关键性质同样是保留对于当前而言更优的一个信息。
为什么权值递减？因为我们要求目前最大值，为什么 id 递增？我们有id 大于某个位置的限制。
简单介绍
一种结构，维护一个序列，每次加入一个元素，询问当前序列中最小的元素，然后删除最小元素。
具体维护，我们一般维护的称为二叉堆，即维护一个结构，支持上述处理过程。
每个节点 i 储存一个权值，左儿子是 2 ∗ i，右儿子是 2 ∗ i +1。
这里展示删除操作
不是特别需要记住，理解原理即可
简单实现
在搞懂原理之后，我们可以用 STL 简化我们的实现：
洛谷 B3616
对顶堆
一个序列，我们每次加入一个元素，或者进行询问。
维护一个初始指针 i=0，每次询问的时候将 i=i+1 然后询问第 i 小的值是多少。
洛谷 P1801
使用两个堆，把序列分为前半和后半，分界点位置就是我们尝试输出的值。
哈夫曼树
例题
这是在堆的基础上的一点点贪心的扩展：以一道经典的问题引入：
[NOIP2004 提高组] 合并果子：
你有 n 堆果子，第 i 堆初始为 ai 大，然后你需要做 n − 1 次操作，每次选择两堆果子，将其合并为一堆，即删除原来两堆 i, j 变成新堆 ai + aj，并消耗新堆大小的体力，问：最少消耗体力。
详解
可能各位同学也有了解，可以选择最小的两堆合并，并一直执行这个过程，贪心的想法是明确的，因为先合并意味着可能会先做贡献。
将这个合并过程建树，这棵树称为哈夫曼树！
洛谷 P1090
性质：
每个数贡献的次数是他到根的边数。
数大的贡献较少，即经过的边数较少。
如果把边顺次标号为 0, 1，则每个叶子到根的一个字符串称为哈夫曼编码。
扩展！如果我们每次选择至多 3 堆果子进行合并，结果会是怎样？
这里请各位同学观察 1,2,4,5,6,7 这个例子。
你们觉得这样优吗？
换一种描述方式，各位同学可以明显的发现，刚才的过程并不优！
所以多叉的哈夫曼树同样涉及到一个补 0 的贪心思想。
具体的，补其 0 使得 n − 1 mod (k − 1) = 0。
[NOI2015] 荷马史诗
说：给定 n 个单词的出现次数，请你用字符集大小为 k 的字符串来替换每个单词，
使得每个单词的出现次数乘对应字符串的长度最小，你需要满足要求：
对于任意两个单词对应的字符串不应该有前缀包含关系，比如 abbc 前缀包含 abb。
注意到，没有前缀包含关系完全对应了哈夫曼编码，而我们最优化次数正好是哈夫曼树的最小的贡献！
所以我们建立扩展的 k 叉哈夫曼树即可得到答案。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read()
{
char c;
int w=1;
while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
int ans=c-'0';
while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
return ans*w;
}
priority_queue<pair<int,int> >q;
int a[5000005];
int n;
int k;
signed main(){
n=read();
k=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
q.push(make_pair(-a[i],-1));
}
while((n-1)%(k-1))n++,q.push(make_pair(0,-1));
int anss=0;
for(int i=1;i<=(n-1)/(k-1);i++)
{
int ans=0;
int maxx=0;
for(int j=1;j<=k;j++)
{
ans+=(-q.top().first);
maxx=max(maxx,-q.top().second);
q.pop();
}
anss+=ans;
q.push(make_pair(-ans,-maxx-1));
}
cout<<anss<<endl<<-q.top().second-1<<endl;
return 0;
}
P2168 荷马史诗
STL
简单介绍
STL 是 C++ 标准库的一部分，包含了很多数据结构和算法，我们可以直接调用这些函数来解决问题。
比如说，我们可以直接调用 vector 来解决动态开数组的问题，调用 set来解决集合（有序数组）的问题。
我们随着代码一起来理解一下这些 STL。
#include<bits/stdc++.h>
#define ll long long
#define dd double
#define ull unsigned ll
#define LL __int128
#define siz(A) ((int)A.size())
using namespace std;
char gc(){static char buf[1<<16],*s,*t;if(s==t){t=(s=buf)+fread(buf,1,1<<16,stdin);if(s==t)return EOF;}return *s++;}
//#define getchar gc
ll read()
{
char c;
ll w=1;
while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
ll ans=c-'0';
while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
return ans*w;
}
void pc(char c,int op)
{
static char buf[1<<16],*s=buf,*t=(buf+(1<<16));
(op||((*s++=c)&&(s==t)))&&(fwrite(buf,1,s-buf,stdout),s=buf);
}
void wt(int x)
{
if(x>9)wt(x/10);
pc('0'+x%10,0);
}
void wts(int x,char op)
{
if(x<0)pc('-',0),x=-x;
wt(x),pc(op,0);
}
namespace vec
{
vector<int>v;
void test()
{
vector<int>A(5);
vector<int>B(5,3);
vector<int>C={1,2,3};
for(vector<int>::iterator it=A.begin();it!=A.end();it++)cout<<*it<<" ";
puts("");
for(auto it:B)cout<<it<<" ";
puts("");
for(int i=0;i<(int)C.size();i++)cout<<C[i]<<" ";
puts("");
int n=read();
v.resize(100);
cout<<(int)v.size()<<"\n";//unsigned
cout<<(int)v.capacity()<<"\n";
for(int i=1;i<=n;i++)
v.push_back(i);
cout<<(int)v.size()<<"\n";//unsigned
cout<<(int)v.capacity()<<"\n";
v.shrink_to_fit();
cout<<(int)v.capacity()<<"\n";
v.push_back(2);
cout<<(int)v.size()<<"\n";
cout<<(int)v.capacity()<<"\n";
v.clear();
cout<<(int)v.capacity()<<"\n";
vector<int>().swap(v);
cout<<(int)v.capacity()<<"\n";
}
}
namespace basic
{
basic_string<int>v;
void test()
{
int n=read();
v.resize(100);
cout<<(int)v.size()<<"\n";//unsigned
cout<<(int)v.capacity()<<"\n";
for(int i=1;i<=n;i++)
v.push_back(i);
cout<<(int)v.size()<<"\n";//unsigned
cout<<(int)v.capacity()<<"\n";
v.shrink_to_fit();
cout<<(int)v.capacity()<<"\n";
v.push_back(2);
cout<<(int)v.size()<<"\n";
cout<<(int)v.capacity()<<"\n";
v.clear();
cout<<(int)v.capacity()<<"\n";
basic_string<int>().swap(v);
cout<<(int)v.capacity()<<"\n";
basic_string<int>A={2,3,4};
basic_string<int>B={2,3,4};
for(auto it:A)cout<<it<<" ";
puts("");
A=A+B;
for(auto it:A)cout<<it<<" ";
puts("");
//string
cout<<A.find({4,2})<<"\n";
}
}
namespace se
{
set<int>A;
multiset<int>B;
void test()
{
for(int i=1;i<=3;i++)
{
A.insert(i);//pair <bool,iterator>
A.insert(i);
B.insert(i);//指针 iterator
B.insert(i);
}
for(auto it:A)cout<<it<<" ";
puts("");
for(auto it:B)cout<<it<<" ";
puts("");
multiset<int>::iterator x=B.lower_bound(0);
multiset<int>::iterator y=B.find(2);
B.erase(x);
for(auto it:B)cout<<it<<" ";
puts("");
B.erase(3);
for(auto it:B)cout<<it<<" ";
puts("");
cout<<(int)B.size()<<"\n";
cout<<(int)B.count(2)<<"\n";
A.clear(),B.clear();
//不能数组下标访问。
}
}
namespace ma
{
map<int,int>A;
unordered_map<int,int>B;
void test()
{
for(int i=1;i<=3;i++)A[i]=i-1,B[i]=i-1;
for(auto it:A)cout<<it.first<<" "<<it.second<<"\n";
puts("");
// for(auto it:B)cout<<it<<" ";
// puts("");
auto it=A.find(2);//key
cout<<A[4]<<"\n";
A.clear(),B.clear();
}
}
namespace bit
{
bitset<10>bit,bb;
void test()
{
bit[5]=1;
cout<<bit<<"\n";
bit.flip();
bit<<=3;
cout<<bit<<"\n";
bb[1]=1;
bb[4]=1;
cout<<bb<<"\n";
bit^=bb;
cout<<bit<<"\n";
int A=bit._Find_first();
cout<<A<<"\n";
cout<<bit._Find_next(A)<<"\n";
}
}
int main(){
vec::test();
basic::test();
se::test();
ma::test();
bit::test();
pair<int,int>A;
array<int,2>B;
// stack
// queue
// priority_queue
// sort();
// merge();
// nth_element();
// next_permutation();
// swap();
vector<int>B=A;
sort(A.begin(),A.end());
A.resize(unique(A.begin(),A.end())-A.begin());
for(auto it:B)cout<<it<<" ";
puts("");
for(int i=0;i<(int)B.size();i++)
B[i]=lower_bound(A.begin(),A.end(),B[i])-A.begin();
for(auto it:B)cout<<it<<" ";
puts("");
pc('1',1);
return 0;
}差分前缀和
是一个很简单的算法，我们可以用来解决一些区间的问题，首先我们来看前缀和的处理方式。
【深进 1. 例 1】求区间和
洛谷 P8218
代码展示
差分
若当前我们每次形如修改一个区间，使得区间加上一个值，最后我们需要求出修改之后的数组我们应该怎么办呢？
若当前我们每次形如修改一个区间，使得区间加上一个值，最后我们需要求出修改之后的数组我们应该怎么办呢？
我们可以用差分的方式，即对于每个区间 [l, r]，我们让 al 加上 v，ar+1减去 v。
最大加权矩形
给定一个 n ∗ n 的矩形，询问这个矩形内部和最大的一个子子矩形，这个子矩形的和是多少？
n ≤ 12
铺地毯
n × n 的格子上有 m 个地毯。
给出这些地毯的信息，问每个点被多少个地毯覆盖。
n, m ≤ 1000
ST 表