20 pts求调

P1253 扶苏的问题

Geirangerfjard @ 2023-01-27 22:48:26

RT,样例1没过,样例2过了 提交20pts 其他MLE

#include <iostream>
#define lc(k) k << 1
#define rc(k) k << 1 | 1

const int N = 1000010;

using namespace std;

int n, q;

int a[N];

struct node
{
    int l, r, mx;
    int po, se;
    //int tag;
}tree[N * 4];

void build (int k, int l, int r)

{
    tree[k].l = l;
    tree[k].r = r;
    tree[k].po = tree[k].se = -1;
    if (l == r)
    {
        tree[k].mx = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build (lc (k), l, mid) , build (rc (k), mid + 1, r);
    tree[k].mx = max (tree[lc (k)].mx , tree[rc (k)].mx);
}

void lazy_po (int k, int v)

{
    tree[k].mx = v;
    tree[k].po = v;
    //tree[k].tag = 0;
}

void lazy_se (int k, int v)

{
    tree[k].se = v;
}

void change_po (int x, int y, int v, int k)

{
    int l = tree[k].l , r = tree[k].r ;
    if (x <= l && y >= r) return lazy_po (k, v);    
    if (tree[k].po != -1)
    {
        lazy_po (lc (k), tree[k].po);
        lazy_po (rc (k), tree[k].po);
        tree[k].po = -1;
    }
    if (tree[k].se != -1)
    {
        lazy_se (lc (k), tree[k].se);
        lazy_se (rc (k), tree[k].se);
        tree[k].se = -1;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) change_po (x, y, v, lc (k));
    if (y > mid) change_po (x, y, v, rc (k));
    tree[k].mx = max (tree[lc (k)].mx , tree[rc (k)].mx);
}

void change_se (int x, int y, int v, int k)

{
    int l = tree[k].l , r = tree[k].r ;
    if (x <= l && y >= r) return lazy_se (k, v);
    if (tree[k].se != -1)
    {
        lazy_se (lc (k), tree[k].se);
        lazy_se (rc (k), tree[k].se);
        tree[k].se = -1;
    }
    if (tree[k].po != -1)
    {
        lazy_po (lc (k), tree[k].po);
        lazy_po (rc (k), tree[k].po);
        tree[k].po = -1;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) change_se (x, y, v, lc (k));
    if (y > mid) change_se (x, y, v, rc (k));
    tree[k].mx = max (tree[lc (k)].mx , tree[rc (k)].mx);
}

int query (int x, int y, int k)

{
    int l = tree[k].l , r = tree[k].r ;
    if (l >= x && r <= y) return tree[k].mx;
    if (tree[k].po != -1)
    {
        lazy_po (lc (k), tree[k].po);
        lazy_po (rc (k), tree[k].po);
        tree[k].po = -1;
    }
    if (tree[k].se != -1)
    {
        lazy_se (lc (k), tree[k].se);
        lazy_se (rc (k), tree[k].se);
        tree[k].se = -1;
    }
    int mid = (l + r) >> 1;
    int ans = 0;
    if (x <= mid) ans = query (x, y, lc (x));
    if (y > mid) ans = max (ans , query (x, y, rc (x))); 
}

int main()

{
    cin >> n >> q;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    build (1, 1, n);
    while (q --)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int l, r, x;
            cin >> l >> r >> x;
            change_po (l, r, x, 1);
        }
        else if (op == 2)
        {
            int l, r, x;
            cin >> l >> r >> x;
            change_se (l, r, x, 1);
        }
        else if (op == 3)
        {
            int l, r;
            cin >> l >> r;
            cout << query (l, r, 1) << endl;
        }
    }
}

by dengzijun @ 2023-01-31 21:25:59

@Alone_Helpless

在build的时候,你把第一个lazytag初始化为了-1,这太大了,因为a数组的最小值可达-1e9。

另外,十年OI一场空,不开long long见祖宗。


by dengzijun @ 2023-01-31 21:26:51

@Alone_Helpless 你在**class上的讨论区里也可以看到我的回复。


by dengzijun @ 2023-01-31 21:33:18

@Alone_Helpless 还有,你需要注意,不同的操作顺序结果不同,用人话讲就是你的lazy_po和lazy_se函数都太简单了,很多情况都没考虑,建议你参考一下题解,出题人扶苏的题解就在第一篇。


by Geirangerfjard @ 2023-01-31 21:45:02

@dengzijun 好的 感谢奆佬


|