rt，复杂度应该是 $\mathcal{O}(\sum k+(n+m)\log n)$ 的吧。但是 TLE 68pts。

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define uint unsigned int
#define pii pair<int,int>
#define io ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
inline int read(){
	int x=0;bool f=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')f=0;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return f?x:-x;
}
int t,op,x,y,n,m,a[300005],b[300005],st,ed,nxt[300005],lst[300005];
ll cnt[300005],q,val[300005],rcnt[300005];
set<pair<ll,int> > s;
vector<int> v;
bitset<300005> vis;
int main(){
	t=read(),n=read(),m=read();
	for(int i=1;i<=n;i++)
		a[i]=read(),b[i]=read(),cnt[b[i]]+=a[i];
	st=n+1,ed=0,nxt[st]=ed,lst[ed]=st,cnt[st]=1e18;
	s.insert({-cnt[st],-st}),s.insert({-cnt[ed],-ed});
	for(int i=1;i<=n;i++){
		auto it=s.lower_bound({-cnt[i],-i});
		lst[i]=lst[-(*it).second],nxt[i]=-(*it).second,lst[nxt[i]]=i,nxt[lst[i]]=i;
		s.insert({-cnt[i],-i});
	}
	v.reserve(300000);
	while(m--){
		op=read();
		if(op==1){
			x=read(),y=read(),a[x]+=y;
			lst[nxt[b[x]]]=lst[b[x]],nxt[lst[b[x]]]=nxt[b[x]];
			s.erase({-cnt[b[x]],-b[x]}),cnt[b[x]]+=y;int i=b[x];
			auto it=s.lower_bound({-cnt[i],-i});
			lst[i]=lst[-(*it).second],nxt[i]=-(*it).second,lst[nxt[i]]=i,nxt[lst[i]]=i;
			s.insert({-cnt[i],-i});
		}
		else{
			cin>>q;int it=nxt[st];v.clear();
			for(int i=1,lst=0;i<=n;lst=i,i=min(i<<1,n)){
				for(int j=n-lst;j>n-i;j--){
					cnt[b[j]]-=a[j];
					if(!vis[b[j]]) vis[b[j]]=1,v.push_back(b[j]);
					while(vis[it]) it=nxt[it];
				}
				int now=0;
				for(int x:v)
					if(cnt[x]>cnt[now]||(cnt[x]==cnt[now]&&x>now))
						now=x;
				if(cnt[it]>cnt[now]||(cnt[it]==cnt[now]&&it>now))
					now=it;
				for(int x:v)
					rcnt[x]=cnt[x];
				for(int j=n-i+1;j<=n-lst;j++){
					int p=b[j];
					cnt[p]+=a[j];
					if(cnt[p]>cnt[now]||(cnt[p]==cnt[now]&&p>now)) now=p;
					val[j]=1ll*now*a[j];
				}
				for(int x:v)
					cnt[x]=rcnt[x];
				int ans=0;
				for(int j=n-lst;j>n-i;j--){
					val[j]^=val[j+1];
					if(val[j]==q){
						ans=n-j+1;
						break;
					}
				}
				if(ans){
					printf("%d\n",ans);
					for(int j=n-i+1;j<=n;j++) vis[b[j]]=0,cnt[b[j]]+=a[j];
					break;
				}
			}
//			for(int i=1;i<=n;i++)
//				cout<<"cnt:"<<i<<' '<<cnt[i]<<'\n';
		}
	}
    return 0;
}