#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include//assert(); //#include //xAOJ ///////// #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define P(p) cout<<(p)< ///////// typedef long long LL; typedef long double LD; typedef unsigned long long ULL; ///////// using namespace::std; ///////// ///////// class UnionFind{ public: int cNum;//要素数 int cSize;// vector parent; vector rank; vector color; vector< vector< int > > tonari; UnionFind(int n){ cNum = n; cSize = n; parent = vector(n); rank = vector(n,0); color = vector(n); tonari = vector< vector >(n); for(int i=0;i temp; vector::iterator it,endit; it = tonari[x].begin(); endit = tonari[x].end(); for(;it != endit;++it){ if( !same(y,*it) ){ temp.push_back(*it); } } tonari[x].clear(); it = tonari[y].begin(); endit = tonari[y].end(); for(;it != endit;++it){ if( !same(y,*it) ){ temp.push_back(*it); } } sort( temp.begin(), temp.end() ); temp.erase( unique( temp.begin(), temp.end() ), temp.end() ); tonari[y].swap( temp ); } void tonariAdd(int atti,int kotti){ tonari[ find(atti) ].push_back(kotti); tonari[ find(kotti) ].push_back(atti); } }; void solve(){ int H,W; cin >> H >> W; UnionFind UF(H*W); int incolor; for(int h=0;h> incolor; if( incolor == 1 ){ UF.color[h*W + w] = true; }else{ UF.color[h*W + w] = false; } } } //////////////// if( 1 0 ){ if( UF.color[h*W+w] == UF.color[(h-1)*W + w] ){ UF.add(h*W+w,(h-1)*W+w ); }else{ UF.tonariAdd(h*W+w,(h-1)*W+w); } } if( w> 0 ){ if( UF.color[h*W+w] == UF.color[h*W+(w-1)] ){ UF.add( h*W+w,h*W+(w-1) ); }else{ UF.tonariAdd(h*W+w,h*W+(w-1) ); } } } } //////////////// int Q; cin >> Q; int R,C,Xnum; bool X; vector::iterator it,endit; int ter; vector tempVec; while(Q--){ cin >> R >> C >> Xnum; --R;--C; if( Xnum == 1 ){ X = true; }else{ X = false; } ter = UF.find(R*W+C); if( UF.color[ ter ] == X ) continue; UF.color[ter] = X; if( UF.cSize == 1 ){ continue;} tempVec.clear(); tempVec.swap( UF.tonari[ ter ] ); it = tempVec.begin(); endit = tempVec.end(); for(;it != endit;++it){ UF.add( ter, *it); } } for(int h=0;h