题目
题目描述
情人节到了,小芳和小明手牵手,打算过一个完美的情人节,但是小刚偏偏也来了,当了一个明晃晃的电灯泡,小明很尴尬,就和小刚说,我交给你个任务,你完成了我俩就带你玩,否则你就回家吧。小刚很有当单身狗的觉悟,他坚决不想让小明过好情人节,同为单身狗的你能帮帮他吗?现在有一个n×n(1 <= n <= 1000)的格子,每一个格子都有一个电灯泡,可能是亮的,也可能是灭的(1代表亮, 0代表灭),现在有两种操作,一种是给你一个坐标,对于那个坐标上的灯泡,如果他是亮的,那么熄灭他,反之如果他是灭的,那么打开它。第二种操作是给你两个坐标,第一个坐标代表一个子矩阵的左上角,另一个坐标是右下角,请你求出当前子矩阵中有多少个灯泡是亮着的。燥起来吧!!!单身狗们!!!!
输入描述
第一行两个整数,n(1 <= n <= 1000)和m(1 <= m <= 100000),分别代表正方形格子的边长和询问次数。
接下来n行,每一行有n个bool形数字(0或1),代表灯泡的状态。
接下来m行,每一行第一个数字f(1或2)代表操作的类型,如果f是1,那么接下来输入一个坐标(x, y)(1 <= x, y <= n),对于当前位置的灯泡状态进行改变,如果是2,那么接下来输入两个坐标(x1, y1)(1 <= x1, y1 <= n), (x2, y2)(1 <= x2, y2 <= n),确定子矩阵的位置,输出子矩阵中亮着的灯泡数量并换行。
输出描述
对于每一个2操作,输出子矩阵中亮着的灯泡数量并换行。
示例1
输入
6 4
0 0 1 0 1 0
1 0 1 1 0 1
1 0 0 0 0 0
1 1 0 0 1 0
0 0 0 0 1 1
0 0 0 0 1 0
2 2 2 4 5
1 1 1
2 1 1 6 6
1 2 6
输出
4
14
题解
方法一
知识点:线段树,枚举。
每行建立个线段树,维护单点异或修改、区间和查询即可。
这个能过纯属数据太烂。理论上可以采用树套树,不过太烦了,二维树状数组可以替代。
时间复杂度 \(O(mn \log n)\)
空间复杂度 \(O(n^2)\)
方法二
知识点:树状数组。
用二维树状数组维护子矩阵和即可,是板子题。
时间复杂度 \(O(m \log^2 n)\)
空间复杂度 \(O(n^2)\)
代码
方法一
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T, class F>
class SegmentTree {
int n;
vector<T> node;
void update(int rt, int l, int r, int x, F f) {
if (r < x || x < l) return;
if (l == r) return node[rt] = f(node[rt]), void();
int mid = l + r >> 1;
update(rt << 1, l, mid, x, f);
update(rt << 1 | 1, mid + 1, r, x, f);
node[rt] = node[rt << 1] + node[rt << 1 | 1];
}
T query(int rt, int l, int r, int x, int y) {
if (r < x || y < l) return T();
if (x <= l && r <= y) return node[rt];
int mid = l + r >> 1;
return query(rt << 1, l, mid, x, y) + query(rt << 1 | 1, mid + 1, r, x, y);
}
public:
SegmentTree(int _n = 0) { init(_n); }
SegmentTree(const vector<T> &src) { init(src); }
void init(int _n) {
n = _n;
node.assign(n << 2, T());
}
void init(const vector<T> &src) {
assert(src.size() >= 2);
init(src.size() - 1);
function<void(int, int, int)> build = [&](int rt, int l, int r) {
if (l == r) return node[rt] = src[l], void();
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
node[rt] = node[rt << 1] + node[rt << 1 | 1];
};
build(1, 1, n);
}
void update(int x, F f) { update(1, 1, n, x, f); }
T query(int x, int y) { return query(1, 1, n, x, y); }
};
struct T {
int sum = 0;
friend T operator+(const T &a, const T &b) { return { a.sum + b.sum }; }
};
struct F {
int vis;
T operator()(const T &x) { return { x.sum ^ vis }; }
};
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
vector<SegmentTree<T, F>> v(n + 1);
for (int i = 1;i <= n;i++) {
vector<T> src(n + 1);
for (int j = 1;j <= n;j++) {
int x;
cin >> x;
src[j] = { x };
}
v[i].init(src);
}
while (m--) {
int op;
cin >> op;
if (op == 1) {
int x, y;
cin >> x >> y;
v[x].update(y, { 1 });
}
else {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int ans = 0;
for (int i = x1;i <= x2;i++) ans += v[i].query(y1, y2).sum;
cout << ans << '\n';
}
}
return 0;
}
方法二
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T>
class Fenwick {
int n, m;
vector<vector<T>> node;
public:
Fenwick(int _n = 0, int _m = 0) { init(_n, _m); }
void init(int _n, int _m) {
n = _n;
m = _m;
node.assign(n + 1, vector<T>(m + 1, T()));
}
void update(int x, int y, T val) {
for (int i = x;i <= n;i += i & -i)
for (int j = y;j <= m;j += j & -j)
node[i][j] += val;
}
T query(int x, int y) {
T ans = T();
for (int i = x;i;i -= i & -i)
for (int j = y;j;j -= j & -j)
ans += node[i][j];
return ans;
}
T query(int x1, int y1, int x2, int y2) {
T ans = T();
ans += query(x2, y2);
ans -= query(x1 - 1, y2);
ans -= query(x2, y1 - 1);
ans += query(x1 - 1, y1 - 1);
return ans;
}
};
struct T {
int sum = 0;
T &operator+= (const T &x) { return sum += x.sum, *this; }
T &operator-= (const T &x) { return sum -= x.sum, *this; }
};
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> a(n + 1, vector<int>(n + 1));
Fenwick<T> fw(n, n);
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++) {
cin >> a[i][j];
if (a[i][j]) fw.update(i, j, { 1 });
}
}
while (m--) {
int op;
cin >> op;
if (op == 1) {
int x, y;
cin >> x >> y;
if (a[x][y]) fw.update(x, y, { -1 });
else fw.update(x, y, { 1 });
a[x][y] ^= 1;
}
else {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << fw.query(x1, y1, x2, y2).sum << '\n';
}
}
return 0;
}
标签:NC15172,rt,init,node,src,int,update,电灯泡,情人节
From: https://www.cnblogs.com/BlankYang/p/17369910.html