首页 > 试题广场 >

情人节的电灯泡

[编程题]情人节的电灯泡

热度指数：12 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

情人节到了，小芳和小明手牵手，打算过一个完美的情人节，但是小刚偏偏也来了，当了一个明晃晃的电灯泡，小明很尴尬，就和小刚说，我交给你个任务，你完成了我俩就带你玩，否则你就回家吧。小刚很有当单身狗的觉悟，他坚决不想让小明过好情人节，同为单身狗的你能帮帮他吗？现在有一个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

算法知识视频讲解

hrdate

发表于 2020-07-06 17:14:40

水题。 #pragma GCC optimize(2) #include <bits/stdc++.h> #define endl '\n' #define ll long long using namespace std; ll tree[1000050],a[1000050],n, 展开全文

威风镰鼬

发表于 2021-06-15 01:20:41

思路把n*n的矩阵摊平成一条直线，就可以用线段树的方法解决啦！n<1000，所以展成直线就是1e6的单点修改+区间求和。个人码风问题我全开ll了，第一发因为update写错了爆零（我太菜了）代码 #include<stdio.h> #include<iostream> 展开全文

Acapplella

发表于 2020-07-22 16:09:17

代码如下： #include <iostream> using namespace std; int n,m; int sum[1005][1005],vis[1005][1005]; int lowbit(int x) { return x & (-x); } void 展开全文

苟且的狮子

发表于 2020-07-24 16:15:30

树状数组题意：情人节到了，小芳和小明手牵手，打算过一个完美的情人节，但是小刚偏偏也来了，当了一个明晃晃的电灯泡，小明很尴尬，就和小刚说，我交给你个任务，你完成了我俩就带你玩，否则你就回家吧。小刚很有当单身狗的觉悟，他坚决不想让小明过好情人节，同为单身狗的你能帮帮他吗？现在有一个n×n（1 < 展开全文

sunrise__sunrise

发表于 2020-07-25 00:27:41

Solution #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/s 展开全文