前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >信息学做题日记:耗时4天,终于AC掉一道题

信息学做题日记:耗时4天,终于AC掉一道题

作者头像
小码匠
发布2024-06-11 17:56:20
850
发布2024-06-11 17:56:20
举报
文章被收录于专栏:小码匠和老码农

大家好!我是老码农。

今天备受折磨的小码匠,终于在早晨AC掉了一道线段树题。

话说这道题,从周三晚上开始,代码写了7、8成;

然后周四继续调试,无果,0分,只过了Subtask #1这个点;

然后周五继续发力,继续无果,依然是0分,依然是只过了Subtask #1这个点;

今天早晨小码匠不甘心,写了会作业,继续搞这道题,终于在11点29分AC掉了这道题;

这道题也是最近做的比较吃力的一道题;

耗时:周三1.5小时+周四1.5小时+周五1.5小时+周六1.5小时 = 6小时啊。

做完题后跟小码匠交流,感觉收获还是很多,对线段树理解比之前上了一个小层次。

这道题也是最近写的代码最长的,后面虐心的题目会越来越多。

爽歪歪的题目实则对自己帮助不是很大。

贴上代码,留个纪念。

代码语言:javascript
复制
#include <bits/stdc++.h>

using namespace std;

constexpr int MAX_NUM = 1e5 + 5;

struct line {
    int l, r, len, sum, max_zero, max_one, left_zero, right_zero, left_one, right_one;
    int lazy, add;
} t[8 * MAX_NUM];

int a[MAX_NUM];

void push_up(int u) {
    auto &root = t[u];
    auto &left = t[u << 1];
    auto &right = t[u << 1 | 1];
    if (left.left_zero == left.len) {
        root.left_zero = left.left_zero + right.left_zero;
    } else {
        root.left_zero = left.left_zero;
    }
    if (left.left_one == left.len) {
        root.left_one = left.left_one + right.left_one;
    } else {
        root.left_one = left.left_one;
    }
    if (right.right_zero == right.len) {
        root.right_zero = right.right_zero + left.right_zero;
    } else {
        root.right_zero = right.right_zero;
    }
    if (right.right_one == right.len) {
        root.right_one = right.right_one + left.right_one;
    } else {
        root.right_one = right.right_one;
    }
    root.max_zero = max({left.max_zero, right.max_zero,
                         left.right_zero + right.left_zero});
    root.max_one = max({left.max_one, right.max_one,
                        left.right_one + right.left_one});
    root.sum = left.sum + right.sum;
}

void build(int u, int l, int r) {
    t[u].l = l;
    t[u].r = r;
    t[u].len = r - l + 1;
    t[u].lazy = -1;
    if (l == r) {
        t[u].left_zero = 1 - a[l];
        t[u].left_one = a[l];
        t[u].right_zero = 1 - a[l];
        t[u].right_one = a[l];
        t[u].max_zero = 1 - a[l];
        t[u].max_one = a[l];
        t[u].sum = a[l];
        return;
    }  else {
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid +1 , r);
        push_up(u);
    }
}

void change(line &x,  bool flag) {
    x.sum = 0;
    x.left_one = 0;
    x.right_one = 0;
    x.left_zero = x.len;
    x.right_zero = x.len;
    x.max_zero = x.len;
    x.max_one = 0;
    if(flag) {
        swap(x.left_one, x.left_zero);
        swap(x.right_one, x.right_zero);
        swap(x.max_one, x.max_zero);
        x.sum = x.len;
    }
}

void change2(line &x) {
    swap(x.left_one, x.left_zero);
    swap(x.right_one, x.right_zero);
    swap(x.max_one, x.max_zero);
    x.sum = x.len - x.sum;
}

void push_down(int u) {
    auto &root = t[u];
    auto &left = t[u << 1];
    auto &right = t[u << 1 | 1];
    if (root.lazy == 0) {
        change(left,  false);
        change(right, false);
    } else if (root.lazy == 1) {
        change(left, true);
        change(right, true);
    }
    if (root.lazy != -1) {
        root.add = 0;
        left.lazy = root.lazy;
        right.lazy = root.lazy;
        left.add = 0;
        right.add = 0;
    }
    if (root.add == 1) {
        root.add = 0;
        if (left.lazy != -1) {
            left.lazy ^= 1;
        } else {
            left.add ^= 1;
        }
        if (right.lazy != -1) {
            right.lazy ^= 1;
        } else {
            right.add ^= 1;
        }
        change2(left);
        change2(right);
    }
    root.lazy = -1;
}

void modify(int u, int l, int r, int opt) {
    push_down(u);
    if (t[u].l >= l && t[u].r <= r) {
        if (opt == 1) {
            change(t[u],  false);
            t[u].lazy = 0;
        } else if (opt == 2) {
            change(t[u],  true);
            t[u].lazy = 1;
        } else if(opt == 3) {
            change2(t[u]);
            t[u].add ^= 1;
        }
        return;
    } else {
        int mid = (t[u].l + t[u].r) >> 1;
        if (l <= mid) {
            modify(u << 1, l, r, opt);
        }
        if (r > mid) {
            modify(u << 1 | 1, l, r, opt);
        }
        push_up(u);
    }
}

int query(int u, int l, int r) {
    if (t[u].l >= l && t[u].r <= r) {
        return t[u].sum;
    }

    push_down(u);

    int mid = (t[u].l + t[u].r) >> 1;
    int s = 0;
    if (l <= mid) {
        s = query(u << 1, l, r);
    }
    if (r > mid) {
        s += query(u << 1 | 1, l, r);
    }
    return s;
}
//line p, q, ans;

line cnt(int u, int l, int r) {

    if (t[u].l >= l && t[u].r <= r) {
        return t[u];
    } else {
        push_down(u);
        int mid = (t[u].l + t[u].r) >> 1;
        line p = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        line q = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        line ans = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
        if (l <= mid) {
            p = cnt(u << 1, l, r);
            ans.max_one = p.max_one;
        }
        if (r > mid) {
            q = cnt(u << 1 | 1, l, r);
            ans.max_one = max(ans.max_one, q.max_one);
        }
        ans.max_one = max(p.right_one + q.left_one, ans.max_one);
        if (p.left_one == p.len) {
            ans.left_one = p.left_one + q.left_one;
        } else {
            ans.left_one = p.left_one;
        }
        if (q.right_one == q.len) {
            ans.right_one = p.right_one + q.right_one;
        } else {
            ans.right_one = q.right_one;
        }
        return ans;
    }
}

void best_coder() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build(1,1,n);
    for (int i = 0; i < m; ++i) {
        int opt, l, r;
        cin >> opt >> l >> r;
        ++opt;
        ++l;
        ++r;
        if(opt <= 3){
            modify(1, l, r, opt);
        } else if (opt == 4) {
            cout << query(1, l, r) << '\n';
        } else {
            cout << cnt(1, l, r).max_one << '\n';
        }
    }
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}

总结

记得「关注」、点「」、点「在看」支持一下老码农,感谢大家的支持!

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2024-06-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 小码匠和老码农 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档