数据结构(一)

前三个只讲STL(都1202年了不会还有人在手写吧……)

FILO(First In Last Out),实现方法就是模拟

std::stack<TypeName> s;  // 使用默认底层容器 deque,数据类型为 TypeName
std::stack<TypeName,Container> s;  // 使用 Container 作为底层容器
std::stack<TypeName> s2(s1);  
s.top();//取顶部元素
s.push(x);//把x从顶部入栈
s.pop();//弹出顶部元素
s.size();//返回容器中元素数量
s.empty();//查询容器是否为空

队列

FIFO(First In First Out),同上

std::queue<TypeName> q;  // 使用默认底层容器 deque,数据类型为 TypeName
std::queue<TypeName, Container> q;  // 使用 Container 作为底层容器
std::queue<TypeName> q2(q1);  // 将 s1 复制一份用于构造 q2
q.front();//取顶部元素(此时队列不能为空)
q.push(x);//把x从顶部入队
q.pop();//弹出顶部元素
q.size();//返回容器中元素数量
q.empty();//查询容器是否为空

std::priority_queue<TypeName> q;             // 数据类型为 TypeName
std::priority_queue<TypeName,Container> q;  // 使用 Container 作为底层容器
std::priority_queue<TypeName,Container,Compare> q;//Compare是比较器,用greater<int>是小根堆,用less<int>是大根堆
auto cmp = [](const std::pair<int,int> &l, const std::pair<int, int> &r) {
 return l.second < r.second;
};
std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int> >,decltype(cmp)>//自定义比较器的写法,decltype是为了查询表达式的数据类型(cmp开的auto)
q.push(x);//访问堆顶元素(此时优先队列不能为空)
q.empty();//查询容器是否为空
q.size();//查询容器中的元素数量
-----以上操作为常数复杂度-----
q.push(x);//插入元素,并对底层容器排序
q.pop();//删除堆顶元素(此时优先队列不能为空)
-----以上操作为log复杂度-----

上面三种数据结构用的STL都属于容器适配器,它们使用的默认底层容器是双端队列deque(队列和栈)和向量vector(优先队列),因此对他们使用容器本身支持的操作也是可行的,但是复杂度也相应的是底层容器的复杂度,下方对这两种底层容器进行简单介绍

deque

vector

vector<int> v;//新建vector
v.reserve(3);//预分配3个元素的空间
vector<int> v(3);//创建vector并预分配空间
vector<int> v(3, 2);//创建vector,预分配空间并赋初值为2
vector<int> v(v2);//新建v拷贝v2至v
vector<int> v(v2.begin() + 1, v2.begin() + 3);//新建v并拷贝v2[1..3]至v
vector<int> v(std::move(v2));  //新建v并把v2移动到v
v.push_back()//从末尾插入
v.pop_back()//删除末尾
v.insert()//在特定位置插入元素,是线性复杂度的,与目的位置离末尾的距离有关
v.size()//返回容器中已经被占用的大小,v.capcity()返回的是在不扩容的情况下的容量上限
v.clear();//清空

并查集

fa[i] = i;
int find(int x){
	if(fa[x] != x){
		fa[x] = find(fa[x]);//路径压缩
	}
	return fa[x];
}
int find(int x){//无路径压缩
	if(fa[x] == x) return x;
	return find(fa[x]);
}
void merge(int x,int y){
	int X = find(x);
	int Y = find(Y);
	if(X == Y) return;
	fa[X] = Y;//如果用按秩合并就把size小的合并到size大的,记得合并size
}

种类并查集

有时候我们需要维护的信息中存在不同集合之间的关系,那么原先只维护一个集合的并查集就不再适用了,这时,我们可以通过将fa数组分段的方式实现基于关系维护集合。以NOI 2001食物链为例

int c[maxn * 3];//[1,n]为A,[n + 1,2n]为B,[2n + 1,3n]为C
if(tmp==1){
	if(find(x + n) == find(y) || find(x) == find(y + n)){
		ans++;
	}else{
		merge(x,y);
		merge(x + n,y + n);
		merge(x + n * 2,y + n * 2);
	}
}else{
	if(find(x) == find(y) || find(x) == find(y + n)){
		ans++;
	}else{
		merge(x + n,y);
		merge(x + n * 2,y + n);
		merge(x,y + n * 2);
    }
}

题目中设定了三个存在捕食与被捕食关系的种群,我们用一个3倍maxn大的fa数组同时进行维护,因为输入不会提供生物个体所属的种群,所以我们可以在三个种群中同时标示两种生物属于同一个种群,给每个生物在每个集合中都创造一个”分身”,而捕食关系则可以表示为捕食者与被捕食者在能捕食它的集合中的”分身”属于同一个集合

单调栈

维护一个单调的栈来优化一些原本需要扫一遍的最值问题,例题POJ3250,比单调队列那个简单(doge

#include <cstdio>
#include <cstdlib>
#include <stack>
#include <cctype>
#define int long long

using namespace std;

template <typename T> inline T read(){
	T sum = 0;
	int fl = 1,ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
	for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int maxn = 8e4 + 5;

int n;
int a[maxn];
stack <int> s;

signed main(){
	n = read<int>();
	for(int i = 1; i <= n; i++){
		a[i] = read<int>();
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		while(!s.empty() && s.top() <= a[i]) s.pop();
		if(!s.empty() && s.top() > a[i]) ans += s.size();
		s.push(a[i]);
	}
	printf("%lld\n",ans);
	return 0;
}

单调队列

顾名思义就是维护一个单调的队列(deque)来优化一些原本需要扫一遍的最值问题。

以滑动窗口为例,我们需要求每连续k个数中的最值,暴力显然需要O(k(n-k))次,是n^2级别的。考虑对它进行优化,显然,对于第一个区间,从头扫到尾才能知道它的最大值,但是在移动查询区间时,就有优化的空间了。不难想到,当查询区间往右边移动一个时,如果当前的最大值在移动后仍然在查询区间内,并且新加入区间的数比当前的最大值大,那么新加入区间的数一定为此区间中的最大值,否则区间中的最大值不变。如果当前的最大值在移动后不在查询区间内,新加入的数会是新的最大值吗?答案显然是不一定。正因为如此,我们才会在每个查询区间内维护一个单调递减的序列,这样,每次弹出查询区间外的值后,留下的队头就是不考虑新加入查询区间的数时的最大值,我们将它与新加入区间的数进行比较就能得知当前的区间最大值

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <deque>
#include <cctype>

using namespace std;

template <typename T> inline T read(){
	T sum = 0;
	int fl = 1,ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
	for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void write(int x){
	if(x < 0){
		x = -x;
		putchar('-');
	}
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}

const int maxn = 1e6 + 5;

int n,k;
int a[maxn];
deque < pair<int,int> > q;

int main(){
	n = read<int>();
	k = read<int>();
	for(int i = 1; i <= n; i++){
		a[i] = read<int>();
	}
	for(int i = 1; i <= n; i++){
		while(!q.empty() && q.front().first <= i - k) q.pop_front();//如果当前最小值不在查找范围内,弹出
		while(!q.empty() && q.front().second >= a[i]) q.pop_front();//如果当前队头不是最大值,弹出
		while(!q.empty() && q.back().second >= a[i]) q.pop_back();//如果队列不单调,弹出(查找范围内不单调则不可能为答案)
		q.push_back(make_pair(i,a[i]));
		if(i >= k) write(q.front().second),putchar(' ');
	}
	puts("");
	q.clear();
	for(int i = 1; i <= n; i++){
		while(!q.empty() && q.front().first <= i - k) q.pop_front();
		while(!q.empty() && q.front().second <= a[i]) q.pop_front();
		while(!q.empty() && q.back().second <= a[i]) q.pop_back();
		q.push_back(make_pair(i,a[i]));
		if(i >= k) write(q.front().second),putchar(' ');
	}
	return 0;
}

树状数组

也是一种用分治的思想维护区间的方式,不过不像线段树结点维护的区间长度从上到下折半,树状数组的结点维护区间的方式是通过lowbit,编号为n的结点维护n及n之前共lowbit(n)个结点

inline int lowbit(int x){
	return x&-x;
}

int query(int i){//前i位的和,若区间[l,r]的和等于区间[1,r]的和减去区间[1,l-1]的和
	int tmp = 0;
	for(; i; i -= lowbit(i)) tmp += c[i];//由上述结点维护区间的规律,求前i个数的和就从i一次跳lowbit()个就好了
	return tmp;
}

void add(int i,int x){//把i以后的部分都加上x(树状数组维护的是前缀和,一个元素改变影响的是它后面的元素)
	for(; i <= n; i += lowbit(i)) c[i] += x;
}

区间加:维护原数组的差分数组的前缀和,等价于维护原数组,在一个点+x等价于把后面的数都+x,那么在区间加的区间后面把x减回来就好了

区间求和:区间[l,r]的和等于区间[1,r]的和减去区间[1,l-1]的和

线段树

用分治的思想维护区间,每个结点的左右子结点分别维护该结点所维护的信息的一半

lazy tag:进行区间操作的时候lazy一点,如果当前结点维护的数据不能直接用来操作(比如不完全包含在操作区间内),那么就不直接应用更改,而是只将更改应用于能直接操作的子辈中,当然,那些不能直接操作的子辈也不会应用更改,知道它在之后的操作中可以被直接操作(即每个不能操作的结点都用pushdown把tag分给左右子结点)。当然,在子节点的操作完成后,更改并没有被应用到它的任何一个前辈,因此还需要pushup来将更改逐级上传到当前结点

重点:想清楚要维护的数据如何应用到区间上,tag应该如何传递,大范围的信息怎么由小范围的信息合成,不同tag直接有没有运算优先级关系(比如:区间乘法,维护区间和的方式是把被乘的区间区间和乘以乘数,传递标记的方式是乘法结合律,如果乘的时候有加法tag那么要把加法tag一起乘)

namespace seg{
#define ls tree[root << 1]
#define rs tree[root << 1 | 1]
#define lson root << 1, l, mid
#define rson root << 1 | 1, mid + 1, r
	struct node{
		int sum;
		int add;
		int mul;
	}tree[maxn * 4];

	void pushup(int root){
		tree[root].sum = (ls.sum + rs.sum) % p;
	}

	void pushdown(int root,int l,int r,int mid){
		if(!tree[root].add && tree[root].mul == 1) return;
		ls.mul *= tree[root].mul,ls.mul %= p;
		ls.add *= tree[root].mul,ls.add %= p;
		ls.sum *= tree[root].mul,ls.sum %= p;
		rs.mul *= tree[root].mul,rs.mul %= p;
		rs.add *= tree[root].mul,rs.add %= p;
		rs.sum *= tree[root].mul,rs.sum %= p;
		ls.add += tree[root].add,ls.add %= p;
		rs.add += tree[root].add,rs.add %= p;
		ls.sum += tree[root].add * (mid - l + 1),ls.sum %= p;
		rs.sum += tree[root].add * (r - mid),rs.sum %= p;
		tree[root].add = 0;
		tree[root].mul = 1;
	}

	void build(int root,int l,int r){
		tree[root].mul = 1;
		tree[root].add = 0;
		if(l == r){
			tree[root].sum = a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(lson);
		build(rson);
		pushup(root);
	}
	
	void add(int root,int l,int r,int ql,int qr,int v){
		if(ql <= l && r <= qr){
			tree[root].sum += (r - l + 1) * v,tree[root].sum %= p;
			tree[root].add += v,tree[root].add %= p;;
			return;
		}
		int mid = (l + r) >> 1;
		pushdown(root,l,r,mid);
		if(ql <= mid) add(lson,ql,qr,v);
		if(qr > mid) add(rson,ql,qr,v);
		pushup(root);
	}

	void mul(int root,int l,int r,int ql,int qr,int v){
		if(ql <= l && r <= qr){
			tree[root].sum *= v,tree[root].sum %= p;
			tree[root].add *= v,tree[root].add %= p;
			tree[root].mul *= v,tree[root].mul %= p;
			return;
		}
		int mid = (l + r) >> 1;
		pushdown(root,l,r,mid);
		if(ql <= mid) mul(lson,ql,qr,v);
		if(qr > mid) mul(rson,ql,qr,v);
		pushup(root);
	}

	int query(int root,int l,int r,int ql,int qr){
		if(ql <= l && r <= qr) return tree[root].sum % p;
		int mid = (l + r) >> 1;
		int ans = 0;
		pushdown(root,l,r,mid);
		if(ql <= mid) ans += query(lson,ql,qr),ans %= p;
		if(qr > mid) ans += query(rson,ql,qr),ans %= p;
		return ans;
	}
#undef ls
#undef rs
#undef lson
#undef rson
}

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇