西安网站建设qq群号,濮阳市住房和城乡建设局网站,python做网站表白,东莞 营销网站建设登录—专业IT笔试面试备考平台_牛客网
题意 思路
首先#xff0c;一个必要步骤是把它转化为两个序列#xff0c;这样就变成了一个序列DS问题
我们的答案是一个位置 pos 后面还有多少位置和这个位置的颜色相同#xff0c;考虑得到这个答案我们需要维护什么东西
我们只需要…登录—专业IT笔试面试备考平台_牛客网
题意 思路
首先一个必要步骤是把它转化为两个序列这样就变成了一个序列DS问题
我们的答案是一个位置 pos 后面还有多少位置和这个位置的颜色相同考虑得到这个答案我们需要维护什么东西
我们只需要维护颜色之间的边界的位置即可
用 set 维护位置剩下就是常规的增删改查了
#include bits/stdc.h#define int long longconstexpr int N 5e2 10;
constexpr int M 1e4 10;
constexpr int mod 998244353;
constexpr int Inf 0x3f3f3f3f;std::setint sa, sb;int n, m;int a(int i, int j) {if (i 1) {return (i - 1) * m j;}else {return i * m - (j - 1);}
}
int b(int i, int j) {if (j 1) {return (j - 1) * n i;}else {return j * n - (i - 1);}
}
void upd(std::setint S, std::vectorchar V, int i, char x) {S.erase(i);S.erase(i 1);V[i] x;if (V[i] ! V[i - 1]) {S.insert(i);}if (V[i] ! V[i 1]) {S.insert(i 1);}
}
void solve() {std::cin n m;std::vectorchar va(n * m 2), vb(n * m 2);for (int i 1; i n; i ) {for (int j 1; j m; j ) {char x;std::cin x;upd(sa, va, a(i, j), x);upd(sb, vb, b(i, j), x);}}int q;std::cin q;while(q --) {int op, x, y;char c;std::cin op;if (op 1) {std::cin x y c;upd(sa, va, a(x, y), c);upd(sb, vb, b(x, y), c);}else if (op 2) {std::cin x y;std::cout (*sa.upper_bound(a(x, y))) - a(x, y) \n;}else {std::cin x y;std::cout (*sb.upper_bound(b(x, y))) - b(x, y) \n;}}
}
signed main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t 1;while(t --) {solve();}return 0;
}
