#创作计划#浅谈数据结构
2024-11-11 13:53:26
发布于：江苏
195阅读
0回复
0点赞
这个fw做题的时候突然想总结一下毒瘤数据结构（持续更中，于是就有了这篇文章...
你别急，我保证一定在CSP-J/S之前更新完，给大家一览！
Ps:本文不再介绍STL中有的数据结构。这里仅介绍NOI大纲1~8级的数据结构
目录一览：
| 1.并查集 | 2.ST表 | 3.线段树&树状数组 | 4.主席树 |
|---|---|---|---|
| 黄题 | 黄题 | 绿题 | 蓝题 |
一，并查集（模板黄题
有时候，我们要处理一种“帮派”问题，大概是这样的：a加入b的帮派，a的帮派和b的帮派结合...类似这样的操作。为了更好的解决这样的问题，我们用并查集来表示。
基本思想：用一个pre数组表示这个人的上级，那么查询a和b食不食再同一个帮派里，只需要比较他们的终极上司食不食一样就行。如果每次都这样查询的话，效率太低。可以使用记忆化搜索。下次找的时候直接返回即可。查询复杂度为（大概）
干讲不行，上例题：
1.(模板)并查集
题目中有查询和加入操作，按照上面的分析来。
一定要初始化pre[i]=i！！！！！！每年都有人忘记这个东西。
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int pre[N];
int n,m;
int find(int x){
if(pre[x]==x) return x;
return pre[x]=find(pre[x]);
}
void join(int x,int y){
int p=find(x),q=find(y);
if(p!=q){
pre[p]=q;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) pre[i]=i;
for(int i=1;i<=m;i++){
int z,x,y;
cin>>z>>x>>y;
if(z==1){
join(x,y);
}else{
if(find(x)==find(y)) cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
}
return 0;
}
2.修复公路
并查集板子题。
先按照时间排序好开通路线的时刻，然后按顺序枚举：将此公路两端的城市x,y加入集合中（如果不相同），那么只要加n-1次所有城市就都在一个集合中了。此时最早通车时间就是当前这条路的开通时间。
ps:此类想法会与后面一个算法不约而同
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
struct node{
int x,y,t;
}a[N];
int pre[N];
int n=1,m;
int find(int x){
if(pre[x]==x) return x;
return pre[x]=find(pre[x]);
}
void join(int x,int y){
int p=find(x),q=find(y);
if(p!=q){
pre[p]=q;
}
}
bool cmp(node a,node b){
return a.t<b.t;
}
int main(){
cin>>n>>m;
if(n==1){
cout<<0;
return 0;
}
for(int i=1;i<=m;i++){
cin>>a[i].x>>a[i].y>>a[i].t;
}
for(int i=1;i<=n;i++) pre[i]=i;
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++){
int f1=find(a[i].x),f2=find(a[i].y);
if(f1!=f2){
join(f1,f2);
n--;
}
if(n==1){
cout<<a[i].t;
return 0;
}
}
cout<<-1;
return 0;
}
3.食物链
这道题给我的印象超级深刻，当时老师让我们尝试新的做法，我尝试了八个小时也没有试出来，最后老师说，这个算法是错的...
此道题也可以用 带权并查集 解决，这里介绍普通做法。
定义一个三倍空间的并查集，其中n是同类并查集，x+n是猎物，x+2*n为天敌（题目中的关系满足三角形）
根据逻辑即可求解。
（代码找不到了，用别人题解上的吧，反正思路都一样）
#include <bits/stdc++.h>
using namespace std;
int fa[300001];
//并查集
int find(int x)//查找
{
if(x != fa[x])
{
fa[x] = find(fa[x]);
}
return fa[x];
}
int unity(int x, int y)//合并
{
int r1 = find(fa[x]);
int r2 = find(fa[y]);
fa[r1] = r2;
}
int main()
{
int i, n, k, x, y, z;
int ans = 0;
scanf("%d %d", &n, &k);
for(i = 1; i <= 3 * n; i++)
{
fa[i] = i;
}
// x是同类，x + n是猎物， x + 2 * n是天敌
for(i = 1; i <= k; i++)
{
scanf("%d %d %d", &z, &x, &y);
if(x > n || y > n)//x和y不能大于n
{
ans++;//假话++
}
else
{
if(z == 1)//x和y是同类
{
if(find(x + n) == find(y) || find(x + 2 * n) == find(y))//如果是同类，x不能是y的猎物或天敌
{
ans++;//假话++
}
else
{
unity(x, y);//x的同类是y的同类
unity(x + n, y + n);//x的猎物是y的猎物
unity(x + 2 * n, y + 2 * n);//x的天敌是y的天敌
}
}
else//y是x的猎物
{
if(x == y || find(x) == find(y) || find(x + 2 * n) == find(y))//如果y是x的猎物，x不能是y的猎物，x不能和y是同类，y不能是x的天敌
{
ans++;//假话++
}
else
{
unity(x, y + 2 * n);//x的同类是y的天敌
unity(x + n, y);//x的猎物是y的同类
unity(x + 2 * n, y + n);//x的天敌是y的猎物
}
}
}
}
printf("%d", ans);//输出
return 0;
}
二，倍增——ST表
ST表是解决RMQ问题的不二之选。他可以把单次静态查询变为，也就是说，它是离线算法。预处理复杂度为
基本想法：为了把区间查询想树一样降到级别的复杂度，不难联想到二进制优化。
设为以i为起点，长度为中的最值，那么 =
于是就可以建表，初始值设
1.Balanced Lineup G
RMQ板子题。
由于n过大，可以用ST表预处理。
#include <bits/stdc++.h>
using namespace std;
int n,m,dp[100005][32],pd[100005][32];
int a[100005];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
dp[i][0]=a[i];
pd[i][0]=a[i];
}
for(int j=1;j<=log2(n);j++){
for(int i=1;i<=n-(1<<j)+1;i++){
dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
pd[i][j]=min(pd[i][j-1],pd[i+(1<<(j-1))][j-1]);
}
}
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
int l=log2(y-x+1);
int ans=max(dp[x][l],dp[y-(1<<l)+1][l]) - min(pd[x][l],pd[y-(1<<l)+1][l]);
cout<<ans<<endl;
}
return 0;
}
(dp表示最大值的st表，pd表示最小值的st表)
2.策略游戏
一道巨恶心的题目，恶心值1100/1500，仅次于时间复杂度。
第一步，把csp语言转化成中文：
两个人在A数组的[l1,r1]区间里面选x，B数[l2,r2]区间里面选y，一个人要使xy最小，一个人要使xy最大。
请看图。
于是代码里就有6个st表，分别求，然后按照上面的思路来就行。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,q;
int amax[100005][25],amin[100005][25],bmax[100005][25],bmin[100005][25],azhengmin[100005][25],afumax[100005][25];
void st(){
int k=log2(n);
for(int j=1;j<=k;j++){
for(int i=1;i<=n-(1<<j)+1;i++){
int p=i+(1<<(j-1));
amax[i][j]=max(amax[i][j-1],amax[p][j-1]);
amin[i][j]=min(amin[i][j-1],amin[p][j-1]);
azhengmin[i][j]=min(azhengmin[i][j-1],azhengmin[p][j-1]);
afumax[i][j]=max(afumax[i][j-1],afumax[p][j-1]);
}
}
k=log2(m);
for(int j=1;j<=k;j++){
for(int i=1;i<=n-(1<<j)+1;i++){
int p=i+(1<<(j-1));
bmax[i][j]=max(bmax[i][j-1],bmax[p][j-1]);
bmin[i][j]=min(bmin[i][j-1],bmin[p][j-1]);
}
}
}
signed main(){
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
int x;
cin>>x;
amax[i][0]=x;
amin[i][0]=x;
afumax[i][0]=(x<0?x:-1e18);
azhengmin[i][0]=(x>=0?x:1e18);
}
for(int i=1;i<=m;i++){
int x;
cin>>x;
bmax[i][0]=x;
bmin[i][0]=x;
}
st();
while(q--){
int l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
int k1=log2(r1-l1+1),k2=log2(r2-l2+1);
int amaxint=max(amax[l1][k1],amax[r1-(1<<k1)+1][k1]);
int aminint=min(amin[l1][k1],amin[r1-(1<<k1)+1][k1]);
int azhengminint=min(azhengmin[l1][k1],azhengmin[r1-(1<<k1)+1][k1]);
int afumaxint=max(afumax[l1][k1],afumax[r1-(1<<k1)+1][k1]);
int bmaxint=max(bmax[l2][k2],bmax[r2-(1<<k2)+1][k2]);
int bminint=min(bmin[l2][k2],bmin[r2-(1<<k2)+1][k2]);
//cout<<amaxint<<" "<<aminint<<" "<<azhengminint<<" "<<bmaxint<<" "<<bminint<<endl;
int maxn=-1e18;
if(amaxint>=0){
maxn=max(maxn,bminint*amaxint);
}else{
maxn=max(maxn,bmaxint*amaxint);
}
if(aminint>=0){
maxn=max(maxn,aminint*bminint);
}else{
maxn=max(maxn,aminint*bmaxint);
}
if(afumaxint != -1e18){
if(afumaxint>=0){
maxn=max(maxn,afumaxint*bminint);
}else{
maxn=max(maxn,afumaxint*bmaxint);
}
}
if(azhengminint!=1e18){
if(azhengminint>=0){
maxn=max(maxn,azhengminint*bminint);
}else{
maxn=max(maxn,azhengminint*bmaxint);
}
}
cout<<maxn<<endl;
}
return 0;
}
/*
4 4 4
-1 3 4 6
2 3 -5 7
*/
三，线段树&树状数组（模板绿
线段树是区间动态修改&区间动态查询的不二之选。 可能我们普通枚举，时间复杂度达到了，再来一个大数据&卡常让你喜提TLE。
众所周知，使用 树 这种结构 可以让查询&修改操作降到。下面以[模板]线段树1为例来分析。
先来一个求左儿子，右儿子的函数，方便以后使用。
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
然后，我们需要一个重要的东西——tag标记。又称lazytag。每次都一个一个修改太麻烦，我们可以先标记，再统一修改，也就是说，它可以传递式记录这个节点的改变，充分利用树的特征。于是，修改一个区间就变成了修改这个区间的LCA，再传递。
按照这样，我们可以建树了。
具体解释见注释。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[100005],tree[100005<<2],tag[100005<<2];//开四倍，开四倍，开四倍，重要的事情说三遍！！！
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
void push_up(int p){
tree[p]=tree[ls(p)]+tree[rs(p)];
//回溯操作，如求最小值可以这样：tree[p]=min(tree[ls(p)],tree[rs(p)])
}
void build(int p,int pl,int pr){
tag[p]=0;//tag初始为0
if(pl==pr){
tree[p]=a[pl];
return;//叶子节点
}
int mid=(pl+pr)>>1;
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);//二分建树
push_up(p);//回溯上去
}
void addtag(int p,int pl,int pr,int d){//加标记，重点
tag[p]+=d;
tree[p]+=d * (pr-pl+1);
}
void push_down(int p,int pl,int pr){//下传递操作
if(tag[p]){//如果有标记
//左子右子树传递标记
int mid=(pl+pr)>>1;
addtag(ls(p),pl,mid,tag[p]);
addtag(rs(p),mid+1,pr,tag[p]);
tag[p]=0;
//自己标记传完了
}
}
void update(int l,int r,int p,int pl,int pr,int d){
if(l<=pl && pr<=r){//区间被包含
addtag(p,pl,pr,d);//标记
return;
}
push_down(p,pl,pr);//下传标记
int mid=(pl+pr)>>1;
if(l<=mid) update(l,r,ls(p),pl,mid,d);//二分更新
if(r>mid) update(l,r,rs(p),mid+1,pr,d);
push_up(p);//回溯上传
}
int query(int l,int r,int p,int pl,int pr){
if(pl>=l && r>=pr) return tree[p];//如果区间包含，直接返回
push_down(p,pl,pr);//下传
int res=0;
int mid=(pl+pr)>>1;
if(l<=mid) res+=query(l,r,ls(p),pl,mid);
if(r>mid) res+=query(l,r,rs(p),mid+1,pr);
return res;
}
int n,m;
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
while(m--){
int q,l,r,d;
cin>>q;
if(q==1){
cin>>l>>r>>d;
update(l,r,1,1,n,d);
}else{
cin>>l>>r;
cout<<query(l,r,1,1,n)<<endl;
}
}
return 0;
}
1.[模板]线段树2
加上一个乘法，不会有人要抄题解了吧
还是同样的，加上一个tag，表示乘法tag。
再下传操作中，我们需要更新一下乘法和加法的顺序。
再pushdown中，tree=tree * 父亲的乘法tag+父亲加法乘上区间
cheng=cheng乘上父亲乘法
jia=jia*父亲乘法+父亲加法
再update中，与线段树1一样。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,q,mod;
int a[100005],tree[100005*4],tagjia[100005*4],tagcheng[100005*4];
int ls(int x){
return x*2;
}
int rs(int x){
return x*2+1;
}
void push_up(int p){
tree[p]=(tree[ls(p)]+tree[rs(p)])%mod;
}
void build(int p,int l,int r){
tagjia[p]=0;
tagcheng[p]=1;//乘数为0，然后呢？
if(l==r){
tree[p]=a[l];
return;
}
int mid=(l+r)/2;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
void addtag(int p,int l,int r,int pfather){
tree[p]=tree[p]*tagcheng[pfather]+tagjia[pfather]*(r-l+1);
tree[p]%=mod;
tagcheng[p]*=tagcheng[pfather];
tagcheng[p]%=mod;
tagjia[p]=tagjia[p]*tagcheng[pfather]+tagjia[pfather];
tagjia[p]%=mod;
}
void pushdown(int p,int l,int r){
int mid=(l+r)/2;
addtag(ls(p),l,mid,p);
addtag(rs(p),mid+1,r,p);
tagjia[p]=0,tagcheng[p]=1;
}
void update1(int p,int pl,int pr,int l,int r,int k){//乘法
if(pr<l||pl>r) return;
if(l<=pl && pr<=r){
tree[p]*=k;
tree[p]%=mod;
tagjia[p]*=k;
tagjia[p]%=mod;
tagcheng[p]*=k;
tagcheng[p]%=mod;
return;
}
pushdown(p,pl,pr);
int mid=(pl+pr)/2;
update1(ls(p),pl,mid,l,r,k);
update1(rs(p),mid+1,pr,l,r,k);
push_up(p);
}
void update2(int p,int pl,int pr,int l,int r,int k){
//cout<<p<<endl;
if(pr<l||pl>r) return;
if(l<=pl && pr<=r){
tagjia[p]+=k;
tagjia[p]%=mod;
tree[p]+=k*(pr-pl+1);
tree[p]%=mod;
return;
}
pushdown(p,pl,pr);
int mid=(pl+pr)/2;
update2(ls(p),pl,mid,l,r,k);
update2(rs(p),mid+1,pr,l,r,k);
push_up(p);
}
int query(int p,int pl,int pr,int l,int r){
if(pr<l||pl>r) return 0;
if(l<=pl&&pr<=r){
return tree[p];
}
pushdown(p,pl,pr);
int sum=0;
int mid=(pl+pr)/2;
//cout<<p<<" "<<pl<<" "<<pr<<" "<<endl;
sum+=query(ls(p),pl,mid,l,r);
sum+=query(rs(p),mid+1,pr,l,r);
return sum%mod;
}
signed main(){
cin>>n>>q>>mod;
for(int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
while(q--){
int op;
cin>>op;
int x,y;
cin>>x>>y;
if(op==1){
int k;
cin>>k;
update1(1,1,n,x,y,k);
}else if(op==2){
int k;
cin>>k;
update2(1,1,n,x,y,k);
}else{
cout<<query(1,1,n,x,y)%mod<<endl;
}
}
return 0;
}
2.数据中心能耗分析
作为排位赛最后一题，出的还是太水了，为什么要放一个模板
本题要求立方和。
稍微推导一下。
定义sum1,sum2,sum3为1次，2次，3次立方和。在pushdown中修改即可。
代码我就不放了。
哎算了还是放一下吧
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
typedef long long LL;
const int p = 1000000007;
int tot, num;
int n, m, r,t,cases=0;
int w[N], a[N], sum1[N * 4], sum2[N * 4], sum3[N * 4], lazy_mul[N * 4], lazy_add[N * 4]; // w[i]=j表示时间戳为i的点的值为j，a[]输入每个节点的值，dat线段树每个点权值，lazy线段树每个点的懒标记
vector<int> mp[N];
void solve(int rt,int len,int a,int b){ //a为add b为mul
lazy_mul[rt] = 1ll*lazy_mul[rt] * b % p;
lazy_add[rt] = 1ll*lazy_add[rt] * b % p;
lazy_add[rt] = ((lazy_add[rt] + a) % p + p) % p;
if(b!=1){ //先乘后加
sum1[rt] = 1ll*sum1[rt] * b % p;
sum2[rt] = (1ll*sum2[rt] * b % p) * b % p;
sum3[rt] = ((1ll*sum3[rt] * b % p) * b % p) * b % p;
}
if(a!=0){
int a2 = 1ll*a * a % p, a3 = 1ll*a2 * a % p;
sum3[rt] = ((sum3[rt] + (LL)len * a3 % p) + p) % p;
sum3[rt] = ((sum3[rt] + 3ll * (LL)sum2[rt] % p * a % p) + p) % p;
sum3[rt] = ((sum3[rt] + 3ll * (LL)sum1[rt] % p * a2 % p) + p) % p;
sum2[rt] = ((sum2[rt] + 2ll * (LL)sum1[rt] % p * a % p) + p) % p;
sum2[rt] = ((sum2[rt] + (LL)len * a2 % p) + p) % p;
sum1[rt] = ((sum1[rt] + (LL)len * a % p) + p) % p;
}
}
void pushup(int rt) {
sum1[rt] = (sum1[rt << 1] + sum1[rt << 1 | 1]) % p;
sum2[rt] = (sum2[rt << 1] + sum2[rt << 1 | 1]) % p;
sum3[rt] = (sum3[rt << 1] + sum3[rt << 1 | 1]) % p;
}
// 建线段树，rt为根，l为rt点管辖的左边界， r为rt点管辖的有边界
void build(int rt, int l, int r)
{
lazy_add[rt] = 0;
lazy_mul[rt] = 1;
if(l==r)
{
int temp = a[l];
sum1[rt] = temp;
sum2[rt] = (1ll*sum1[rt] * sum1[rt]) % p;
sum3[rt] = (1ll*sum1[rt] * sum2[rt]) % p;
return ;
}
int mid=(l + r)>>1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid+1, r);
pushup(rt);
}
// 下传
void pushdown(int rt, int l, int r)
{
int mid = (l + r) >> 1;
solve(rt << 1, mid - l + 1, lazy_add[rt], lazy_mul[rt]);
solve(rt << 1 | 1, r - mid, lazy_add[rt], lazy_mul[rt]);
lazy_add[rt] = 0;
lazy_mul[rt] = 1;
}
// rt为根，l为rt点管辖的左边界， r为rt点管辖的有边界， L为需要修改的左区间，R为需要修改的右区间
void modify(int rt, int l, int r, int L, int R, int a,int b)
{
if(L <= l && r <= R)
{
solve(rt, r - l + 1, a, b);
return ;
}
pushdown(rt, l, r);
int mid = (l + r)>>1;
if(L <= mid) modify(rt << 1, l, mid, L, R, a,b);
if(mid < R) modify(rt << 1 | 1, mid + 1, r, L, R, a,b);
pushup(rt);
}
// rt为根，l为rt点管辖的左边界， r为rt点管辖的有边界， L为需要查询的左区间，R为查询的右区间,k代表查询的是k次方和
int query(int rt, int l, int r, int L, int R,int k)
{
if(L <= l && r <= R)
{
if(k==1)
return sum1[rt];
if(k==2)
return sum2[rt];
if(k==3)
return sum3[rt];
}
pushdown(rt, l, r);
int mid = (l + r)>>1;
int ans = 0;
if(L <= mid){
ans += query(rt << 1, l, mid, L, R,k);
ans%=p;
}
if(mid < R){
ans += query(rt << 1 | 1, mid + 1, r, L, R,k);
ans%=p;
}
pushup(rt);
return ans;
}
int main()
{
cin>>n>>m;
for(int i=1; i<=n; i++) cin>>a[i]; // 读入每个点的权值
build(1, 1, n);
// m次询问
for(int i=1, op, x, y, z; i<=m; i++)
{
scanf("%d", &op);
if(op == 1)
{
cin>>x>>y>>z;
modify(1,1,n,x, y, z,1); // 区间[x,y]加上z
}
else if(op == 2)
{
cin>>x>>y;
int ans=query(1,1,n,x,y,3);
if(ans<0){
cout<<(ans+p)%p<<endl;
}
else cout<<ans<<endl;
}
}
return 0;
}
请我的机房朋友修改了一下，所以码风会和之前不一样。
四，主席树（权值线段树）（模板蓝
主席树就是在线段树上加上“权值”具体一点的说，主席树的每一个节点都在维护一棵线段树。
与线段树不同的是，每个节点代表的是的范围。
干讲没用，上例题。
1.王老师的奇妙集合
主席树板子题。
数据比较大，使用主席树优化到，而删除操作就是把元素交换到一个不为人知的地方。
具体解释看代码。
#include <bits/stdc++.h>
using namespace std;
int n,q;
int a[4000005];
int ls(int x){
return x*2;
}
int rs(int x){
return x*2+1;
}
void add(int x,int l,int r,int d){//加入操作
a[x]++;
if(l==r) return;
int mid=(l+r)/2;
if(d<=mid){
add(ls(x),l,mid,d);
}else{
add(rs(x),mid+1,r,d);
}
}
void sub(int x,int l,int r,int k){//删除操作
a[x]--;
if(l==r) return;
int mid=(l+r)/2;
if(a[ls(x)]>=k){
sub(ls(x),l,mid,k);
}else{
sub(rs(x),mid+1,r,k-a[ls(x)]);
}
}
void print(int x,int l,int r){//输出操作
if(l==r){
cout<<l;
return;
}
int mid=(l+r)>>1;
if(a[ls(x)]){
print(ls(x),l,mid);
}else{
print(rs(x),mid+1,r);
}
}
signed main(){
//freopen("set.in","r",stdin);
//freopen("set.out","w",stdout);
cin>>n>>q;
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
add(1,1,n,x);
}
for(int i=1;i<=q;i++){
int x;
scanf("%d",&x);
if(x>=1) add(1,1,n,x);
else sub(1,1,n,-x);
}
if(a[1]==0){
cout<<0<<endl;
}else{
print(1,1,n);
}
//fclose(stdin);
//fclose(stdout);
return 0;
}
具体的请读者自己练习。
有帮助，赞一个