Fill-Rect QueryProblem Statement有一个H × W H \times WH×W的网格。初始时每个格子中都写有字母A。从顶部数第i ii行、从左数第j jj列的格子记为( i , j ) (i,j)(i,j)。我们将按顺序执行Q QQ次操作。在第i ii次操作中将以左上角( 1 , 1 ) (1,1)(1,1)、右下角( R i , C i ) (R_i,C_i)(Ri​,Ci​)为对角线的矩形内的所有格子覆盖为大写英文字母X i X_iXi​。请输出所有操作执行完毕后的网格。Constraints1 ≤ H , W 1 \le H,W1≤H,WH × W ≤ 10 6 H \times W \le 10 ^ 6H×W≤1061 ≤ Q ≤ 2 × 10 5 1 \le Q \le 2 \times 10^51≤Q≤2×1051 ≤ R i ≤ H 1 \le R_i \le H1≤Ri​≤H1 ≤ C i ≤ W 1 \le C_i \le W1≤Ci​≤WX i X_iXi​为大写英文字母。所有输入数字均为整数。Input输入从标准输入中给出格式如下H HHW WWQ QQR 1 R_1R1​C 1 C_1C1​X 1 X_1X1​R 2 R_2R2​C 2 C_2C2​X 2 X_2X2​⋮ \vdots⋮R Q R_QRQ​C Q C_QCQ​X Q X_QXQ​Output输出H HH行。第i ii行应包括一个长度为W WW的字符串其中第j jj个字符表示写在( i , j ) (i,j)(i,j)上的字母。Solution由于H × W ≤ 10 6 H \times W \le 10^6H×W≤106可以知道min ⁡ ( H , W ) ≤ 10 3 \min(H,W) \le 10^3min(H,W)≤103。又行与列没有本质差别不妨令H ≤ 10 3 H \le 10^3H≤103。将每次操作( R i , C i , X i ) (R_i,C_i,X_i)(Ri​,Ci​,Xi​)转化为第1 11到R i R_iRi​行上的操作( C i , X i ) (C_i,X_i)(Ci​,Xi​)即在格子1 11到C i C_iCi​写上X i X_iXi​。对于任意i j ijij满足C i ≥ C j C_i \ge C_jCi​≥Cj​第j jj次操作对于满足r ≤ R i r \le R_ir≤Ri​且r ≤ R j r \le R_jr≤Rj​的第r rr行是无效的。所以用H HH个二元组栈存储每行的有效操作加入操作时将栈顶C j ≥ C i C_j \ge C_iCj​≥Ci​的元素弹出在将( C i , X i ) (C_i,X_i)(Ci​,Xi​)入栈。最后将所有元素出栈并依次记录到答案中。对于每个操作最多会在每行中出入栈一次最后记录答案最多会写到H × W H \times WH×W个格子所以总时间复杂度约为O ( Q min ⁡ ( H , W ) ) O(Q \min(H,W))O(Qmin(H,W))最大为2 × 10 8 2 \times 10^82×108在AtCoder上2 22秒完全能跑完。Code#includebits/stdc.h#defineintlonglongusingnamespacestd;inth,w,q;boolflag;stackpairint,intqs[1005];intans[1000005];intf(intx,inty){return(x-1)*wy-1;}voidprint(intx,inty){coutchar(ans[f(x,y)]A);}signedmain(){flag0;cinhwq;if(hw){swap(h,w);flag1;}for(inti1;iq;i){intr,c,x;charch;cinrcch;xch-A;if(flag)swap(r,c);for(intj1;jr;j){while(!qs[j].empty()){if(qs[j].top().firstc)break;qs[j].pop();}qs[j].push({c,x});}}for(inti1;ih;i){intnow1;while(!qs[i].empty()){while(nowqs[i].top().first){ans[f(i,now)]qs[i].top().second;now;}qs[i].pop();}}if(flag){for(inti1;iw;i){for(intj1;jh;j){print(j,i);}cout\n;}}else{for(inti1;ih;i){for(intj1;jw;j){print(i,j);}cout\n;}}return0;}