线段树复习小结

wujingfey · 2023-10-03 17:01:27 · 算法·理论

此博客长期不定时更新！

线段树基础

线段树简介

线段树是一种高级数据结构，支持快速的进行区间修改、加减、求最值、求和等操作，效率很高，一次修改查询复杂度均为 \log_2n，但拥有较大常数

能处理的问题

用于维护区间信息，要求这些维护的信息满足可加性，即某个区间的信息可以通过将两个子区间的信息进行一些计算得到。当然这个计算可以是简单地四则运算，也可能是复杂的递归合并。具体后文再说。

复杂度

建树过程是 n，修改、查询复杂度均为 \log_2n。

原理

将一个线段的不同区间用一棵二叉树表示，树上每个点都代表一个区间的信息。

基础样例

以区间和为例，样板程序如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
    int res=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        res=(res<<3)+(res<<1)+c-'0';
        c=getchar();
    }
    return res*f;
}
const int N=1e6+5;
int n,q,a[N];//原数组
struct N{
    int l,r,sum,lz;
}tr[N<<2];//线段树结构体
void push_up(int p){//自下而上更新区间答案
    tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
}
void build(int p,int l,int r){//建树，l是区间左界，r区间右界
    tr[p].l=l; tr[p].r=r;
    tr[p].sum=tr[p].lz=0;
    if(l==r){//更新到叶子结点
        tr[p].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;//二分
    build(p<<1,l,mid);//左边建树
    build(p<<1|1,mid+1,r);//右边建树
    push_up(p);//通过子区间答案更新区间和
}
void f(int p,int k){//区间更改，只更新父节点，子节点更改值用lz表示
    tr[p].sum+=(tr[p].r-tr[p].l+1)*k;
    tr[p].lz+=k;
}
void push_down(int p){//下传懒标记
    f(p<<1,tr[p].lz);
    f(p<<1|1,tr[p].lz);
    tr[p].lz=0;
}
void updata(int p,int nl,int nr,int k){//区间修改
    if(nl<=tr[p].l&&tr[p].r<=nr){//当前区间⊆修改区间
        f(p,k);
        return;
    }
    push_down(p);//要对子区间修改了，必须要往下传懒标记
    int mid=(tr[p].l+tr[p].r)>>1;
    if(nl<=mid) updata(p<<1,nl,nr,k);
    if(mid<nr) updata(p<<1|1,nl,nr,k);
    push_up(p);//子区间修改完后，必须要上传答案
}
int query(int p,int nl,int nr){//区间查询
    int res=0;
    if(nl<=tr[p].l&&tr[p].r<=nr){//当前区间⊆修改区间
        return tr[p].sum;
    } 
    push_down(p);//要查询子区间，也必须下传懒标记
    int mid=(tr[p].l+tr[p].r)>>1;
    if(nl<=mid) res+=query(p<<1,nl,nr);
    if(mid<nr) res+=query(p<<1|1,nl,nr);
    return res;
} 
signed main(){
    n=read(),q=read();
    for(int i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    for(int i=1;i<=q;i++){
        int op=read(),x,y,z;
        if(op==1){//修改
            x=read(),y=read(),z=read();
            updata(1,x,y,z);
        }else{//查询
            x=read(),y=read();
            printf("%lld\n",query(1,x,y));
        }
    }
    return 0;
}

懒标记

懒标记打在一个根节点上，表示这个根节点的子树均进行了同样的操作。这是一个标记，因此子树实际上是没有更改的，只有象征性更改。所以在实际修改、查询的时候，我们一定要下传懒标记。不然我们就“徒有其名”了——第一次更新时，我不需要把每个值都更新，就只给他打上标记告诉我们下次使用时要记得更新，第二次需要更新时又把懒标记忘了，懒标记变相相当于没打。

因此我对懒标记的理解就是，如果一个子树发生了修改，但目前并不需要用到这些修改时，我就先不修改，用懒标记记录一下“我现在欠这个子树一次修改”，到后面需要用到这次修改的信息时，我再根据懒标记把欠下的修改还回去。 我们可以以此来理解后续的更多操作。

线段树进阶（如何处理多种操作）

线段树维护加、乘操作模板传送门:[维护加乘线段树]

题意：给定一个长度为 n 的序列 a，存在四种操作：

在 [l,r] 加上一个数 x。
在 [l,r] 乘上一个数 x。
把 [l,r] 上的每一个数变成 x-a_i,i\in [l,r]
求 \sum_{i=l}^r a_i。

其中 1\le n \le 10^5,1\le q \le 10^5,-10^3\le a_i,x_ \le 10^3，所有答案对 10^9+7 取模。

思路分析

首先要明确一点，我们其实不需要专门维护操作 3，因为把 [l,r] 上的每一个数变成 x-a_i,i\in [l,r]，等效于先把 [l,r] 上的每一个数乘上 -1，再加上 x。所以我们只需要维护加乘操作即可。

维护加乘双懒标记

多种操作的线段树其他部分与基础线段树大差不差，但懒标记要格外注意：我们该如何维护双标记呢？

理性理解法

根据上文对懒标记的理解，懒标记其实是对操作的赊欠。我们根据情况分类讨论一下：

如果现在某子树有一个加法标记 lz1，又下传了一个加法标记 lz1'，直接相加即可。
如果现在某子树有一个乘法标记 lz2，又下传了一个乘法标记 lz2'，相当于子树每一个节点要先乘以 lz2 再乘以 lz2'，显然根据乘法结合律，等于乘以 lz2*lz2'。
如果现在某子树有一个加法标记 lz1，又下传了一个乘法标记 lz2，相当于子树每一个节点要先加上 lz1，再乘以 lz2，根据加法分配律，等于每个节点先乘以 lz2 再加上 lz1*lz2。这也解释了为什么要先乘再加——下传前我们已经把加法标记乘以了 lz2，下传时的 lz2 应该只针对原区间的数（如果再针对加法标记，是不是相当于加法标记乘以了 lz2^2？
如果现在某子树有一个乘法标记 lz2，又下传了一个加法标记 lz1，显然先对每个元素乘了，再加上即可。

根据上面的一系列分析，我总结出了两个毒点：

*lz2 表示的是某个子树要乘以的倍数，所以应当初始化为 1，表示 1 倍关系。而且对于多次乘，根据结合律，乘数也应该相乘，而不该相加。即：维护时 $lz2'\gets lz2_1lz2_2$。**
在打下 lz2 时我们已经对于存在的 lz1 进行维护了，所以下传时我们只因该对原区间进行修改，所以应该先乘后加（否则加维护了两次）。

感性理解法

由于我们将懒标记和区间元素分别维护，所以在下传 lz2 的修改应该只对元素值进行修改，所以要先乘后加。

维护更多标记

（虽然大多数情况加乘都够用了）如果遇到其他情况需要维护更多标记，也一定要牢记：我们是把懒标记和区间元素单独维护的，所以要按照上文提到的逻辑，摸清修改的顺序。

练习运用: 扶苏的问题（区间加、修）

AC 代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int res=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        res=(res<<3)+(res<<1)+c-'0';
        c=getchar();
    }
    return res*f;
}
const int N=1e6+10,INF=1e18+10;
int n,q,a[N];
struct NODE{
    int l,r,lz1,lz2,maxx;
}tr[N<<2];
void push_up(int p){
    tr[p].maxx=max(tr[p<<1].maxx,tr[p<<1|1].maxx);
}
void build(int p,int l,int r){
    tr[p].l=l,tr[p].r=r;
    tr[p].lz1=0,tr[p].lz2=INF;
    if(l==r){
        tr[p].maxx=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    push_up(p);
}
void f1(int p,int k){
    tr[p].maxx+=k;
    tr[p].lz1+=k;
}
void f2(int p,int k){
    tr[p].maxx=k;
    tr[p].lz1=0;
    tr[p].lz2=k;
}
void push_down(int p){
    if(tr[p].lz2!=INF){
        f2(p<<1,tr[p].lz2);
        f2(p<<1|1,tr[p].lz2);
        tr[p].lz2=INF;
    }
    f1(p<<1,tr[p].lz1);
    f1(p<<1|1,tr[p].lz1);
    tr[p].lz1=0;
}
void updata1(int p,int nl,int nr,int k){
    if(nl<=tr[p].l&&tr[p].r<=nr){
        f1(p,k);
        return;
    }
    push_down(p);
    int mid=(tr[p].l+tr[p].r)>>1;
    if(nl<=mid) updata1(p<<1,nl,nr,k);
    if(mid<nr) updata1(p<<1|1,nl,nr,k);
    push_up(p);
}
void updata2(int p,int nl,int nr,int k){
    if(nl<=tr[p].l&&tr[p].r<=nr){
        f2(p,k);
        return;
    }
    push_down(p);
    int mid=(tr[p].l+tr[p].r)>>1;
    if(nl<=mid) updata2(p<<1,nl,nr,k);
    if(mid<nr) updata2(p<<1|1,nl,nr,k);
    push_up(p);
}
int query(int p,int nl,int nr){
    if(nl<=tr[p].l&&tr[p].r<=nr){
        return tr[p].maxx;
    }
    push_down(p);
    int mid=(tr[p].l+tr[p].r)>>1;
    int res=-INF;
    if(nl<=mid) res=max(res,query(p<<1,nl,nr));
    if(mid<nr) res=max(res,query(p<<1|1,nl,nr));
    return res;
}
signed main(){
    n=read(),q=read();
    for(int i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    for(int i=1;i<=q;i++){
        int op=read(),x,y,z;
        if(op==1){
            x=read(),y=read(),z=read();
            updata2(1,x,y,z);
        }else if(op==2){
            x=read(),y=read(),z=read();
            updata1(1,x,y,z);
        }else{
            x=read(),y=read();
            printf("%lld\n",query(1,x,y));
        }
    }
    return 0;
}

同理，因为要进行区间加和区间修改两种操作，比较两种操作的优先级。我们在 f2 中直接对 lz1 进行了修改，所以在 push-down 中我们的 f2 应当在 f1 之前，不然相当于抹消了打在 f2 之后的区间加操作的贡献。因此应该先修改再加。

线段树变种

线段树区间开根

题目链接：上帝造题七分钟（线段树区间开根号）

题目要求

维护一个区间。给定以下两种操作：

给 [l,r] 上的每一个数开根。
求 [l,r] 上每个数的和。

开根我们用懒标记比较难维护，但我们发现即使 a_i\leq 10^{12}，开根开成 0 也看看只需要不到 10 次就可以变成 1。所以我们可以搜索到子节点，然后暴力开根。对于已经变成 1 的数，显然再进行多少次开根都是 1。所以我们用懒标记表示一个区间上的数是不是都变成 1 了即可 AC 本题。

AC代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int res=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        res=(res<<3)+(res<<1)+c-'0';
        c=getchar();
    }

    return res*f;
}
const int N=1e5+5;
int n,m,a[N];
struct NODE{
    int l,r,lz,sum;//lz表示区间里的所有数都被修改成1了 
}tr[N<<2];
void push_up(int p){
    tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
    tr[p].lz=tr[p<<1].lz && tr[p<<1|1].lz;
}
void build(int p,int l,int r){
    tr[p].l=l; tr[p].r=r;
    tr[p].lz=0;
    if(l==r){
        tr[p].sum=a[l];
        if(a[l]==1) tr[p].lz=1;
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    push_up(p);
} 
void f(int p){
    tr[p].sum=sqrt(tr[p].sum);
    if(tr[p].sum==1) tr[p].lz=1;
}
void updata(int p,int nl,int nr){
    if(tr[p].lz==1){
        return;
    }else if(tr[p].l==tr[p].r){
        f(p);
        return;
    }
    int mid=(tr[p].l+tr[p].r)>>1;
    if(nl<=mid) updata(p<<1,nl,nr);
    if(mid<nr) updata(p<<1|1,nl,nr);
    push_up(p);
}
int query(int p,int nl,int nr){
    if(nl<=tr[p].l&&tr[p].r<=nr){
        return tr[p].sum;
    }
    int mid=(tr[p].l+tr[p].r)>>1;
    int res=0;
    if(nl<=mid) res+=query(p<<1,nl,nr);
    if(mid<nr) res+=query(p<<1|1,nl,nr);
    return res; 
}
void test(int p){
    if(tr[p].l==tr[p].r){
        cout<<tr[p].l<<" "<<tr[p].sum<<endl;
        return;
    }
    int mid=(tr[p].l+tr[p].r)>>1;
    test(p<<1);
    test(p<<1|1);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    cin>>m;
    for(int i=1;i<=m;i++){
        int op,a,b;
        cin>>op>>a>>b;
        if(a>b) swap(a,b);
        if(op==0){
            updata(1,a,b);
        }else{
            cout<<query(1,a,b)<<endl;
        }
    }
    return 0;
}

非常规类 push_up

这类题难点就在线段树的 push_up 函数上——在有些区间问题中，一个区间的信息不能单纯通过四则运算维护，这时候需要更改 push_up，在合并的过程中维护信息。

T1

模板题题：hdu 1540。

题意描述：给一个 01 数组，求最长的一段连续 1 的个数。

区间问题，用线段树维护，每个区间节点维护三个信息：sum,pre,suf。sum 表示这个区间内的最长连续 1 个数；pre 记录这个区间内最长的前缀 1 长度；suf 记录最长的后缀 1。

在合并的时候，分类讨论一下左右儿子是不是满 1，然后对应去写就好了。

T2

传送门：P4198 楼房重建

维护的时候需要引入递归合并的办法，在合并的时候对子树进行 dfs 搜索信息。引流自己写的题解：P4198 楼房重建

T3

传送门：P4425

维护方式和上一题差不多，但需要多推一下性质和式子，所以黑。但不算难，可做。引流自己题解：P4425 转盘

权值线段树

线段树维护的是值域了，即维护一段值域内出现了哪些数。通常来说权值线段树都需要离散化后再处理。

T1

给一道比较难的例题，即需要具备灵活的思维进行推导，也需要对权值线段树和离散化有较好的掌握水平。

传送门：P9596 冒泡排序.

那道题我写了题解，这里把链接挂上，就不重新写一次题解了。解题报告：P9596 解题报告。

T2

水紫一道：P9176

引流大佬的博客，可以点个关注是吧 awa：巨佬の博客

可持久化线段树

传送门：模板

推荐一位很好的老师的讲解视频：bilibili 董晓算法

建立可持久化线段树，[l,r] 的第 k 大可以通过 r 区间减去 l-1 区间得到，类似于前缀和。

具体怎么写可持久化线段树？这和普通线段树有差别。

首先，它需要动态开点，所以需要用 ls,rs 记录左右儿子节点编号。sum 就记录至于内的数的个数。

struct NODE{
    int ls,rs,sum;
}tr[N*22];

然后建树部分，比较值得注意的是传引用。所以儿子更改到的标号会被传到这个节点上，方便记录（只有一个返回值其实写 int 函数也行）。

void build(int &x,int l,int r){//串引用 
    x=++idx;//开新的节点 
    if(l==r) return;//根节点 
    int mid=(l+r)>>1;
    build(ls(x),l,mid);
    build(rs(x),mid+1,r);
}

以及插入操作，每次插入就开一个新的版本在旧树上。具体过程是先开一个新节点，最开始继承上一个版本的对应节点 x。然后这一段值域内肯定数多了一个，sum++。继续二分缩小值域，在 v 对应的位置继续修改，另外一半边直接继承 x 的。

void insert(int x,int &y,int l,int r,int v){
    y=++idx;
    tr[y]=tr[x];//继承上一个版本的信息 
    tr[y].sum++;//增加一个值
    if(l==r) return;
    int mid=(l+r)>>1;
    if(v<=mid) insert(ls(x),ls(y),l,mid,v);//值域左半边 
    else insert(rs(x),rs(y),mid+1,r,v);//值域右半边 
}

可持久化线段树的查询搜索过程是同步搜索两个版本，也就是说同一次函数内两棵树的值域范围是相同的！不同的只是时间版本。对于一个区间，用类似于权值线段树求第 k 小的办法求就好。

int query(int x,int y,int l,int r,int k){
    if(l==r) return l;
    int mid=(l+r)>>1;
    int s=tr[ls(y)].sum-tr[ls(x)].sum;//这个区间内左半部分的数个数 
    if(k<=s) return query(ls(x),ls(y),l,mid,k);//k在左侧
    else return query(rs(x),rs(y),mid+1,r,k-s);//k在右侧 
}

主函数内，离散化一下，然后对于每个节点开一个新版本。这里我们还需要另外一个数组 rt，记录每个版本从哪个根开始搜。建树的时候就以 0 为根建树。

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[++btp]=a[i];
    }
    sort(b+1,b+1+btp);
    for(int i=1;i<=n;i++){//离散化 
        if(i==1||b[i-1]!=b[i]){
            c[++ctp]=b[i];
        }
    }
    build(rt[0],1,ctp);//建空树 
    for(int i=1;i<=n;i++){
        int x1=lower_bound(c+1,c+1+ctp,a[i])-c;
        insert(rt[i-1],rt[i],1,ctp,x1);//全局的x1位置插入一个数 
    }
    for(int i=1;i<=m;i++){
        int l,r,k;
        cin>>l>>r>>k;
        int id=query(rt[l-1],rt[r],1,ctp,k);
        cout<<c[id]<<'\n';
    } 
    return 0;
}

线段树合并

将两颗不同的线段树合并成为 1 棵线段树。董晓算法

模板传送门：线段树合并模板

在上文中的可持久化线段树中，我们采用了动态开点的线段树，这里的线段树合并也是对这样的两个树合并，这样的两棵树在逻辑上独立完整，但结构并不完整，且单独表示每种情况的信息。在合并之后我们会得到一颗表示两种情况之和的信息。

合并过程

我们还是类似于上面可持久化线段树的查询过程一样，同步在两棵树的对应节点上搜索。比如现在搜索到 x,y 两个节点，它们的区间范围应该是相同的（或者其中一个为空）。我们把 y 塞到 x 上。

分类讨论一下：

如果搜索到的这个范围，x 或 y 其中一个为空，那就不用再递归下去了，直接返回 x 编号即可。这个代码偷了个懒，刚好可以实现这个要求。如果 x,y 均为 0，它也能正确的返回 0，也就是空。
```
if(!x||!y) return x+y;//有一边为空，返回另外一个 
```
如果搜索到了叶子结点且均不为空，则把 y 的信息合并到 x 上，然后返回 x 的编号。
```
if(l==r){//合并叶子 
 tr[x].sum+=tr[y].sum;
 return x;
}
```
否则继续合并。把左右儿子都先合并起来，并记录节点编号。然后根据合并后的儿子信息，push_up。最后还是要返回 x 编号，以供父亲使用。
```
int mid=(l+r)>>1;
tr[x].ls=merge(tr[x].ls,tr[y].ls,l,mid);//合并左节点并记录 
tr[x].rs=merge(tr[x].rs,tr[y].rs,mid+1,r);//合并右节点并记录 
push_up(x);
return x;
```

对于这道题

我们每个节点都开一个权值线段树——当然不动态开点肯定是存不下的。然后我们利用差分的方式进行修改。因为线段树合并就是类似于两个区间的求和，所以差分依然可以作用在线段树合并上。

细节看代码，注意 rt 记录每个节点从哪个节点进入线段树森林。且其实每棵树都在逻辑上单独成立，且权值线段树值域都是 1-MAX_N。

#include<bits/stdc++.h>
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
using namespace std;
inline int read(){
    int res=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        res=(res<<3)+(res<<1)+c-'0';
        c=getchar();
    }
    return res*f;
}
const int N=1e5+5;
int n,m,tot;
int dep[N],fa[N],sz[N],top[N],son[N];
int rt[N];//记录每个节点从哪个点进入线段树 
int ans[N];
vector<int> e[N];
struct NODE{
    int ls,rs,sum,type;
}tr[N*50];
void dfs1(int u,int f){
    dep[u]=dep[f]+1;
    sz[u]=1;
    fa[u]=f;
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==f) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int t){
    top[u]=t;
    if(son[u]) dfs2(son[u],t);
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}
void push_up(int p){
    if(tr[ls(p)].sum>=tr[rs(p)].sum){//如果相等取更小的 
        tr[p].sum=tr[ls(p)].sum;
        tr[p].type=tr[ls(p)].type;
    }else{
        tr[p].sum=tr[rs(p)].sum;
        tr[p].type=tr[rs(p)].type;
    } 
}
int merge(int x,int y,int l,int r){
    if(!x||!y) return x+y;//有一边为空，返回另外一个 
    if(l==r){//合并叶子 
        tr[x].sum+=tr[y].sum;
        return x;
    }
    int mid=(l+r)>>1;
    tr[x].ls=merge(tr[x].ls,tr[y].ls,l,mid);//合并左节点并记录 
    tr[x].rs=merge(tr[x].rs,tr[y].rs,mid+1,r);//合并右节点并记录 
    push_up(x);
    return x;
}
void update(int &p,int l,int r,int x,int k){
    if(!p) p=++tot;//动态开新点
    if(l==r){
        tr[p].type=x;
        tr[p].sum+=k;
        return;
    } 
    int mid=(l+r)>>1;
    if(x<=mid) update(ls(p),l,mid,x,k);
    else update(rs(p),mid+1,r,x,k);
    push_up(p);
}
void count(int u,int f){//统计每个点的答案 
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==f) continue;
        count(v,u);
        rt[u]=merge(rt[u],rt[v],1,1e5);//合并子树 
    }
    ans[u]=tr[rt[u]].sum?tr[rt[u]].type:0;//记录答案 
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs1(1,0);
    dfs2(1,1);
    for(int i=1;i<=m;i++){
        int x,y,z,lca;
        cin>>x>>y>>z;
        lca=LCA(x,y);
        //差分 
        update(rt[x],1,1e5,z,1);//权值线段树，开到z上界 
        update(rt[y],1,1e5,z,1);
        update(rt[lca],1,1e5,z,-1);
        update(rt[fa[lca]],1,1e5,z,-1);
    }
    count(1,0);
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}