#include<bits/stdc++.h>
using namespace std;
#define task "task"
#define ii pair<int,int>
#define fi first
#define se second
//#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 30
#define iii pair<int,ii>
#define iiii pair<ii,ii>
//#define base 29
#define eps 1e-8
int dx[]= {0LL,0LL,1,-1,1,1,-1,-1};
int dy[]= {1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=4e5+1;
const int mod=1e9+7;
int goc,id[maxn],pos[maxn],timer,mn[maxn],P[maxn][lg2+1],n,q;
vector<int>a[maxn];
bool cmp(int x,int y)
{
return mn[x]<mn[y];
}
void dfs(int u)
{
mn[u]=u;
for(int v:a[u])
{
dfs(v);
P[v][0]=u;
mn[u]=min(mn[v],mn[u]);
}
sort(a[u].begin(),a[u].end(),cmp);
}
void gan(int u)
{
for(int v:a[u])
{
gan(v);
}
id[u]=++timer;
pos[timer]=u;
}
struct FEN
{
int n;
vector<int>bit;
FEN(){};
FEN(int _n):bit(n+1,0),n(_n+1)
{
};
int get(int r) {
int ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1)
ret += bit[r];
return ret;
}
int get(int l, int r) {
return get(r) - get(l - 1);
}
void update(int idx, int delta) {
for (; idx < n; idx = idx | (idx + 1))
bit[idx] += delta;
}
void updateRange(int l,int r,int val)
{
update(l,val);
update(r+1,-val);
}
}bit;
void init()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
int p;
cin>>p;
if(!p)goc=i;
else a[p].push_back(i);
}
dfs(goc);
gan(goc);
for(int j=1;j<=lg2;j++)
{
for(int i=1;i<=n;i++)
{
P[i][j]=P[P[i][j-1]][j-1];
}
}
bit=FEN(n+2);
for(int i=1;i<=n;i++)bit.update(i,-1);
while(q--)
{
int t;
cin>>t;
if(t==1)
{
int k;
cin>>k;
int ans=0;
for(int i=1;i<=k;i++)
{
int l=0,r=n;
while(l<=r)
{
int mid=(l+r)/2;
if(bit.get(mid)<0)
{
r=mid-1;
ans=mid;
}
else l=mid+1;
}
// cout<<ans<<" ";
bit.update(ans,1);
}
// cout<<ans<<'\n';
cout<<pos[ans]<<'\n';
}
else
{
int u;
cin>>u;
int ans=0;
for(int j=lg2;j>=0;j--)
{
if(P[u][j]&&bit.get(id[P[u][j]])==bit.get(id[P[u][j]]-1))
{
ans+=(1<<j);
u=P[u][j];
}
}
bit.update(id[u],-1);
cout<<ans<<'\n';
}
}
}
void process()
{
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
int t=1;
// cin>>t;
while(t--)
{
init();
process();
cout<<'\n';
}
cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
}
Compilation message (stderr)
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:153:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |