题解 | #小红的数组操作#不会线段树只能分块了

• MI[i]预处理块i的最小值，最小值用multiset维护，复杂度q*n^(1/2)

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=1e5+9;
const int inf=21e8;
int n,q,group[N],L[N],R[N],cnt,MI[N],id;
multiset<int>s[N];

void init()
{
	cnt=sqrt(n)+1;
	for(int i=1;i<=n;i++)MI[i]=inf;
	for(int i=1;i<=n;i++)
	{
		L[++id]=i;
		R[id]=min(n,i+cnt);
		for(int j=L[id];j<=R[id];j++)
		{
			group[j]=id;
			MI[id]=min(MI[id],*s[j].begin());
		}
		i=R[id];
	}
}

void change(auto &a,int x,int y,int t)
{
	int res=a[x][y];
	auto it=s[x].begin();
	int fr=*it,sc=*(++it);
	
	s[x].erase(s[x].find(a[x][y]));
	a[x][y]=t;
	s[x].insert(t);
	
	int p=0;
	for(int i=L[group[x]];i<=R[group[x]];i++)
	{
		if(p>=2)break;
		it=s[i].begin();
		if(*it==MI[group[x]])p++;
		if(*++it==MI[group[x]])p++;
	}
	
	if(p>=2)
	for(int i=L[group[x]];i<=R[group[x]];i++)
	MI[group[x]]=min(MI[group[x]],*s[i].begin());
	else
	{
		MI[group[x]]=inf;
		for(int i=L[group[x]];i<=R[group[x]];i++)
		MI[group[x]]=min(MI[group[x]],*s[i].begin());
	}
}

int MIN(auto &a,int en)
{
	int res=inf,l=L[group[en]],r=en,lagroup=group[en]-1;
	for(int i=1;i<=lagroup;i++)res=min(res,MI[i]);
	for(int i=l;i<=r;i++)res=min(res,*s[i].begin());
	return res;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    vector<vector<int>>a(n+1,vector<int>(1));
    for(int i=1;i<=n;i++)
    {
    	int m;cin>>m;
    	a[i].resize(m+1);
    	for(int j=1;j<=m;j++)cin>>a[i][j],s[i].insert(a[i][j]);
	}
	
	cin>>q;
	init();
	//cout<<cnt<<' '<<id<<'\n';
	//for(int i=1;i<=n;i++)cout<<group[i]<<' ';cout<<'\n';
	
	
	while(q--)
	{
		int t;cin>>t;
		if(t==1)
		{
			int i,j,x;cin>>i>>j>>x;
			change(a,i,j,x);
			//cout<<'\n';
			//for(int i=1;i<=id;i++)cout<<MI[i]<<' ';
			//cout<<'\n';
		}else
		{
			int r;cin>>r;
			cout<<MIN(a,r)<<'\n';
		}
	}
	
    return 0;
}
/*
4
3 2 2 3
3 4 5 6
4 7 8 9 10
2 1 2
5
2 2
1 1 1 10
2 3
1 1 2 11
2 2
*/