#include #include using namespace std; struct Query{ int r; int c; int x; }; class Island; int h, w; int **a; Island*** islands; class Island{ private: Island* parent; void init(int y, int x){ if(y<0 || x < 0 || y >= h || x >= w) return; if(islands[y][x] == this) return; if(a[y][x] != color) { if(islands[y][x] != NULL){ setJoinedIsland(islands[y][x]); } return; } islands[y][x] = this; init(y-1,x); init(y,x-1); init(y+1,x); init(y,x+1); } public: vector childs; vector joined_islands; int id; int color; Island(int y,int x,int id){ this->id = id; parent = NULL; color = a[y][x]; init(y,x); } void setJoinedIsland(Island* island){ for(int i=0; isetJoinedIsland(this); } void setParent(Island *p){ getParent()->parent = p; parent = p; } Island* getParent(){ if(parent == NULL) return this; return parent = parent->getParent(); } int getColor(){ return getParent()->color; } void reverseColor(){ if(parent!=NULL) { getParent()->reverseColor(); return; } color = (color+1)%2; merge(); } void merge(){ if(joined_islands.size()>0){ Island* p = getParent(); for(int i=0;igetParent(); if(target == p) continue; bool flg = true; for(int ii=0;iichilds.size();ii++){ if(p->childs[ii] == target) flg = false; } if(flg) { p->childs.push_back(target); target->setParent(p); } } joined_islands.clear(); } else{ vector tmp = childs; childs.clear(); for(int i=0;imerge(); } } } }; int main(){ ios::sync_with_stdio(false); cin >> h >> w; a = new int*[h]; islands = new Island**[h]; for(int i=0;i> a[i][ii]; islands[i][ii] = NULL; } } int q; cin >> q; Query* qa = new Query[q]; for(int i=0; i> qa[i].r >> qa[i].c >> qa[i].x; qa[i].r -= 1; qa[i].c -= 1; } //cout << "all query loaded." << endl; int c=0; for(int i=0;igetColor() == query.x) continue; // same color islands[query.r][query.c]->reverseColor(); } //cout << "all query completed." << endl; for(int i=0;igetColor() << " "; } cout << endl; } //cout << "solved." << endl; }