首页 > 其他分享 >NC15172 情人节的电灯泡

NC15172 情人节的电灯泡

时间:2023-05-03 23:33:28浏览次数:52  
标签:NC15172 rt init node src int update 电灯泡 情人节

题目链接

题目

题目描述

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

相关文章

  • pta情人节
    #include<bits/stdc++.h>usingnamespacestd;typedefstruct{stringname;}Name;intmain(){Namenum[1000];inti=0;while(1){ cin>>num[i].name; if(num[i].name!="."){ i++;}elsebreak;......
  • 牛客2023情人节比赛总结
    来水一篇...今天的比赛还是蛮简单的(虽然也没ak吧)主要有两个点要提醒一下自己,一个是组合公式\(k*C_n^{k}=n*C_{n-1}^{k-1}\),还有一个是一个并不难证明的结论:若\(\frac{a......
  • 2023.2.14 写于情人节的信竞反思(雾
    \(in\)\(the\)\(past:\)回想之前走了3年半的信竞之路,学了却感觉什么都没学一样。回忆起来都满是水分。作为一个自制力很差的人,很需要外界条件的约束(虽然我也知道不是......
  • 牛客情人节 (悸动的距离)
      点击查看代码 inta,b,c,d; cin>>a>>b>>c>>d; intans=0; if(a>=0&&c<=0||c>=0&&a<=0)ans++;//x轴交点 if(b>=0&&d<=0||b>=0&&d<=0)ans++;//y轴交点 if......
  • 码分享 | 情人节表白黑科技
    在去年年尾的时候,鼎道发布了《​​活动|编程式浪漫,让你的世界永远有烟花~​​​》,和大家分享了如何用技术代码实现烟花和鞭炮,也让大家了解到程序员专属的浪漫。情人节在即......
  • 装饰灯串情人节灯串上架亚马逊UL588报告流程?费用是多少?
    ​电子产品作为亚马逊平台上最受欢迎的类别之一,引起了许多卖家的关注。近日,有运营灯具品类的卖家表示,亚马逊向其要求提供相关证明,以证明部分灯具产品的安全性,否则该产品将无......
  • 情人节装饰品氛围灯串欧盟亚马逊CE认证
    灯串出口欧洲CE认证使用什么标准?灯串产品出口欧洲,CE认证是灯具进入欧盟市场的通行证,要做CE认证,EMC和LVD两个指令!灯串CE认证使用LVD(安规)标准为:欧洲EN60598-2-20:2015灯串的......
  • 情人节装饰品心形灯串上架美国亚马逊UL588流程
    2月14日,是西方传统的圣瓦伦丁节,又称“情人节”,它具有悠久的历史。古罗马时代的牧神节,就是一个情侣们的节日。是日男女青年欢聚一堂,姑娘们把表达爱情的祝词放在签筒里,小伙子......
  • 情人节浪漫3D照片墙【附源码】
    适合人群:初级学习者和爱好者,下面有展示图。计算机毕业设计文章目录​​1前言​​​​2正文​​​​2.1展示预览​​​​2.2项目结构​​​​2.2主要代码展示​​​​源......
  • 情人节:我又来了!
    以下是情书内容:以前,有很多新奇的想法,被别人无情的嘲笑,或被现实无情的摧残,但是我坚信,只要胸腔有热血,脚下还有路可走,就没有达不成的目标。感谢征文活动,给我这么好的机会,让我把......