可爱线段树只过 hack 0pts 求调

xudongyi1 @ 2024-07-18 19:13:23

by xudongyi1 @ 2024-07-18 19:13:45

#include <iostream>
#include <stack>
#include <cmath>
#include <vector>
#include <map>
#include <string.h>
#include <queue>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
struct node
{
    int l, r, len;
    int lz, co;
    int num[3];// 数字数量 
    int ml[3];// 左边最长 
    int mr[3];// 右边最长 
    int mx[3];// 最大字段和 
}tr[N << 2];
int a[N];
void push_up(int u)
{
    for(int i = 0; i <= 1; i++)
    {
        tr[u].num[i] = tr[u << 1].num[i] + tr[u << 1 | 1].num[i];

        tr[u].ml[i] = tr[u << 1].ml[i];
        if(tr[u << 1].ml[i] == tr[u << 1].len) tr[u].ml[i] = tr[u << 1].len + tr[u << 1 | 1].ml[i];

        tr[u].mr[i] = tr[u << 1 | 1].mr[i];
        if(tr[u << 1 | 1].mr[i] == tr[u << 1 | 1].len) tr[u].mr[i] = tr[u << 1 | 1].len + tr[u << 1].mr[i];

        tr[u].mx[i] = max(tr[u << 1].mr[i] + tr[u << 1 | 1].ml[i], max(tr[u << 1].mx[i], tr[u << 1 | 1].mx[i]));
    }
}
void colour(int u)
{
    int co = tr[u].co;
    tr[u << 1].co = tr[u << 1 | 1].co = co;

    tr[u << 1].num[!co] = tr[u << 1 | 1].num[!co] = 0;
    tr[u << 1].ml[!co] = tr[u << 1 | 1].ml[!co] = 0;
    tr[u << 1].mr[!co] = tr[u << 1 | 1].mr[!co] = 0;
    tr[u << 1].mx[!co] = tr[u << 1 | 1].mx[!co] = 0;

    tr[u << 1].num[co] = tr[u << 1].ml[co] = tr[u << 1].mr[co] = tr[u << 1].mx[co] = tr[u << 1].len;
    tr[u << 1 | 1].num[co] = tr[u << 1 | 1].ml[co] = tr[u << 1 | 1].mr[co] = tr[u << 1 | 1].mx[co] = tr[u << 1 | 1].len;

    tr[u].co = -1;
}
void reverse(int u)
{
    tr[u << 1].lz = tr[u << 1 | 1].lz = tr[u].lz;

    swap(tr[u << 1].num[0], tr[u << 1].num[1]);
    swap(tr[u << 1].ml[0], tr[u << 1].ml[1]);
    swap(tr[u << 1].mr[0], tr[u << 1].mr[1]);
    swap(tr[u << 1].mx[0], tr[u << 1].mx[1]);

    swap(tr[u << 1 | 1].num[0], tr[u << 1 | 1].num[1]);
    swap(tr[u << 1 | 1].ml[0], tr[u << 1 | 1].ml[1]);
    swap(tr[u << 1 | 1].mr[0], tr[u << 1 | 1].mr[1]);
    swap(tr[u << 1 | 1].mx[0], tr[u << 1 | 1].mx[1]);

    tr[u].lz = 0;
}
void push_down(int u)
{
    if(tr[u].co != -1) colour(u);
    if(tr[u].lz == 1) reverse(u);
}
void build(int u, int l, int r)
{
    tr[u].l = l, tr[u].r = r;
    tr[u].len = r - l + 1;
    tr[u].co = -1, tr[u].lz = 0;
    if(l == r)
    {
        int v = a[l];
        tr[u].num[v] = tr[u].ml[v] = tr[u].mr[v] = tr[u].mx[v] = 1;
        return ;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    push_up(u);
}
void change(int u, int l, int r, int x)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].co = x;
        tr[u].lz = 0;
        tr[u].num[x] = tr[u].len;
        tr[u].num[!x] = 0;
        tr[u].ml[x] = tr[u].mr[x] = tr[u].mx[x] = tr[u].len;
        tr[u].ml[!x] = tr[u].ml[!x] = tr[u].mx[!x] = 0;
        return ;
    }
    push_down(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) change(u << 1, l, r, x);
    if(mid < r) change(u << 1 | 1, l, r, x);
    push_up(u);
}
void rever(int u, int l, int r)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        tr[u].lz ^= 1;
        swap(tr[u].num[0], tr[u].num[1]);
        swap(tr[u].ml[0], tr[u].ml[1]);
        swap(tr[u].mr[0], tr[u].mr[1]);
        swap(tr[u].mx[0], tr[u].mx[1]);
        return ;
    }
    push_down(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(l <= mid) rever(u << 1, l, r);
    if(mid < r) rever(u << 1 | 1, l, r);
    push_up(u);
}
int query_sum(int u, int l, int r)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        return tr[u].num[1];
    }
    push_down(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    int ans = 0;
    if(l <= mid) ans += query_sum(u << 1, l, r);
    if(mid < r) ans += query_sum(u << 1 | 1, l, r);
    return ans;
}
node query_part(int u, int l, int r)
{
    if(l <= tr[u].l && tr[u].r <= r)
    {
        return tr[u];
    }
    push_down(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(r <= mid) return query_part(u << 1, l, r);
    else if(mid < l) return query_part(u << 1 | 1, l, r);

    node now;
    node ls = query_part(u << 1, l, r), rs = query_part(u << 1 | 1, l, r);

    for(int i = 0; i <= 1; i++)
    {
        now.ml[i] = ls.ml[i];
        if(ls.ml[i] == ls.len) now.ml[i] = ls.len + rs.ml[i];

        now.mr[i] = rs.mr[i];
        if(rs.mr[i] == rs.len) now.mr[i] = rs.len + ls.mr[i];

        now.mx[i] = max(ls.mr[i] + rs.ml[i], max(ls.mx[i], rs.mx[i]));
    }
    return now;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while(m--)
    {
        int opt, l, r;
        cin >> opt >> l >> r;
        opt++;
        l++, r++;
        if(opt == 1)
        {
            change(1, l, r, 0);
        }
        if(opt == 2)
        {
            change(1, l, r, 1);
        }
        if(opt == 3)
        {
            rever(1, l, r);
        }
        if(opt == 4)
        {
            cout << query_sum(1, l, r) << endl;
        }
        if(opt == 5)
        {
            cout << query_part(1, l, r).mx[1] << endl;
        }
    }
    return 0;
}

by _buzhidao_ @ 2024-07-18 19:14:14

@xudongyi1 here

by xudongyi1 @ 2024-07-18 19:16:41

@buzhidao 看不懂\kk，大佬能不能解释一下。

by _buzhidao_ @ 2024-07-18 20:43:22

@xudongyi1 能不能简单说说代码思路？CSP不太好，代码阅读能力不强。

by xudongyi1 @ 2024-07-18 21:17:49

@buzhidao 维护前缀最大值，后缀最大值，合并成最大字段和。

co 是覆盖的懒标记，lz 是翻转的懒标记。

把所有要求的给维护起来了（）

by _buzhidao_ @ 2024-07-18 22:53:39

@xudongyi1 大概测试一下是哪个操作出了问题？

by xudongyi1 @ 2024-07-19 11:05:22

@buzhidao 50 pts了，改了一下 push_down 里面的覆盖，如下。