二分+排序

https://codeforces.com/contest/2053/problem/D
https://blog.csdn.net/weixin_61825750/article/details/144799098

#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#define INF 2e9
using namespace std;

#define endl '\n'
using ll = long long;
using pii = pair<ll, ll>;
const double PI = acos(-1);
const int N = 1e3+ 10;
const int mod = 998244353;
ll qmi(int a,int p){
	ll sum=1;
	ll aa=a;
	while(p){
		if(p&1){
			sum=(sum*aa)%mod;
		}
		p>>=1;
		aa=(aa*aa)%mod;
	}
	return sum;
}
void solve(){

	int n,q;cin>>n>>q;
	vector<int> a(n),b(n);
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++)
		cin>>b[i];
	vector<int> c(a.begin(),a.end()),d(b.begin(),b.end());
	sort(c.begin(),c.end());
	sort(d.begin(),d.end());
	ll ans=1;
	for(int i=0;i<n;i++){
		ans=(ans*min(c[i],d[i]))%mod;
	}
	cout<<ans<<" ";
	while(q--){
		int o,x;cin>>o>>x;
		if(o==1){
			int now=a[x-1];
			a[x-1]++;
			int l=0,r=n-1;
			while(l<r){
				int mid=(l+r+1)>>1;
				if(c[mid]<=now) l=mid;
				else r=mid-1;
			}
			c[l]++;
			if(c[l]-1<d[l]){
				ans=(ans*qmi(c[l]-1,mod-2))%mod;
				ans=(ans*c[l])%mod;
			}
		}
		else{
			int now=b[x-1];
			b[x-1]++;//原数组同步更新
				int l=0,r=n-1;
				while(l<r){
					int mid=(l+r+1)>>1;
					if(d[mid]<=now) l=mid;
					else r=mid-1;
				}
				d[l]++;
				if(d[l]-1<c[l]){
					ans=(ans*qmi(d[l]-1,mod-2))%mod;
					ans=(ans*d[l])%mod;
				}
		}
		cout<<ans<<" ";
	}
	cout<<endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int T = 1;
	cin>>T;
	while (T--) {
		solve();
	}
	
	return 0;
}