F - Simplified Reversi 矩阵侧边视角 修改
1 行修改的时候只🔥影响的是哪些位置 因为Queries are pairwise distinct.
也就是当前行修改过之后 当前行就不会重复修改。额。实际上如果没有这个条件也无所谓的 我们可以用一个vis来判重就行
2 用什么东西可以维护这样的区间修改
主要还是行列间的 查询和修改的互动。。还挺有意思
…
void solve() {
cin >> n >> m;
f.build(1, 1, n - 1, n - 1); //（root,l,r,val) //我们这边用n-1 。。到时候-1 。。这样会更舒服一点。
g.build(1, 1, n - 1, n - 1);
int ans = (n - 2) * (n - 2);
while (m--) {
int o, i;
cin >> o >> i;
if (o == 1) {
int t = g.query(1, i, i);// (root,l,r)我们要找到当前列。他能到的底部位置
ans -= t - 1;
f.update(1, 1, t, i - 1);//(root,l,r,val)列的底部位置 就是行 [1,t]需要更新能到的最远距离i
} else {
int t = f.query(1, i, i);//(root,l,r)上下相反就行了。。
ans -= t - 1;
g.update(1, 1, t, i - 1);
}
}
cout << ans << '\n';
};
这代码省略了。。线段树主模版。。对线段树熟悉的。一般能看的懂。