生活随笔
收集整理的這篇文章主要介紹了
第四章 高级数据结构
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
目錄
- 并查集
- 1250. 格子游戲【并查集判環(huán)】
- 1252. 搭配購(gòu)買(mǎi)【并查集 + 01背包】
- 237. 程序自動(dòng)分析【并查集的擴(kuò)展】
- 239. 奇偶游戲【不會(huì)】
- 238. 銀河英雄傳說(shuō)【維護(hù)距離的并查集】
- 樹(shù)狀數(shù)組
- 241. 樓蘭圖騰【樹(shù)狀數(shù)組的基本應(yīng)用】
- 242. 一個(gè)簡(jiǎn)單的整數(shù)問(wèn)題【區(qū)間修改 / 單點(diǎn)查詢】
- 243. 一個(gè)簡(jiǎn)單的整數(shù)問(wèn)題2【區(qū)間修改 / 區(qū)間查詢】
- 244. 謎一樣的牛【快速求排名擴(kuò)展】
- 線段樹(shù)
- 1275. 最大數(shù)【線段樹(shù) / 維護(hù)區(qū)間最大值】
- 245. 你能回答這些問(wèn)題嗎【單點(diǎn)修改 求區(qū)間的最大連續(xù)子段和】
- 243. 一個(gè)簡(jiǎn)單的整數(shù)問(wèn)題2【區(qū)間修改 / 區(qū)間查詢】
- 1277. 維護(hù)序列【區(qū)間乘/加 區(qū)間查詢】
- 可持續(xù)化數(shù)據(jù)結(jié)構(gòu)
- 255. 第K小數(shù)【可持續(xù)化線段樹(shù) / 主席樹(shù)】
- AC自動(dòng)機(jī)
- 1282. 搜索關(guān)鍵詞
- 1285. 單詞
并查集
并查集的基本操作:
- 合并兩個(gè)集合
- 查詢某個(gè)元素的祖宗結(jié)點(diǎn)
并查集的基本應(yīng)用擴(kuò)展
- 記錄每個(gè)集合的大小(綁定到根節(jié)點(diǎn))
- 記錄每個(gè)點(diǎn)到根節(jié)點(diǎn)的距離。(綁定到每個(gè)元素上)
1250. 格子游戲【并查集判環(huán)】
https://www.acwing.com/problem/content/description/1252/
如果合并之前，這兩元素已經(jīng)在集合中，那么說(shuō)明有環(huán)。
1250. 格子游戲【并查集】
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5+10;
int p
[N
],n
,m
;
int find(int x
)
{if(x
!=p
[x
]) p
[x
]=find(p
[x
]);return p
[x
];
}
int get(int x
,int y
) {return x
*n
+y
;}
int main(void)
{cin
>>n
>>m
;for(int i
=0;i
<n
*n
;i
++) p
[i
]=i
;for(int i
=1;i
<=m
;i
++){int x
,y
;char op
; cin
>>x
>>y
>>op
;x
--,y
--;int a
=get(x
,y
),b
;if(op
=='R') b
=get(x
,y
+1);else b
=get(x
+1,y
);if(find(a
)==find(b
)){cout
<<i
;return 0;}p
[find(a
)]=find(b
);}puts("draw");return 0;
}
1252. 搭配購(gòu)買(mǎi)【并查集 + 01背包】
https://www.acwing.com/problem/content/description/1254/
1252. 搭配購(gòu)買(mǎi)【并查集 + 01背包】
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5+10;
int w
[N
],v
[N
],p
[N
],n
,m
,sum
,f
[N
];
int find(int x
)
{if(x
!=p
[x
]) p
[x
]=find(p
[x
]);return p
[x
];
}
int main(void)
{cin
>>n
>>m
>>sum
;for(int i
=1;i
<=n
;i
++) p
[i
]=i
;for(int i
=1;i
<=n
;i
++) cin
>>v
[i
]>>w
[i
];for(int i
=1;i
<=m
;i
++){int a
,b
; cin
>>a
>>b
;if(find(a
)!=find(b
)){w
[find(a
)]+=w
[find(b
)];v
[find(a
)]+=v
[find(b
)];p
[find(b
)]=find(a
);}}for(int i
=1;i
<=n
;i
++){if(p
[find(i
)]==i
){for(int j
=sum
;j
>=v
[i
];j
--){f
[j
]=max(f
[j
],f
[j
-v
[i
]]+w
[i
]);}}}cout
<<f
[sum
];return 0;
}
237. 程序自動(dòng)分析【并查集的擴(kuò)展】
https://www.acwing.com/problem/content/description/239/
237. 程序自動(dòng)分析【并查集】
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5*3+10;
struct node {int a
,b
,c
;};
int p
[N
],t
,n
,idx
;
unordered_map
<int,int>mp
;
int get(int x
)
{if(mp
.count(x
)==0) mp
[x
]=++idx
;return mp
[x
];
}
void init(){mp
.clear(),idx
=0;}
int find(int x
)
{if(x
!=p
[x
]) p
[x
]=find(p
[x
]);return p
[x
];
}
int main(void)
{cin
>>t
;while(t
--){init();cin
>>n
;vector
<node
>ve
;for(int i
=0;i
<n
;i
++){int a
,b
,c
; cin
>>a
>>b
>>c
;ve
.push_back({get(a
),get(b
),c
});}for(int i
=1;i
<=idx
;i
++) p
[i
]=i
;for(int i
=0;i
<ve
.size();i
++)if(ve
[i
].c
==1&&find(ve
[i
].a
)!=find(ve
[i
].b
)) p
[find(ve
[i
].b
)]=find(ve
[i
].a
);bool flag
=true;for(int i
=0;i
<ve
.size();i
++)if(!ve
[i
].c
&&find(ve
[i
].a
)==find(ve
[i
].b
)) flag
=false;if(flag
) puts("YES");else puts("NO");}return 0;
}
239. 奇偶游戲【不會(huì)】
https://www.acwing.com/problem/content/241/
238. 銀河英雄傳說(shuō)【維護(hù)距離的并查集】
https://www.acwing.com/problem/content/240/
238. 銀河英雄傳說(shuō)【邊帶權(quán)的并查集】
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5*3+10;
int p
[N
],cnt
[N
],d
[N
],n
;
int find(int x
)
{if(x
!=p
[x
]){int root
=find(p
[x
]);d
[x
]+=d
[p
[x
]];p
[x
]=root
;}return p
[x
];
}
int main(void)
{for(int i
=1;i
<N
;i
++) p
[i
]=i
,cnt
[i
]=1;cin
>>n
;while(n
--){string op
;int a
,b
; cin
>>op
>>a
>>b
;if(op
=="M"){int pa
=find(a
),pb
=find(b
);d
[pa
]=cnt
[pb
];cnt
[pb
]+=cnt
[pa
];p
[pa
]=pb
;}else{int pa
=find(a
),pb
=find(b
);if(pa
==pb
) cout
<<max(0,abs(d
[a
]-d
[b
])-1)<<endl
;else cout
<<-1<<endl
;}}return 0;
}
樹(shù)狀數(shù)組
241. 樓蘭圖騰【樹(shù)狀數(shù)組的基本應(yīng)用】
https://www.acwing.com/problem/content/243/
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5*2+10;
typedef long long int LL
;
LL up
[N
],down
[N
],a
[N
],tr
[N
],n
;
int lowbit(int x
) {return x
&(-x
);}
int add(int x
,int v
) {for(int i
=x
;i
<=n
;i
+=lowbit(i
)) tr
[i
]+=v
;}
LL
query(int x
)
{LL sum
=0;for(int i
=x
;i
;i
-=lowbit(i
)) sum
+=tr
[i
];return sum
;
}
int main(void)
{cin
>>n
;for(int i
=1;i
<=n
;i
++) cin
>>a
[i
];for(int i
=n
;i
>=1;i
--){up
[i
]=query(n
)-query(a
[i
]);down
[i
]=query(a
[i
]-1);add(a
[i
],1);}memset(tr
,0,sizeof tr
);long long int ans1
=0,ans2
=0;for(int i
=1;i
<=n
;i
++){ans1
+=(query(n
)-query(a
[i
]))*up
[i
];ans2
+=query(a
[i
]-1)*down
[i
];add(a
[i
],1);}cout
<<ans1
<<" "<<ans2
<<endl
;return 0;
}
242. 一個(gè)簡(jiǎn)單的整數(shù)問(wèn)題【區(qū)間修改 / 單點(diǎn)查詢】
https://www.acwing.com/problem/content/description/248/
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5+10;
int tr
[N
],a
[N
],n
,m
;
int lowbit(int x
){return x
&(-x
);}
int add(int x
,int v
){for(int i
=x
;i
<=n
;i
+=lowbit(i
)) tr
[i
]+=v
;}
int query(int x
)
{int sum
=0;for(int i
=x
;i
;i
-=lowbit(i
)) sum
+=tr
[i
];return sum
;
}
int main(void)
{cin
>>n
>>m
;for(int i
=1;i
<=n
;i
++) cin
>>a
[i
],add(i
,a
[i
]-a
[i
-1]);while(m
--){string op
; cin
>>op
;if(op
=="C"){int l
,r
,c
; cin
>>l
>>r
>>c
;add(l
,c
),add(r
+1,-c
);}else {int x
; cin
>>x
;cout
<<query(x
)<<endl
;}}return 0;
}
243. 一個(gè)簡(jiǎn)單的整數(shù)問(wèn)題2【區(qū)間修改 / 區(qū)間查詢】
https://www.acwing.com/problem/content/description/244/
詳細(xì)題解
#include<bits/stdc++.h>
using namespace std
;
typedef long long int LL
;
const int N
=1e5+10;
LL tr1
[N
],tr2
[N
],a
[N
],n
,m
;
LL
lowbit(LL x
){return x
&(-x
);}
LL
add(LL tr
[],LL x
,LL v
){for(int i
=x
;i
<=n
;i
+=lowbit(i
)) tr
[i
]+=v
;}
LL
query(LL tr
[],LL x
)
{LL sum
=0;for(int i
=x
;i
;i
-=lowbit(i
)) sum
+=tr
[i
];return sum
;
}
LL
sum(LL x
)
{return query(tr1
,x
)*(x
+1)-query(tr2
,x
);
}
int main(void)
{cin
>>n
>>m
;for(int i
=1;i
<=n
;i
++){cin
>>a
[i
];LL b
=a
[i
]-a
[i
-1];add(tr1
,i
,b
);add(tr2
,i
,i
*b
);}while(m
--){string op
; cin
>>op
;if(op
=="C"){LL l
,r
,d
; cin
>>l
>>r
>>d
;add(tr1
,l
,d
),add(tr1
,r
+1,-d
);add(tr2
,l
,l
*d
),add(tr2
,r
+1,-d
*(r
+1));}else {LL l
,r
; cin
>>l
>>r
;cout
<<sum(r
)-sum(l
-1)<<endl
;}}return 0;
}
244. 謎一樣的牛【快速求排名擴(kuò)展】
https://www.acwing.com/problem/content/245/
詳細(xì)題解
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5+10;
int tr
[N
],a
[N
],b
[N
],n
;
int lowbit(int x
) {return x
&(-x
);}
int add(int x
,int v
) {for(int i
=x
;i
<=n
;i
+=lowbit(i
)) tr
[i
]+=v
;}
int query(int x
)
{int sum
=0;for(int i
=x
;i
;i
-=lowbit(i
)) sum
+=tr
[i
];return sum
;
}
int main(void)
{cin
>>n
;for(int i
=2;i
<=n
;i
++) cin
>>a
[i
];for(int i
=1;i
<=n
;i
++) add(i
,1);for(int i
=n
;i
>=1;i
--){int x
=a
[i
]+1;int l
=1,r
=n
;while(l
<r
){int mid
=l
+r
>>1;if(query(mid
)>=x
) r
=mid
;else l
=mid
+1;}b
[i
]=l
;add(l
,-1);}for(int i
=1;i
<=n
;i
++) cout
<<b
[i
]<<endl
;return 0;
}
線段樹(shù)
上圖摘自: https://www.acwing.com/blog/content/372/
線段樹(shù)常用的操作:
- pushup 由子節(jié)點(diǎn)的信息,來(lái)計(jì)算父節(jié)點(diǎn)的信息
- pushdown 由父節(jié)點(diǎn)更新子節(jié)點(diǎn)節(jié)點(diǎn)信息 lazytag(懶標(biāo)記)
- build 由區(qū)間建立線段樹(shù)
- modify 修改某一個(gè)點(diǎn)(easy)或者區(qū)間(hard)
- query 查詢某一端區(qū)間信息
線段樹(shù)常見(jiàn)的應(yīng)用場(chǎng)景:
- 單點(diǎn)修改
- 區(qū)間查詢
- 區(qū)間修改
相關(guān)的文章:https://www.cnblogs.com/jason2003/p/9676729.html
詳細(xì)理解線段樹(shù)
1275. 最大數(shù)【線段樹(shù) / 維護(hù)區(qū)間最大值】
https://www.acwing.com/problem/content/description/1277/
#include<bits/stdc++.h>
using namespace std
;
typedef long long int LL
;
const int N
=1e5*2+10;
int m
,p
;
struct node{int l
,r
,v
;}tr
[N
*4];
void pushup(int u
)
{tr
[u
].v
=max(tr
[u
<<1].v
,tr
[u
<<1 | 1 ].v
);
}
void build(int u
,int l
,int r
)
{tr
[u
]={l
,r
};if(l
==r
) return;int mid
=l
+r
>>1;build(u
<<1,l
,mid
),build(u
<<1|1,mid
+1,r
);
}
int query(int u
,int l
,int r
)
{if(tr
[u
].l
>=l
&&tr
[u
].r
<=r
) return tr
[u
].v
;int mid
=tr
[u
].l
+tr
[u
].r
>>1;int v
=0;if(l
<=mid
) v
=query(u
<<1,l
,r
);if(r
>mid
) v
=max(v
,query(u
<<1|1,l
,r
));return v
;
}
void modify(int u
,int x
,int v
)
{if(tr
[u
].l
==x
&&tr
[u
].r
==x
) tr
[u
].v
=v
;else{int mid
=tr
[u
].l
+tr
[u
].r
>>1;if(x
<=mid
) modify(u
<<1,x
,v
);else modify(u
<<1|1,x
,v
);pushup(u
);}
}
int main(void)
{int n
=0,last
=0;scanf("%d%d",&m
,&p
);build(1,1,m
);int x
;string op
;while(m
--){cin
>>op
>>x
;if(op
=="Q"){last
=query(1,n
-x
+1,n
);cout
<<last
<<endl
;}else {modify(1,n
+1,(1ll*last
+x
)%p
);n
++;}}return 0;
}
245. 你能回答這些問(wèn)題嗎【單點(diǎn)修改 求區(qū)間的最大連續(xù)子段和】
https://www.acwing.com/problem/content/246/
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5*5+10;
int n
,m
;
int w
[N
];
struct node
{int l
,r
;int sum
,lmax
,rmax
,tmax
;
}tr
[N
*4];
void pushup(node
&u
,node
&l
,node
&r
)
{u
.sum
=l
.sum
+r
.sum
;u
.lmax
=max(l
.lmax
,l
.sum
+r
.lmax
);u
.rmax
=max(r
.rmax
,r
.sum
+l
.rmax
);u
.tmax
=max(max(l
.tmax
,r
.tmax
),l
.rmax
+r
.lmax
);
}
void pushup(int u
)
{pushup(tr
[u
],tr
[u
<<1],tr
[u
<<1 | 1]);
}
void build(int u
,int l
,int r
)
{if(l
==r
) tr
[u
]={l
,r
,w
[r
],w
[r
],w
[r
],w
[r
]};else{tr
[u
]={l
,r
};int mid
=l
+r
>>1;build(u
<<1,l
,mid
),build(u
<<1|1,mid
+1,r
);pushup(u
);}
}
void modify(int u
,int x
,int v
)
{if(tr
[u
].l
==x
&&tr
[u
].r
==x
) tr
[u
]={x
,x
,v
,v
,v
,v
};else{int mid
=tr
[u
].l
+tr
[u
].r
>>1;if(x
<=mid
) modify(u
<<1,x
,v
);else modify(u
<<1|1,x
,v
);pushup(u
);}
}
node
query(int u
,int l
,int r
)
{if(tr
[u
].l
>=l
&&tr
[u
].r
<=r
) return tr
[u
];else{int mid
=tr
[u
].l
+tr
[u
].r
>>1;if(r
<=mid
) return query(u
<<1,l
,r
);else if(l
>mid
) return query(u
<<1|1,l
,r
);else{auto left
=query(u
<<1,l
,r
);auto right
=query(u
<<1|1,l
,r
);node res
;pushup(res
,left
,right
);return res
; }}
}
int main(void)
{cin
>>n
>>m
;for(int i
=1;i
<=n
;i
++) cin
>>w
[i
];build(1,1,n
);int k
,x
,y
;while(m
--){cin
>>k
>>x
>>y
;if(k
==1){if(x
>y
) swap(x
,y
);printf("%d\n",query(1,x
,y
).tmax
);}else modify(1,x
,y
);}return 0;
}
243. 一個(gè)簡(jiǎn)單的整數(shù)問(wèn)題2【區(qū)間修改 / 區(qū)間查詢】
https://www.acwing.com/problem/content/description/244/
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5+10;
typedef long long int LL
;
int n
,m
;
int w
[N
];
struct node
{int l
,r
;LL sum
,add
;
}tr
[N
*4];
void pushup(int u
)
{tr
[u
].sum
=tr
[u
<<1].sum
+tr
[u
<<1 | 1].sum
;
}
void pushdown(int u
)
{auto &root
=tr
[u
],&left
=tr
[u
<<1],&right
=tr
[u
<<1 | 1];if(root
.add
){left
.add
+=root
.add
,left
.sum
+=(LL
)(left
.r
-left
.l
+1)*root
.add
;right
.add
+=root
.add
,right
.sum
+=(LL
)(right
.r
-right
.l
+1)*root
.add
;root
.add
=0;}
}
void build(int u
,int l
,int r
)
{if(l
==r
) tr
[u
]={l
,r
,w
[r
],0};else{tr
[u
]={l
,r
};int mid
=l
+r
>>1;build(u
<<1,l
,mid
),build(u
<<1 | 1,mid
+1,r
);pushup(u
);}
}
void modify(int u
,int l
,int r
,int d
)
{if(tr
[u
].l
>=l
&&tr
[u
].r
<=r
){tr
[u
].sum
+=(LL
)(tr
[u
].r
-tr
[u
].l
+1)*d
;tr
[u
].add
+=d
;}else{pushdown(u
);int mid
=tr
[u
].l
+tr
[u
].r
>>1;if(l
<=mid
) modify(u
<<1,l
,r
,d
);if(r
>mid
) modify(u
<<1 | 1,l
,r
,d
);pushup(u
);}
}
LL
query(int u
,int l
,int r
)
{if(tr
[u
].l
>=l
&&tr
[u
].r
<=r
) return tr
[u
].sum
;pushdown(u
);int mid
=tr
[u
].l
+tr
[u
].r
>>1;LL sum
=0;if(l
<=mid
) sum
=query(u
<<1,l
,r
);if(r
>mid
) sum
+=query(u
<<1 | 1,l
,r
);return sum
;
}
int main(void)
{cin
>>n
>>m
;for(int i
=1;i
<=n
;i
++) cin
>>w
[i
];build(1,1,n
);while(m
--){string op
; cin
>>op
;if(op
=="Q"){int l
,r
; cin
>>l
>>r
;cout
<<query(1,l
,r
)<<endl
;}else{int l
,r
,d
; cin
>>l
>>r
>>d
;modify(1,l
,r
,d
);}}return 0;
}
1277. 維護(hù)序列【區(qū)間乘/加 區(qū)間查詢】
https://www.acwing.com/problem/content/1279/
#include<bits/stdc++.h>
using namespace std
;
typedef long long int LL
;
const int N
=1e5+10;
int n
,m
,p
;
int w
[N
];
struct node
{int l
,r
;int sum
,add
,mul
;
}tr
[N
*4];
void pushup(int u
)
{tr
[u
].sum
=(tr
[u
<<1].sum
+tr
[u
<<1 | 1].sum
)%p
;
}
void eval(node
&t
,int add
,int mul
)
{t
.sum
=((LL
)t
.sum
*mul
+(LL
)(t
.r
-t
.l
+1)*add
)%p
;t
.mul
=(LL
)t
.mul
*mul
%p
;t
.add
=((LL
)t
.add
*mul
+add
)%p
;
}
void pushdown(int u
)
{eval(tr
[u
<<1],tr
[u
].add
,tr
[u
].mul
);eval(tr
[u
<<1 | 1],tr
[u
].add
,tr
[u
].mul
);tr
[u
].add
=0,tr
[u
].mul
=1;
}
void build(int u
,int l
,int r
)
{if(l
==r
) tr
[u
]={l
,r
,w
[r
],0,1};else{tr
[u
]={l
,r
,0,0,1};int mid
=l
+r
>>1;build(u
<<1,l
,mid
),build(u
<<1|1,mid
+1,r
);pushup(u
);}
}
void modify(int u
,int l
,int r
,int add
,int mul
)
{if(tr
[u
].l
>=l
&&tr
[u
].r
<=r
) eval(tr
[u
],add
,mul
);else{pushdown(u
);int mid
=tr
[u
].l
+tr
[u
].r
>>1;if(l
<=mid
) modify(u
<<1,l
,r
,add
,mul
);if(r
>mid
) modify(u
<<1|1,l
,r
,add
,mul
);pushup(u
);}
}
int query(int u
,int l
,int r
)
{if(tr
[u
].l
>=l
&&tr
[u
].r
<=r
) return tr
[u
].sum
;pushdown(u
);int mid
=tr
[u
].l
+tr
[u
].r
>>1;int sum
=0;if(l
<=mid
) sum
=query(u
<<1,l
,r
);if(r
>mid
) sum
=(sum
+query( u
<< 1 | 1 ,l
,r
) )%p
;return sum
;
}
int main(void)
{cin
>>n
>>p
;for(int i
=1;i
<=n
;i
++) cin
>>w
[i
];build(1,1,n
);cin
>>m
;while(m
--){int op
; cin
>>op
;if(op
==1){int l
,r
,d
; cin
>>l
>>r
>>d
;modify(1,l
,r
,0,d
);}else if(op
==2){int l
,r
,d
; cin
>>l
>>r
>>d
;modify(1,l
,r
,d
,1);}else{int l
,r
; cin
>>l
>>r
;cout
<<query(1,l
,r
)<<endl
;}}return 0;
}
可持續(xù)化數(shù)據(jù)結(jié)構(gòu)
255. 第K小數(shù)【可持續(xù)化線段樹(shù) / 主席樹(shù)】
https://www.acwing.com/problem/content/257/
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e5+10;
int n
,m
;
int a
[N
];
vector
<int>nums
;
struct Node
{int l
,r
;int cnt
;
}tr
[N
*4+N
*17];
int root
[N
],idx
;
int find(int x
)
{return lower_bound(nums
.begin(),nums
.end(),x
)-nums
.begin();
}
int build(int l
,int r
)
{int p
=++idx
;if(l
==r
) return p
;int mid
=l
+r
>>1;tr
[p
].l
=build(l
,mid
),tr
[p
].r
=build(mid
+1,r
);return p
;
}
int insert(int p
,int l
,int r
,int x
)
{int q
=++idx
;tr
[q
]=tr
[p
];if(l
==r
){tr
[q
].cnt
++;return q
;}int mid
=l
+r
>>1;if(x
<=mid
) tr
[q
].l
=insert(tr
[p
].l
,l
,mid
,x
);else tr
[q
].r
=insert(tr
[p
].r
,mid
+1,r
,x
);tr
[q
].cnt
=tr
[tr
[q
].l
].cnt
+tr
[tr
[q
].r
].cnt
;return q
;
}
int query(int q
,int p
,int l
,int r
,int k
)
{if(l
==r
) return r
;int cnt
=tr
[tr
[q
].l
].cnt
-tr
[tr
[p
].l
].cnt
;int mid
=l
+r
>>1;if(k
<=cnt
) return query(tr
[q
].l
,tr
[p
].l
,l
,mid
,k
);else return query(tr
[q
].r
,tr
[p
].r
,mid
+1,r
,k
-cnt
);
}
int main(void)
{scanf("%d%d",&n
,&m
);for(int i
=1;i
<=n
;i
++){scanf("%d",&a
[i
]);nums
.push_back(a
[i
]);}sort(nums
.begin(),nums
.end());nums
.erase(unique(nums
.begin(),nums
.end()),nums
.end());root
[0]=build(0,nums
.size()-1);for(int i
=1;i
<=n
;i
++)root
[i
]=insert(root
[i
-1],0,nums
.size()-1,find(a
[i
]));while(m
--){int l
,r
,k
; scanf("%d%d%d",&l
,&r
,&k
);printf("%d\n",nums
[query(root
[r
],root
[l
-1],0,nums
.size()-1,k
)]);}return 0;
}
AC自動(dòng)機(jī)
1282. 搜索關(guān)鍵詞
https://www.acwing.com/problem/content/description/1284/
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e4+10,S
=55,M
=1e6+10;
int n
;
int tr
[N
*S
][26],cnt
[N
*S
],idx
;
char str
[M
];
int q
[N
*S
],ne
[N
*S
];
void insert()
{int p
=0;for(int i
=0;str
[i
];i
++){int t
=str
[i
]-'a';if(!tr
[p
][t
]) tr
[p
][t
]=++idx
;p
=tr
[p
][t
];}cnt
[p
]++;
}
void build()
{int hh
=0,tt
=-1;for(int i
=0;i
<26;i
++)if(tr
[0][i
]) q
[++tt
]=tr
[0][i
];while(hh
<=tt
){int t
=q
[hh
++];for(int i
=0;i
<26;i
++){int p
=tr
[t
][i
];if(!p
) tr
[t
][i
]=tr
[ne
[t
]][i
];else{ne
[p
]=tr
[ne
[t
]][i
];q
[++tt
]=p
;}}}
}
int main(void)
{int t
; cin
>>t
;while(t
--){memset(tr
,0,sizeof tr
);memset(cnt
,0,sizeof cnt
);memset(ne
,0,sizeof ne
);idx
=0;cin
>>n
;for(int i
=0;i
<n
;i
++){scanf("%s",str
);insert();}build();scanf("%s",str
);int res
=0;for(int i
=0,j
=0;str
[i
];i
++){int t
=str
[i
]-'a';j
=tr
[j
][t
];int p
=j
;while(p
){res
+=cnt
[p
];cnt
[p
]=0;p
=ne
[p
];}}printf("%d\n",res
);}return 0;
}
1285. 單詞
https://www.acwing.com/problem/content/1287/
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e6+10;
int n
;
int tr
[N
][26],f
[N
],idx
;
int q
[N
],ne
[N
];
char str
[N
];
int id
[210];
void insert(int x
)
{int p
=0;for(int i
=0;str
[i
];i
++){int t
=str
[i
]-'a';if(!tr
[p
][t
]) tr
[p
][t
]=++idx
;p
=tr
[p
][t
];f
[p
]++;}id
[x
]=p
;
}
void build()
{int hh
=0,tt
=-1;for(int i
=0;i
<26;i
++)if(tr
[0][i
]) q
[++tt
]=tr
[0][i
];while(hh
<=tt
){int t
=q
[hh
++];for(int i
=0;i
<26;i
++){int &p
=tr
[t
][i
];if(!p
) p
=tr
[ne
[t
]][i
];else {ne
[p
]=tr
[ne
[t
]][i
];q
[++tt
]=p
;}}}
}
int main(void)
{scanf("%d",&n
);for(int i
=0;i
<n
;i
++){scanf("%s",str
);insert(i
);}build();for(int i
=idx
-1;i
>=0;i
--) f
[ne
[q
[i
]]]+=f
[q
[i
]];for(int i
=0;i
<n
;i
++) printf("%d\n",f
[id
[i
]]);return 0;
}
總結(jié)
以上是生活随笔為你收集整理的第四章 高级数据结构的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
