Yuuki and a problem

树状数组（线段树）套主席树，修改的部分会用到，算是积累一个带修主席树的板子

#include <bits/stdc++.h>
#define inf 0x7fffffff
#define ll long long
//#define int long long
//#define double long double
#define re register int
#define void inline void
#define eps 1e-5
//#define mod 1e9+7
//#define ls(p) p<<1
//#define rs(p) p<<1|1
//#define pi acos(-1.0)
#define pb push_back
#define P pair < int , int >
#define mk make_pair
#define fi first
#define se second
//#define unordered_map map
//#define __int128 long long
using namespace std;
const int mod=998244353;
const int N=2e5+5;
int rt[N<<7],n,q,a[N];
namespace HJT
{
	#define ls(p)  e[p].l
	#define rs(p)  e[p].r
	struct nod
	{
		int l,r;
		ll sum;
	}e[N<<7];
	int tot;
	void insert(int &p,int l,int r,int pos,ll val)
	{
		if(!p)  p=++tot;
		e[p].sum+=val;
		if(l==r)  return;
		int mid=(l+r)>>1;
		if(pos<=mid)  insert(ls(p),l,mid,pos,val);
		else insert(rs(p),mid+1,r,pos,val); 
	}
	ll ask(int p,int l,int r,int pos)
	{
		if(l==r)  return e[p].sum;
		int  mid=(l+r)>>1;
		if(pos<=mid)  return ask(ls(p),l,mid,pos);
		return ask(rs(p),mid+1,r,pos)+e[ls(p)].sum;
	}
	#undef ls
	#undef rs
}
namespace TREE
{
	int lowbit(int x){return x&(-x);}
	void update(int p,int pos,ll val)
	{
		for(re i=p;i<=N;i+=lowbit(i))  HJT::insert(rt[i],1,N,pos,val);
	}
	ll ask(int L,int R,int pos)
	{
		ll ans=0;
		for(re i=R;i;i-=lowbit(i))  ans+=HJT::ask(rt[i],1,N,pos);
		for(re i=L-1;i;i-=lowbit(i))  ans-=HJT::ask(rt[i],1,N,pos);
		return ans;
	}
}
void solve()
{
	cin>>n>>q;
	for(re i=1;i<=n;i++)  scanf("%d",&a[i]);
	for(re i=1;i<=n;i++)  TREE::update(i,a[i],a[i]);
	while(q--)
	{
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(op==1)
		{
			TREE::update(x,a[x],-a[x]);
			TREE::update(x,y,y);
			a[x]=y;
		}
		else
		{
			ll ans=0,la=0;
			while(1)
			{
				la=TREE::ask(x,y,min(ans+1,1ll*N));
				if(la==ans)  break;
				ans=la;
			}
			printf("%lld\n",ans+1);
		}
	}
}
signed main()
{
//	fflush(stdout);
//	srand(102321547);
//	freopen("Ain.txt", "r", stdin)
//	freopen("Aout.txt", "w", stdout);
//	freopen("9.out", "w", stdout);
    int T=1;
//    cin>>T;
    for(int index=1;index<=T;index++)
    {
//        printf("Case %d: ",index);
        solve();
//        puts("");
    }
    return 0;
}
/*
6 1
ABABBA
1 1 3 3 4
6 4



*/