10分玄关求调(马蜂良好

P2572 [SCOI2010] 序列操作

1_1_1_1_1_1_ @ 2024-07-30 17:52:21

除了#2和hack外全WA

#include<bits/stdc++.h>

using namespace std;

struct node
{
    int sum0, sum1;//共有多少个0,1 
    int m0, m1;//连续0,1的最长长度 
    int l0, r0, l1, r1;//l0表示从左起连续0的长度 
    node(int asum0, int am0, int al0, int ar0 , int asum1 , int am1 , int al1 , int ar1 )
    {
        sum0 = asum0;
        m0 = am0;
        l0 = al0;
        r0 = ar0;
        sum1 = asum1;
        m1 = am1;
        l1 = al1;
        r1 = ar1;
    }
    node(){

    }
}tr[400010];

int n, m;
int a[400010];
int tag[400010];//更改的懒标记,-1表示不需要更改,0表示改为0,1表示改为1 
bool tag2[400010];//取反的懒标记 

node qufan(node x)//取反一个节点 
{
    swap(x.sum0, x.sum1);
    swap(x.m0, x.m1);
    swap(x.l0, x.l1);
    swap(x.r0, x.r1);
    return x;
}

void push_down(int id, int l, int r)//下放懒标记 
{
    int mid = (l + r) / 2;
    if(tag[id] != -1)//需要更改为0或1 
    {
        int x = tag[id];
        tag[id * 2] = x;
        tag[id * 2 + 1] = x;
        tag[id] = -1;
        node g;
        int k;
        if(x == 0)
        {
            k = mid - l + 1;
            g = node(k, k, k, k, 0, 0, 0, 0);
            tr[id * 2] = g;

            k = r - mid;
            g = node(k, k, k, k, 0, 0, 0, 0);
            tr[id * 2 + 1] = g;
        }
        else
        {
            k = mid - l + 1;
            g = node(0, 0, 0, 0, k, k, k, k);
            tr[id * 2] = g;

            k = r - mid;
            g = node(0, 0, 0, 0, k, k, k, k);
            tr[id * 2 + 1] = g;
        }
    }
    if(tag2[id] == 1)//需要取反 
    {
        tr[id * 2] = qufan(tr[id * 2]);
        tr[id * 2 + 1] = qufan(tr[id * 2 + 1]);
        tag2[id * 2] = 1 - tag2[id * 2];//1变为0,0变为1 
        tag2[id * 2 + 1] = 1 - tag2[id * 2 + 1];//1变为0,0变为1 
        tag2[id] = 0;
    }
}

node push_up(node x, node y)//合并区间 
{
    node ans;
    ans.sum0 = x.sum0 + y.sum0;
    ans.sum1 = x.sum1 + y.sum1;

    ans.m0 = max(x.r0 + y.l0, max(x.m0, y.m0));
    if(x.sum1 == 0)//左子树全是0 
    {
        ans.l0 = x.sum0 + y.l0;
    }
    else
    {
        ans.l0 = x.l0;
    }
    if(y.sum1 == 0)//右子树全是0 
    {
        ans.r0 = x.r0 + y.sum0;
    }
    else
    {
        ans.r0 = y.r0;
    }

    ans.m1 = max(x.r1 + y.l1, max(x.m1, y.m1));
    if(x.sum0 == 0)//左子树全是1 
    {
        ans.l1 = x.sum1 + y.l1;
    }
    else
    {
        ans.l1 = x.l1;
    }
    if(y.sum0 == 0)//右子树全是1 
    {
        ans.r1 = x.r1 + y.sum1;
    }
    else
    {
        ans.r1 = y.r1;
    }
    return ans;
}

void build(int id, int l, int r)//建树 
{
    if(l == r)
    {
        if(a[l] == 1)
        {
            tr[id].sum1 = 1;
            tr[id].m1 = 1;
            tr[id].l1 = 1;
            tr[id].r1 = 1;
        }
        else
        {
            tr[id].sum0 = 1;
            tr[id].m0 = 1;
            tr[id].l0 = 1;
            tr[id].r0 = 1;
        }
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    tr[id] = push_up(tr[id * 2], tr[id * 2 + 1]);
}

void gengxin_0(int id, int l, int r, int left, int right)//全部改为0 
{
    if(left <= l && r <= right)
    {
        if(tag2[id] == 1)
        {
            tag2[id] = 0;
        }
        int k = r - l + 1;
        tr[id] = node(k, k, k, k, 0, 0, 0, 0);
        tag[id] = 0;
        return;
    }
    push_down(id, l, r);
    int mid = (l + r) / 2;
    if(left <= mid)
    {
        gengxin_0(id * 2, l, mid, left, right);
    }
    if(mid < right)
    {
        gengxin_0(id * 2 + 1, mid + 1, r, left, right);
    }
    tr[id] = push_up(tr[id * 2], tr[id * 2 + 1]);
}

void gengxin_1(int id, int l, int r, int left, int right)//全部改为1 
{
    if(left <= l && r <= right)
    {
        if(tag2[id] == 1)
        {
            tag2[id] = 0;
        }
        int k = r - l + 1;
        tr[id] = node(0, 0, 0, 0, k, k, k, k);
        tag[id] = 1;
        return;
    }
    push_down(id, l, r);
    int mid = (l + r) / 2;
    if(left <= mid)
    {
        gengxin_1(id * 2, l, mid, left, right);
    }
    if(mid < right)
    {
        gengxin_1(id * 2 + 1, mid + 1, r, left, right);
    }
    tr[id] = push_up(tr[id * 2], tr[id * 2 + 1]);
}

void gengxin_qufan(int id, int l, int r, int left, int right)//取反 
{
    if(left <= l && r <= right)
    {
        tr[id] = qufan(tr[id]);
        tag2[id] = 1 - tag2[id];
        return;
    }
    push_down(id, l, r);
    int mid = (l + r) / 2;
    if(left <= mid)
    {
        gengxin_qufan(id * 2, l, mid, left, right);
    }
    if(mid < right)
    {
        gengxin_qufan(id * 2 + 1, mid + 1, r, left, right);
    }
    tr[id] = push_up(tr[id * 2], tr[id * 2 + 1]);
}

int ask_sum(int id, int l, int r, int left, int right)//询问1的个数 
{
    if(left <= l && r <= right)
    {
        return tr[id].sum1;
    }
    push_down(id, l, r);
    int mid = (l + r) / 2;
    int ans = 0;
    if(left <= mid)
    {
        ans = ask_sum(id * 2, l, mid, left, right); 
    }
    if(mid < right)
    {
        ans += ask_sum(id * 2 + 1, mid + 1, r, left, right);
    }
    return ans;
}

node ask_d(int id, int l, int r, int left, int right)//询问最长连续1的长度 
{
    if(left <= l && r <= right)
    {
        return tr[id];
    }
    push_down(id, l, r);
    int mid = (l + r) / 2;
    node x, y;
    bool flagx = 0;
    bool flagy = 0;
    if(left <= mid)
    {
        flagx = 1;
        x = ask_d(id * 2, l, mid, left, right);
    }
    if(mid < right)
    {
        flagy = 1;
        y = ask_d(id * 2 + 1, mid + 1, r, left, right);
    }
    if(flagx == 0)
    {
        return y;
    }
    if(flagy == 0)
    {
        return x;
    }
    return push_up(x, y);
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    memset(tag, -1, sizeof(tag));
    build(1, 1, n);
    for(int i = 1; i <= m; i++)
    {
        int op, l, r;
        cin >> op >> l >> r;
        l++;
        r++;
        if(op == 0)
        {
            gengxin_0(1, 1, n, l, r);
        }
        else if(op == 1)
        {
            gengxin_1(1, 1, n, l, r);
        }
        else if(op == 2)
        {
            gengxin_qufan(1, 1, n, l, r);
        }
        else if(op == 3)
        {
            cout << ask_sum(1, 1, n, l, r) << endl;
        }
        else if(op == 4)
        {
            node g = ask_d(1, 1, n, l, r);
            cout << g.m1 << endl;
        }
    }
    return 0;
}

by wrh316 @ 2024-07-31 09:17:09

代码风格确实良好


by fzy_qwq @ 2024-07-31 10:03:19

@1_1_1_1_11 不如暴力拿30分


by pugong @ 2024-08-09 21:29:20

@1_1_1_1_11 给你组数据
输入:

7 5
0 0 1 1 1 1 0 
3 5 6
2 1 5
0 2 6
3 1 4
2 5 6

输出:

1
1

|