题解：AT_abc477_d [ABC477D] Masking Tape

题意简述N 个格子初始颜色全是a。操作1 X格子 X 胶带状态切换 —— 有胶带就撕掉没胶带就贴上。操作2 C所有当前没有胶带的格子全部改成颜色c。有胶带的格子不受这次染色影响。我们维护 2 个数组lst[]时间戳记录这个格子最近一次撕掉胶带是第几号查询ok[]bool表示当前 x 格子有没有贴胶带。1表示贴了0表示没贴。再维护 1 个变量g保存最近一次 type2 的颜色。核心思路如果是 1 X翻转胶带情况 A本来没有胶带现在贴上胶带贴上胶带之后后面所有 type2 染色都碰不到这个格子。 那贴上去这一刻格子的颜色是什么 如果这个格子上次撕胶带的时间lst[x] ≤ 最近一次染色时间dq说明在贴胶带前它已经被全局染成g了。把这个颜色存到c[x]固定下来。ok[x]1标记贴上胶带。情况 B本来贴着现在撕掉撕掉之后这个格子会接收之后所有 type2 染色。 我们只要记下这次撕胶带发生在第i号查询。lst[x]i。ok[x]0标记被撕。如果是 2 C全局染色无胶带格子改成 C不用循环直接更新全局变量gCdqi把这次染色的查询号记下来。最后输出答案的时候对每个格子 i如果ok[i]true现在还贴着胶带。胶带挡住后面所有染色它的颜色就是当初贴胶带那一刻存下来的c[i]。如果ok[i]false现在没有胶带那要看【撕掉胶带的时间】和【最后一次全局染色时间】谁更晚就行了。完整代码#includebits/stdc.h #define fr1(i,a,b) for(int (i)(a);(i)(b);(i)) #define fr2(i,a,b) for(int (i)(a);(i)(b);--(i)) #define fr3(i,a,b,n) for(int (i)(a);(i)(b);(i)(n)) #define fr4(i,a,b,n) for(int (i)(a);(i)(b);(i)-(n)) #define fv(i,p) for(auto (i):(p)) #define written using #define ll long long #define ull unsigned ll #define pii pairint,int #define pll pairll,ll #define by namespace #define _1st first #define _2nd second #define qz5zwangzihan1 std #define y1 yy1 #define elif else if #define RT return #define debug coutendl-------------------------------------------------------------endl written by qz5zwangzihan1; const int MAXN300005; int n,q; bool ok[MAXN]; char c[MAXN]; int lst[MAXN]; char g; int dq; int main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cinnq; ga; fr1(i,1,n) lst[i]0; fr1(i,1,q){ int op; cinop; if(op1){ int x;cinx; if(!ok[x]){ ok[x]1; if(lst[x]dq){ c[x]g; } }else{ ok[x]0; lst[x]i; } }else{ char ccc; cinccc; gccc; dqi; } } string ans; fr1(i,1,n){ if(ok[i]){ ansc[i]; }else{ if(lst[i]dq){ ansg; }else{ ansc[i]; } } } coutans; RT 0; }