维护前缀众数，考虑分块。维护前 \(i\) 个块中每种数的出现次数与众数，单点加只会影响后面的块，\(O(\sqrt n)\)。看到这个 \(k\) 的范围基本就确定是直接从后向前找，从后往前枚举块，有了出现次数前缀和容易通过扫一遍块得到其中所有位置的权值，最坏应该是 \(O(m\sqrt n+\sum k)\)。
但是因为需要维护前缀和数组，是 \(O(n\sqrt n)\) 的。为了空间只能牺牲时间，大抵是卡不过去的。
因为 \(k\) 是从后向前扫的，也不用考虑散块修改。考虑倍增分块，从后向前 \(1,2,4,8,\cdots\) 分一块。则修改只有 \(\log n\) 个块，前缀和数组大小也是 \(O(n\log n)\) 的。找 \(k\) 时最多枚举两倍的位置，总复杂度 \(O(m\log n+\sum k)\)。
Takanashi Rikka
// Problem: P11398 众数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11398
// Memory Limit: 512 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
#define fin(x) freopen(#x".in","r",stdin)
#define fout(x) freopen(#x".out","w",stdout)
#define fr(x) fin(x),fout(x);
#define Fr(x,y) fin(x),fout(y)
#define INPUT(_1,_2,FILE,...) FILE
#define IO(...) INPUT(__VA_ARGS__,Fr,fr)(__VA_ARGS__)
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define intz(x,z) memset((x),(z),sizeof((x)))
#define cfast ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
inline ll lowbit(ll x){return x&-x;}
#define fi first
#define se second
inline void cmx(auto &x,ll y){if(y>x)x=y;}
inline void cmn(auto &x,ll y){if(y<x)x=y;}
const int N=3e5+5,B=55;
int b[N],bl[N],p[B],L[N],R[N];ll val[N],a[N],sum[B][N],c[N];
void UesugiErii(){int id,n,m;cin>>id>>n>>m;for(int i=1;i<=n;i++)cin>>a[i]>>b[i];int tot=1;for(int i=n,tmp=1;i>0;i--){for(int j=i;j>max(0,i-tmp);j--)bl[j]=tot;i-=tmp-1,tmp*=2,++tot;}for(int i=1;i<=n;i++){R[bl[i]=tot-bl[i]+1]=i;if(!L[bl[i]])L[bl[i]]=i;}for(int i=1;i<=bl[n];i++){for(int j=1;j<=n;j++)sum[i][j]+=sum[i-1][j];for(int j=L[i];j<=R[i];j++)sum[i][b[j]]+=a[j];int mx=0;for(int j=1;j<=n;j++)if(sum[i][j]>=mx)mx=sum[i][j],p[i]=j;}while(m--){int op;ll x,y;cin>>op>>x;if(op==1){cin>>y,a[x]+=y;for(int j=bl[x];j<=bl[n];j++){sum[j][b[x]]+=y;if((sum[j][b[x]]>sum[j][p[j]])||(sum[j][b[x]]==sum[j][p[j]]&&b[x]>=p[j]))p[j]=b[x];}}else{ll v=0;bool flag=0;for(int i=bl[n];i&&!flag;i--){int P=p[i-1];for(int j=L[i];j<=R[i];j++){c[b[j]]+=a[j];if((sum[i-1][b[j]]+c[b[j]]>sum[i-1][P]+c[P])||(sum[i-1][b[j]]+c[b[j]]==sum[i-1][P]+c[P]&&b[j]>=P))P=b[j];val[j]=1ll*P*a[j];}for(int j=R[i];j>=L[i];j--)if((v^=val[j])==x){cout<<n-j+1<<'\n';flag=1;break;}for(int j=L[i];j<=R[i];j++)c[b[j]]=0;}}}
}
signed main(){cfast;int _=1;//cin>>_;for(;_;_--)UesugiErii();return 0;
}