#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
#define f first
#define s second
#define pb push_back
#define nl '\n'
#define sz(x) (int) x.size()
#define rep(i,a,b) for(int i=a; i<=b; i++)
const int N=200000;
const int B=400;
int r, c, q;
vector<vi> g;
int par[N];
int sz[N];
int col[N];
vi adj[N];
vi big;
map<int, set<int>> adj2[N];
int dx[]={-1, 0, 0, 1};
int dy[]={0, -1, 1, 0};
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
void join(int x, int y){
// cout << "join " << x << " " << y << nl;
int a=find(x);
int b=find(y);
if(a==b) return;
// cout << "ab " << a << " " << b << nl;
if(sz[b]>sz[a]) swap(a,b);
if(sz[a]>B && sz[b]>B){
for(auto e:adj2[b]){
for(int k:e.s) adj2[a][e.f].insert(k); // shouldn't need find(k)
}
}
else if(sz[a]>B && sz[b]<=B){
for(int k:adj[b]){
int c=col[find(k)];
if(k!=a && k!=b) adj2[a][c].insert(find(k));
}
}
else if(sz[a]+sz[b]<=B) {
for(int k:adj[b]) if(find(k)!=a && find(k)!=b) adj[a].pb(k);
}
if(sz[a]+sz[b]>B && sz[a]<=B){
big.pb(a);
for(int k:adj[a]) if(find(k)!=a && find(k)!=b) adj2[a][col[find(k)]].insert(find(k));
}
par[b]=a;
sz[a]+=sz[b];
}
int h(int i, int j){
return c*i+j;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> r >> c;
g.resize(r, vi(c));
rep(i,0,r-1){
rep(j,0,c-1){
par[h(i,j)]=h(i,j);
sz[h(i,j)]=1;
rep(k,0,1){
int x=i+dx[k];
int y=j+dy[k];
if(x<0 || y<0) continue;
adj[h(i,j)].pb(h(x,y));
adj[h(x,y)].pb(h(i,j));
}
}
}
rep(i,0,r-1){
rep(j,0,c-1){
cin >> g[i][j];
col[h(i,j)]=g[i][j];
rep(k,0,1){
int x=i+dx[k];
int y=j+dy[k];
if(x<0 || y<0) continue;
// cout << g[i][j] << "=" << g[x][y] << nl;
if(g[i][j]==g[x][y]) join(h(i,j), h(x,y));
}
}
}
cin >> q;
while(q--){
// cout << "Q " <<q << nl;
int x, y, c;
cin >> x >> y >> c;
x--; y--;
int i=find(h(x,y));
col[i]=c;
if(sz[i]>B){
vi nei;
for(int p:adj2[i][c]) nei.pb(p);
adj2[i][c].clear();
for(int k:nei) if(col[find(k)]==c) join(i, k);
}
else{
vi nei;
for(int p:adj[i]) nei.pb(p);
for(int k:nei){
if(col[find(k)]==c) join(i, k);
}
}
i=find(i);
if(sz[i]<=B){
for(int k:adj[i]){
if(sz[find(k)]>B && find(k)!=i) adj2[find(k)][c].insert(i);
}
}
else{
for(int j:big){
j=find(j);
if(j==i) continue;
if(adj2[i][col[j]].find(j)!=adj2[i][col[j]].end()) adj2[j][c].insert(i);
}
}
}
rep(i,0,r-1){
rep(j,0,c-1){
cout << col[find(h(i,j))] << " ";
}
cout << nl;
}
Compilation message
paint.cpp: In function 'int main()':
paint.cpp:155:2: error: expected '}' at end of input
155 | }
| ^
paint.cpp:73:11: note: to match this '{'
73 | int main(){
| ^
