树状数组例题

就这树状数组的题做下来没有一点成就感，看一遍题，看不懂，看了题解的思路，不明白，照着题解的代码一行一行看下去才最终理解，然后敲了一遍，不明不白的就过了，所以写一篇来理顺一下思路

tip：用树状数组做题的时候不要总想着树状数组，就当他是个修改和查询都是 \(O(\log n)\) 级别的前缀和就好

很多题看上去没有思路，但找到一个排序策略（也就是优先处理什么，后处理什么）思路就明朗了。

P3374 【模板】树状数组 1

洛谷链接

题目描述

单点修改，区间查询。

解题思路

树状数组直接对原数组进行维护即可。

Code

// Problem: 
//     P3374 【模板】树状数组 1
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3374
// Memory Limit: 512 MB
// Time Limit: 1000 ms

#include<bits/stdc++.h>
using namespace std;
int n,m,a[500005];
int c[500005];//树状数组
int lowbit(int x){
	return x & (-x);
}
void add(int x,int v){
	while(x<=n){
		c[x]+=v;
		x+=lowbit(x);
	}
}
int sum(int x){
	int ret=0;
	while(x>0){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		add(i,a[i]);
	}
	for(int i=1;i<=m;i++){
		int op,x,y;cin>>op>>x>>y;
		if(op==1){
			add(x,y);
		}else{
			cout<<sum(y)-sum(x-1)<<endl;
		}
	}
	return 0;
}

P3368 【模板】树状数组 2

洛谷链接

题目描述

区间修改，单点查询。

解题思路

依旧是模板树状数组，只不过对于这种区间修改我们可以使用树状数组去维护一个差分数组。

Code

// Problem: 
//     P3368 【模板】树状数组 2
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3368
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include<bits/stdc++.h>
using namespace std;
int n,m,a[500005],d[500005],c[500005];
int lowbit(int x){
	return x & (-x);
}
void add(int x,int v){
	while(x<=n){
		c[x]+=v;
		x+=lowbit(x);
	}
}
int sum(int x){
	int ret=0;
	while(x>0){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		d[i]=a[i]-a[i-1];
		add(i,d[i]);
	}
	for(int i=1;i<=m;i++){
		int op,x;cin>>op>>x;
		if(op==1){
			int y,k;cin>>y>>k;
			add(x,k),add(y+1,-k);
		}else{
			cout<<sum(x)<<endl;
		}
	}
	return 0;
}

P1774 最接近神的人

洛谷链接

题目描述

求逆序对

解题思路

先将序列按照数值从大到小排序（用结构体，别忘了记录在原序列中的位置），如果相同就按照出现的顺序逆序排序（即后出现的在前）。每次都计算当前元素在原序列的位置前面有多少个已经考虑过得，因为是从大到小考虑，所以肯定都比现在这个大。

代码

// Problem: 
//     P1774 最接近神的人
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1774
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include<bits/stdc++.h>
using namespace std;
struct node{
	int val,pos;
}bar[500005];//排序
int n,a[500005];
long long ans;//别忘了开long long
int c[500005];//树状数组
bool cmp(node lhs,node rhs){
	if(lhs.val==rhs.val)
		return lhs.pos>rhs.pos;
	return lhs.val>rhs.val;
}//排序，如果相等就让后出现的在前
int lowbit(int x){
	return x & (-x);
}
void add(int x,int v){
	while(x<=n){
		c[x]+=v;
		x+=lowbit(x);
	}
}
int sum(int x){
	int ret=0;
	while(x>0){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];//其实这里不要a数组也行
		bar[i].val=a[i],bar[i].pos=i;
	}
	sort(bar+1,bar+1+n,cmp);//排序，第一次提交写了cmp忘了写sort QWQ
	for(int i=1;i<=n;i++){
		add(bar[i].pos,1);//在当前位置放一个1，表示这里有一个数
		ans+=sum(bar[i].pos-1);
		//表示在他之前有多少数，因为是从大到小考虑，所以都比当前大
	}
	cout<<ans;//输出
	return 0;//结束
}

P2345 [USACO04OPEN] MooFest G

洛谷链接

题目描述

约翰的 \(n\) 头奶牛每年都会参加“哞哞大会”。

它们参加活动时会聚在一起，第 \(i\) 头奶牛的坐标为 \(x_i\)，没有两头奶牛的坐标是相同的。

奶牛们的叫声很大，第 \(i\) 头和第 \(j\) 头奶牛交流，会发出 \(\max\{v_i,v_j\}\times |x_i − x_j |\) 的音量，其中 \(v_i\) 和 \(v_j\) 分别是第 \(i\) 头和第 \(j\) 头奶牛的听力。

假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。

解题思路

很显然，我们可以 \(O(n^2)\) 枚举两头牛 \(i,j\) 但这样的话超时是必然的。

我们可以对这个公式进行一些优化。

对于 \(\max\) 很容易想到我们可以按听力从小到大排序，这样我们每次新加入一头牛的时候他的听力肯定是最大的。

让我们来对样例模拟一下（先排序）

先放进去一头

这个时候他旁边没有牛，不发出声音。

再放第二头

这个时候，他前面有一头牛，于是发出了 \(2 \times (6-5)\) 的声音

三号牛后面有两头，于是它发出了 \(3 \times (5-1)+3 \times (6-1)\) 的声音。

化简可得 \(3 \times (5-1+6-1)\) 即 \(3 \times [(5+6)-(1 \times 2)]\) 。发现什么了吗？

让我们继续往下看：

他总共需要发出 \(4 \times [(3 \times 1) - 1] + 4 \times [(5+6)-(3\times 2)]\) 。

规律已经显而易见了。设 \(x_f,x_b\) 为前面、后面牛的坐标和，设 \(c_f,c_b\) 为前面、后面牛的个数。

那么对于每一次加牛的操作，我们就可以把公式简化为 \(v_i \times (x_i \times c_f - x_f)+v_i \times (x_b - x_i \times c_b)\) 。

这样一来，我们就只需要知道前后牛的个数和坐标和就好了，正好可以用树状数组。

Code

// Problem: 
//     P2345 [USACO04OPEN] MooFest G
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2345
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
	ll v,pos;
}cow[20004];
ll n,treec[20004],treev[20004],maxpos=0;//两个数组，分别计算个数和坐标
bool cmp(node lhs,node rhs){return lhs.v<rhs.v;}//按听力排序
ll lowbit(int x){return x & (-x);}
void add(ll c[],int x,int v){//ll c[]相当于直接传入一个数组的地址，这样就不用写两遍功能重复的函数了
	while(x<=maxpos){
		c[x]+=v;
		x+=lowbit(x);
	}
}
ll query(ll c[],int x){//同上
	ll ret=0;
	while(x>0){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>cow[i].v>>cow[i].pos;
		maxpos=max(maxpos,cow[i].pos);
	}
	sort(cow+1,cow+1+n,cmp);
	ll ans=0,sp=0;
	for(int i=1;i<=n;i++){
		int fc=query(treec,cow[i].pos);//前面有多少牛
		int bc=i-fc-1;//后面有多少牛
		int fp=query(treev,cow[i].pos);//前面的坐标和
		int bp=sp-fp;//后面的坐标和
		ans+=cow[i].v*(cow[i].pos*fc-fp)+cow[i].v*(bp-bc*cow[i].pos);
		sp+=cow[i].pos;//到现在牛的坐标和，因为要计算后面牛的坐标和，所以需要记录
		add(treec,cow[i].pos,1);//分别往两个数组中加入
		add(treev,cow[i].pos,cow[i].pos);
	}
	cout<<ans;//输出
	return 0;//结束
}

P1637 三元上升子序列

洛谷链接

题目描述

Erwin 最近对一种叫 thair 的东西巨感兴趣。。。

在含有 \(n\) 个整数的序列 \(a_1,a_2,\ldots,a_n\) 中，三个数被称作thair当且仅当 \(i<j<k\) 且 \(a_i<a_j<a_k\)。

求一个序列中 thair 的个数。

解题思路

很明显，我们可以枚举中间元素，设 \(l_i\) 为 \(i\) 前面小于 \(i\) 的数的个数， \(r_i\) 为在 \(i\) 后面且大于 \(i\)

的数的个数，根据乘法原理，以 \(i\) 为中间那个数的三元组的个数为 \(l_i \times r_i\) 。

那么现在问题就转移成了如何求一个数前面有多少数小于他呢？（大于同理，这里只说小于的情况）

很显然，我们可以用树状数组。先按升序排序，然后类比求逆序对的方法来求就行了。

值得一提的是，为了方便处理，我还用了一下离散化。

Code

// Problem: 
//     P1637 三元上升子序列
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1637
// Memory Limit: 128 MB
// Time Limit: 1000 ms

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[30004];
int top;
int b[30004];
int lef[30004],rig[30004];
int tmi[30004],tma[30004];//两个树状数组，一个计算大于，另一个计算小于
//我的代码有两个数组，一个是树状数组，另一个也是树状数组~~
int lowbit(int x){//树状数组函数组
	return x & (-x);
}
int mapping(int x){//离散化的映射函数
	return lower_bound(b,b+1+top,x)-b;
}
void add(int c[],int x,int v){//树状数组函数组
	while(x<=n){
		c[x]+=v;
		x+=lowbit(x);
	}
}
int sum(int c[],int x){//树状数组函数组
	int ret=0;
	while(x>0){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];//离散化记录
	}
	sort(b+1,b+1+n);//排序
	top=unique(b+1,b+1+n)-b-1;//去重
	for(int i=1;i<=n;i++){//计算左侧小于
		lef[i]=sum(tmi,mapping(a[i])-1);
		add(tmi,mapping(a[i]),1);
	}
	for(int i=n;i>=1;i--){//计算右侧大于
		rig[i]=n-i-sum(tma,mapping(a[i]));
		add(tma,mapping(a[i]),1);
	}
	ll ans=0;//统计求和，别忘了long long
	for(int i=1;i<=n;i++)
		ans+=lef[i]*rig[i];
	cout<<ans;
	return 0;//结束
}

P3660 [USACO17FEB] Why Did the Cow Cross the Road III G

洛谷链接

题目描述

给定长度为 \(2\times N\) 的序列， \(1 \sim N\) 各出现过2次， \(i\) 第一次出现位置记为 \(a_i\) ，第二次记为 \(b_i\)，求满足 \(a_i<a_j<b_i<b_j\) 的对数。

解题思路

我们可以先思考一个假的做法：记录下每个元素的起始位置和终止位置，直接按 \(i\sim N\) 的顺序枚举， \(ans \leftarrow ans + sum(right_i) - sum(left_i)\) 其中的 \(sum(right_i)\) 和 \(sum(left_i)\) 都是树状数组的查询函数，然后再将两端点的位置各加一。

这个做法有一个显然错误的地方：有可能我们有一个区间同时包含了前面一个某个区间的两个端点，而这种情况本来应该加零我们却加了二。

既然这样就放弃这种做法再另想一种吧

哎，等等，先别想着放弃，难道这种做法没有改进空间了吗？

导致刚刚那种做法失败的原因显然是因为当现在的区间比之前考虑过的区间更大的时候，我们会多算两个。

换句话说，是因为在计算当前区间之前，我们计算了两端点间距离比他更小的区间。

想到这一点，改进的方法就显而易见了。

联系一开始我说的那句话：排序啊。

只要我们按照两端点跨度大小进行降序排序，这样以来，在对每个区间思考的时候，之前就只可能考虑过两端点间跨度大于等于它的区间，这样就无论如何都不可能同时包括一个区间的两个端点了。

Code

// Problem: 
//     P3660 [USACO17FEB] Why Did the Cow Cross the Road III G
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3660
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
	int id,fir,sec;
}as[50004];
int n,a[100004];
int c[100004];
bool cmp(node lhs,node rhs){//做法正确的关键：排序
	return lhs.sec-lhs.fir>rhs.sec-rhs.fir;
}
int lowbit(int x){
	return x & (-x);
}
void add(int x,int v){
	while(x<=n*2){
		c[x]+=v;
		x+=lowbit(x);
	}
}
ll sum(int x){
	ll ret=0;
	while(x>0){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}
int main(){
	cin>>n;
	for(int i=1;i<=n*2;i++){
		cin>>a[i];
		if(as[a[i]].fir==0){//记录区间的两端点
			as[a[i]].fir=i;
		}else
			as[a[i]].sec=i;
	}
	sort(as+1,as+1+n,cmp);//排序
	ll ans=0;
	for(int i=1;i<=n;i++){
		add(as[i].fir,1);
		add(as[i].sec,1);
		ans+=sum(as[i].sec-1)-sum(as[i].fir);
		//这里先加进来还是先统计都可以，如果是先加进来的话别忘了右端点-1，不然直接WA
	}
	cout<<ans;//输出结果
	return 0;//结束
}

P3253 [JLOI2013] 删除物品

洛谷链接

题目描述

箱子再分配问题需要解决如下问题：

1. 一共有 \(N\) 个物品，堆成 \(M\) 堆。

2. 所有物品都是一样的，但是它们有不同的优先级。

3. 你只能够移动某堆中位于顶端的物品。

4. 你可以把任意一堆中位于顶端的物品移动到其它某堆的顶端。若此物品是当前所有物品中优先级最高的，可以直接将之删除而不用移动。

5. 求出将所有物品删除所需的最小步数。删除操作不计入步数之中。

6. 这是一个比较难解决的问题，这里你只需要解决一个比较简单的版本：不会有两个物品有着相同的优先级，且 \(M=2\) 。

解题思路

我们不妨先手动模拟几遍样例，然后，你就会发现：无论怎么移动栈顶物品，每个物品的相对位置总是不变的。

然后我就（看了题解）有了这样一个想法：我们可以把两个栈的顶端连接起来。

这样一来，我们只需要用一个变量记录一下两个栈顶相接的位置，排序后依次将栈顶指针移动到当前最大的元素旁边，记录下中间跨过的元素个数就好了。

可是中间跨过的元素个数该怎么记录呢？（假装不知道这是树状数组题单的屑）

先考虑一种暴力做法：开一个 \(vis[]\) 数组，表示某个元素是否已经被删除。

在知道移动的距离之后，我们就可以便利一遍 \(vis[]\) 数组，并进行求和。

超时是显然的，但是看到这个过程你有没有想到什么？

我们需要对一个数组进行单点修改，区间查询。这是什么？这不就是树状数组的例题吗！

优化之后就可以轻松AC了。

Code

// Problem: 
//     P3253 [JLOI2013] 删除物品
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3253
// Memory Limit: 125 MB
// Time Limit: 1000 ms

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
	int id,val;
}a[200005];
int n,m,c[100005];
bool cmp(node lhs,node rhs){
	return lhs.val>rhs.val;
}
int lowbit(int x){
	return x & (-x);
}
void add(int x,int v){
	while(x<=n+m){
		c[x]+=v;
		x+=lowbit(x);
	}
}
int sum(int x){
	int ret=0;
	while(x>0){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}
int main(){
	cin>>n>>m;
	for(int i=n;i>=1;i--){
		cin>>a[i].val;
		a[i].id=i;
		add(i,1);
	}
	for(int i=n+1;i<=n+m;i++){
		cin>>a[i].val;
		a[i].id=i;
		add(i,1);
	}//输入顺便拼接两个栈
	sort(a+1,a+1+n+m,cmp);
	//按大小排序，因为要从大到小删，同时别忘了记录下每个元素位置，统计距离时要用
	ll ans=0;//记得开long long
	int p=n;//栈顶指针
	for(int i=1;i<=n+m;i++){
		ans+=abs(sum(p)-sum(a[i].id))-(p<a[i].id);//统计
		add(a[i].id,-1);//标记此元素已经删去
		p=a[i].id-(p<a[i].id);
		//移动顶指针，bool表达式在为真时返回1，省去一层if
	}
	cout<<ans;//输出别忘了（应该不会有人连这个都忘吧）
	return 0;//结束
}

P1972 [SDOI2009] HH的项链

洛谷链接

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。

有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答…… 因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

解题思路

这应该也算一种区间求和。。。吧？只不过我们在求和的时候如果有重复的应该略过。

怎么做呢？首先，我们如果我们这道题暴力去解的话会发现，其实对于重复的元素来说，我们只需要关注他在这个区间最后一次，或者说第一次出现在哪里。

就按最后一次出现的来看，在右端点固定的情况下，无论一个数在前面出现了几次。

只要他的左端点包含了这个数字最后一次出现的位置，那就包含了，如果他的左端点连这个数最后一次出现的位置都没有包含，那这个区间就没有包含这个数。（这不废话吗）

不难发现，只要我们按照右端点从小到大进行排序，然后每次从上次的右端点到这次的右端点处理一下：记录最后一次出现，然后把倒数第二次出现的标记给清除。

Code

// Problem: 
//     P1972 [SDOI2009] HH的项链
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1972
// Memory Limit: 512 MB
// Time Limit: 2000 ms

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct ques{
	int l,r,id,ans;
}q[1000006];
int read(){//题目已经提醒你了，用快读 
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,a[1000006];
int m,c[1000006];
int vis[1000006];
int ans[1000006];//整齐的定义 
bool cmp(ques lhs,ques rhs){//按照右端点从小到大排序 
	return lhs.r<rhs.r;
}
int lowbit(int x){
	return x & (-x);
}
void add(int x,int v){
	while(x<=n){
		c[x]+=v;
		x+=lowbit(x);
	}
}
int sum(int x){
	int ret=0;
	while(x>0){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	m=read();
	for(int i=1;i<=m;i++)
		q[i].l=read(),q[i].r=read(),q[i].id=i;
	sort(q+1,q+1+m,cmp);//按右端点从小到大进行排序 
	int now=1;//标记当前已经处理到第几个数，即上一个的右端点到哪 
	for(int i=1;i<=m;i++){
		for(;now<=q[i].r;now++){//循环变量是now，第一项直接跳过就好，当然这里最好用while 
			if(!vis[a[now]]){//也就是if(vis[a[now]]==0)，成立则表示a[now]是第一次出现
			//去掉这一层判断会执行add(0,-1),直接zb(划掉)死循环，还要在add()里加一个判断 
				add(now,1);
				vis[a[now]]=now;
			}else{
				add(vis[a[now]],-1);
				add(now,1);
				vis[a[now]]=now;
			}
		}
		ans[q[i].id]=sum(q[i].r)-sum(q[i].l-1);//先处理，再统计 
	}
	for(int i=1;i<=m;i++)
		cout<<ans[i]<<endl;//由于不是按照输入顺序计算的，最后再输出 
	return 0;//结束 
}

P3605 [USACO17JAN] Promotion Counting P

洛谷链接

题目描述

奶牛们又一次试图创建一家创业公司，还是没有从过去的经验中吸取教训——牛是可怕的管理者！

为了方便，把奶牛从 \(1 \sim N\) 编号，把公司组织成一棵树， \(1\) 号奶牛作为总裁（这棵树的根节点）。除了总裁以外的每头奶牛都有一个单独的上司（它在树上的 “双亲结点”）。

所有的第 \(i\) 头牛都有一个不同的能力指数 \(p_i\) ，描述了她对其工作的擅长程度。如果奶牛 \(i\) 是奶牛 \(j\) 的祖先节点，那么我们我们把奶牛 \(j\) 叫做 \(i\) 的下属。

不幸地是，奶牛们发现经常发生一个上司比她的一些下属能力低的情况，在这种情况下，上司应当考虑晋升她的一些下属。你的任务是帮助奶牛弄清楚这是什么时候发生的。简而言之，对于公司的中的每一头奶牛 \(j\) ，请计算其下属 \(j\) 的数量满足 \(p_j>p_i\) 。

解题思路

这道题可以 dfs ，先保存 不计算 \(x\) 的下属时，有多少人比 \(x\) 强，然后 dfs 的去计算 \(x\) 的所有下属，然后在 \(x\) 的下属中比 \(x\) 强的人数就是 计算 \(x\) 的下属后比 \(x\) 强的人数减去不计算 \(x\) 的下属时比 \(x\) 强的人数。

Code

// Problem: 
//     P3605 [USACO17JAN] Promotion Counting P
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3605
// Memory Limit: 128 MB
// Time Limit: 1000 ms

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
	int u,v;
	int next;
}eg[100005];
int ans[100005];
int idx[100005],top;
int n,p[100005],c[100005];
int b[100005];
int lowbit(int x){
	return x & (-x);
}
void add(int x,int v){
	while(x<=n){
		c[x]+=v;
		x+=lowbit(x);
	}
}
int sum(int x){
	int ret=0;
	while(x>0){
		ret+=c[x];
		x-=lowbit(x);
	}
	return ret;
}
void dfs(int x){//递归 
	ans[x]=sum(p[x])-sum(n);//不计算x的下属时比x强的人 
	for(int i=idx[x];i!=0;i=eg[i].next)
		dfs(eg[i].v);//计算x的每个下属 
	ans[x]+=sum(n)-sum(p[x]);//计算x的下属中，比x强的人 
	add(p[x],1);//在x的能力值处有一个人 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i];b[i]=p[i];//进行离散化，p[i]最大值是1e9，数组直接开会炸 
	}
	sort(b+1,b+1+n);
	for(int i=1;i<=n;i++)
		p[i]=lower_bound(b+1,b+1+n,p[i])-b;//离散化 
	for(int i=2;i<=n;i++){//前向星存树也行 
		int t;cin>>t;
		eg[++top].u=t;
		eg[top].v=i;
		eg[top].next=idx[t];
		idx[t]=top;
	}
	dfs(1);//递归 
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<endl;//输出结果 
	return 0;
}

本栏目推荐文章
• 类模板实现简单的数组
• 数组内存图
• 数组
• 1.12_redis 的存取在最后 晚上_浙江本地环境的header不能用线上的_header中host和refer分别代表什么意思?_模型的save()参数是数组怎么理解?
• 吴师兄学算法day06 双指针 80. 合并两个有序数组
• C# 方法中的参数数组
• 吴师兄学算法day06 双指针 26. 删除有序数组中的重复项
• 打印稀疏数组
• 吴师兄学算法day06 双指针 88. 合并两个有序数组
• C语言中这几种数组，弄明白了吗？int(*pai[2])[5]，int *aapi[2][2]， int **p[2]， int *numT[5]， int(*num2)[5]

例题 数组例题 数组 例题 例题list 例题deque 蓝桥 例题 例题 经典 蓝桥 例题 卡片 例题 课本 例题 第三章 部分 线段 例题