[ABC217D] Cutting Woods阉割版线段树原因及求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
char buf[1 << 20], *p1, *p2;
#define gc()                                                               \
  (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) \
       ? EOF                                                               \
       : *p1++)
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while (c<'0' || c>'9')
    {
        if (c=='-')  f=-1;
        c=getchar();
    }
    while (c>='0' && c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
inline void print(int x)
{
    if (x<0)
    {
        putchar('-');x=-x;
    }
    if (x>9) print(x/10);
    putchar(x%10+'0');
}
int l,q;
int rts;
struct node{
	int l,r,s,ls,rs;
}a[8888888];
int aa=1;
int find_rt(int root,int x)
{
	if(a[a[root].ls].r<x and a[a[root].ls].s)
	{
		return find_rt(a[root].rs,x);
	}
	else if(a[a[root].rs].l>x and a[a[root].rs].s)
	{
		return find_rt(a[root].ls,x);
	}
	else if(a[root].l<=x and a[root].r>=x)
	{
		return root;
	}
	return 0;
}
int find_ans(int root,int x)
{
	
	if(a[a[root].ls].r<x and a[a[root].ls].s)
	{
		return find_ans(a[root].rs,x);
	}
	else if(a[a[root].rs].l>x and a[a[root].rs].s)
	{
		return find_ans(a[root].ls,x);
	}
	else if(a[root].l<=x and a[root].r>=x)
	{
		return a[root].s;
	}
	return 0;
}
signed main()
{
	// cin>>l>>q;
	l=read();
	q=read();
	a[++rts]={1,l,l,0,0};
	for(int i=1,x,y;i<=q;i++)
	{
		// cin>>x>>y;
		x=read();
		y=read();
		if(x==1)
		{
			int rt=find_rt(1,y);
			a[++rts]={a[rt].l,y,y-a[rt].l+1};
			a[rt].ls=rts;
			a[++rts]={y+1,a[rt].r,a[rt].r-y};
			a[rt].rs=rts;
		}
		else
		{
			// cout<<find_ans(1,y)<<'\n';
			print(find_ans(1,y));
			puts("");
		}
	}
}