C++ 解法, 执行用时: 1457ms, 内存消耗: 117988K, 提交时间: 2022-06-20 20:38:08

#pragma GCC optimize(3)
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 1100000
using namespace std;

int read()
{
    int ret=0;
    char ch=getchar();
    while(!(ch<='9'&&ch>='0'))ch=getchar();
    while(ch<='9'&&ch>='0')
    {
        ret=ret*10+ch-'0';
        ch=getchar();
    }
    return ret;
}

struct Intv{
    int l,r;
    int v;
    pair<int,int> dep;
}p[MAXN];

int n,m;
int a[MAXN];

inline void check_max(int &x,int y){if(x<y)x=y;}
inline void check_max(pair<int,int> &x,pair<int,int> y){if(x<y)x=y;}

struct FHQ_Treap{
    static const int Null=0;
    int num,root;
    struct node{
        int l,r,fa;
        int rnd,val,siz;
        node(){siz=0;}
    }tr[MAXN*3];
  
    void init(){num=0;root=Null;}//init!!
    void pushup(int x)
    {
        tr[x].siz=tr[tr[x].l].siz+tr[tr[x].r].siz+1;
      	//tr[tr[x].l].fa=tr[tr[x].r].fa=x; 维护fa
    }
    inline int rnd(){return (((rand()&0xffff)<<16)|(rand()&0xffff));}
    int add(int val)
    {
        num++;tr[num].l=tr[num].r=Null;tr[num].rnd=rnd();
      	tr[num].siz=1;tr[num].val=val;return num;
    }
    void split_val(int x,int k,int &l,int &r)
    {
        if(!x){l=r=Null;return;}
        if(tr[x].val<=k){l=x;split_val(tr[x].r,k,tr[x].r,r);}
        else{r=x;split_val(tr[x].l,k,l,tr[x].l);}
        pushup(x);
    }
  	void split_rank(int x,int k,int &l,int &r)
    {
        if(!x){l=r=Null;return;}
        if(tr[tr[x].l].siz+1<=k)
        {l=x;split_rank(tr[x].r,k-tr[tr[x].l].siz-1,tr[x].r,r);}
        else
        {r=x;split_rank(tr[x].l,k,l,tr[x].l);}
        pushup(x);
    }
    int merge(int x,int y)
    {
        if(!x||!y)return x|y;
        if(tr[x].rnd<tr[y].rnd){tr[x].r=merge(tr[x].r,y);pushup(x);return x;}
        else{tr[y].l=merge(x,tr[y].l);pushup(y);return y;}
    }
    int findkth(int x,int k)
    {
        while(1){
            if(tr[tr[x].l].siz>=k)x=tr[x].l;
            else if(tr[tr[x].l].siz+1==k)return x;
            else {k-=tr[tr[x].l].siz+1;x=tr[x].r;}
        }
    }
    int findrank(int val)
    {
        int tx,ty,ret;
        split_val(root,val-1,tx,ty);
        ret=tr[tx].siz+1;root=merge(tx,ty);
        return ret;
    }
  	int find_node_rank(int x)//注意这个需要维护fa
    {
        int ans=tr[tr[x].l].siz+1;
        while(x!=root)
        {
            int fa=tr[x].fa;
            if(x==tr[fa].r)ans+=tr[tr[fa].l].siz+1;
            x=fa;
        }
        return ans;
    }
    void insert(int val)
    {
        int  u = add(val);
        int l,r;
        split_val(root,val,l,r);
        root = merge(merge(l,u),r);
    }
    void get_subtree(int x,Intv &head,int &num,int siz)
    {
        if(x==Null)return;
        if(tr[x].l)get_subtree(tr[x].l,head,num,siz);
        
        int u=tr[x].val;
        num++;
        check_max(head.v,p[u].v);
        if(num!=siz)
            check_max(head.v,a[p[u].r]);
        else
            head.r = p[u].r;
        if(num==1)head.l = p[u].l;
        check_max(head.dep,make_pair(p[u].dep.first+1,p[u].dep.second));
        
        if(tr[x].r)get_subtree(tr[x].r,head,num,siz);
    }
    int Build(int L,int R)
    {
        if(L==R)
            return add(L);
        int mid=(L+R)/2;
        return merge(Build(L,mid),Build(mid+1,R));
    }
}treap;



struct BIT{
    pair<int,int> q[MAXN];
    BIT(){memset(q,0,sizeof(q));}

    void Max(int loc,pair<int,int> x)
    {
        for(int i=loc;i<MAXN;i+=i&-i)q[i]=max(q[i],x);
    }
    pair<int,int> Premax(int x)
    {
        pair<int,int> ret=make_pair(0,0);
        for(int i=x;i;i-=i&-i)ret=max(ret,q[i]);
        return ret;
    }
}bit;

int main()
{
    n=read();m=read();
    for(int i=1;i<n;i++)
    {
        a[i]=read();
    }

    treap.init();

    for(int i=1;i<=n;i++)
    {
        p[i].l=p[i].r=i;
        p[i].dep=make_pair(0,-i);
        p[i].v=0;
    }
    treap.root = treap.Build(1,n);

    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        op=read();
        //op=(treap.tr[treap.root].siz==1?2:1);
        if(op==1)
        {
            x=read();y=read();
            //int tmp = treap.tr[treap.root].siz;x=rand()%(tmp-1)+1;y=x+1;
            int l,mid,r;

            //int S = clock();
            treap.split_rank(treap.root,y,mid,r);
            treap.split_rank(mid,x-1,l,mid);
            //tp += clock()-S;
            
            int num=0;
            int u = treap.tr[mid].val;
            Intv nsh = p[u];
            treap.get_subtree(mid,nsh,num,treap.tr[mid].siz);
            p[u]=nsh;
            
            treap.tr[mid].l = treap.tr[mid].r=0;
            treap.tr[mid].siz = 1;

            //S = clock();
            treap.root =  treap.merge(treap.merge(l,mid),r);
            //tp += clock()-S;
            
            bit.Max(p[u].v+1,p[u].dep);
        }
        else
        {
            x=read();
            //x=rand()%n+1;
            int ans = bit.Premax(x).second;
            printf("%d\n",ans?-ans:1);
        }
    }

    return 0;
}