#7 8 9 10 WA 求调

Gary0925 @ 2024-11-08 21:56:26

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define inf ((1LL << 63) - 1)
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define f(x) (x >> 1)
#define m(l, r) (l + r + 1 >> 1)
LL n, q, num[1000006], tree[4000006] = { 0 }, ctag[4000006] = { 0 }, atag[4000006] = { 0 };
void buildtree(LL id = 1, LL l = 1, LL r = n + 1)
{
    ctag[id] = inf, atag[id] = 0;
    if (l + 1 == r) tree[id] = num[l];
    else
        buildtree(ls(id), l, m(l, r)),
        buildtree(rs(id), m(l, r), r);
    tree[f(id)] = max(tree[ls(f(id))], tree[rs(f(id))]);
}
void setnode(LL id, LL l, LL r, LL c, LL a)
{
    ctag[id] = (c == inf) ? ctag[id] : c, atag[id] += a;
    if (ctag[id] == inf) tree[id] += a;
    else tree[id] = ctag[id];
}
void pushtag(LL id, LL l, LL r)
{
    setnode(ls(id), l, m(l, r), ctag[id], atag[id]);
    setnode(rs(id), m(l, r), r, ctag[id], atag[id]);
    ctag[id] = inf, atag[id] = 0;
}
void change(LL al, LL ar, LL c, LL id = 1, LL l = 1, LL r = n + 1)
{
    if (al <= l && ar >= r) { setnode(id, l, r, c, 0); return; }
    pushtag(id, l, r);
    if (al < m(l, r)) change(al, ar, c, ls(id), l, m(l, r));
    if (ar > m(l, r)) change(al, ar, c, rs(id), m(l, r), r);
    tree[id] = max(tree[ls(id)], tree[rs(id)]);
}
void add(LL al, LL ar, LL a, LL id = 1, LL l = 1, LL r = n + 1)
{
    if (al <= l && ar >= r) { setnode(id, l, r, inf, a); return; }
    pushtag(id, l, r);
    if (al < m(l, r)) add(al, ar, a, ls(id), l, m(l, r));
    if (ar > m(l, r)) add(al, ar, a, rs(id), m(l, r), r);
    tree[id] = max(tree[ls(id)], tree[rs(id)]);
}
LL findmax(LL al, LL ar, LL id = 1, LL l = 1, LL r = n + 1)
{
    if (al <= l && ar >= r) return tree[id];
    pushtag(id, l, r);
    LL ans = -inf;
    if (al < m(l, r)) ans = max(ans, findmax(al, ar, ls(id), l, m(l, r)));
    if (ar > m(l, r)) ans = max(ans, findmax(al, ar, rs(id), m(l, r), r));
    tree[id] = max(tree[ls(id)], tree[rs(id)]);
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> num[i];
    buildtree();
    while (q--)
    {
        int op, l, r; cin >> op >> l >> r;
        if (op == 1)
        {
            int x; cin >> x;
            change(l, r + 1, x);
        }
        else if (op == 2)
        {
            int x; cin >> x;
            add(l, r + 1, x);
        }
        else if (op == 3)
        {
            cout << findmax(l, r + 1) << "\n";
        }
    }
    return 0;
}

by Gary0925 @ 2024-11-18 10:01:36

讨论区的帖子基本都看了，问题点改了好多遍，还是过不去，现在代码改成这样了：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define inf ((1LL << 63) - 1)
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define f(x) (x >> 1)
#define m(l, r) (l + r + 1 >> 1)
LL n, q, num[1000006], tree[4000006] = { 0 }, ctag[4000006] = { 0 }, atag[4000006] = { 0 };
void buildtree(LL id = 1, LL l = 1, LL r = n + 1)
{
    ctag[id] = inf, atag[id] = 0;
    if (l + 1 == r) tree[id] = num[l];
    else
        buildtree(ls(id), l, m(l, r)),
        buildtree(rs(id), m(l, r), r);
    tree[f(id)] = max(tree[ls(f(id))], tree[rs(f(id))]);
}
void setnode(LL id, LL l, LL r, LL c, LL a)
{
    if (c != inf)
    {
        ctag[id] = c, atag[id] = 0;
        tree[id] = c;
    }
    else
    {
        atag[id] += a;
        tree[id] += a;
    }
}
void pushtag(LL id, LL l, LL r)
{
    setnode(ls(id), l, m(l, r), ctag[id], atag[id]);
    setnode(rs(id), m(l, r), r, ctag[id], atag[id]);
    ctag[id] = inf, atag[id] = 0;
}
void change(LL al, LL ar, LL c, LL id = 1, LL l = 1, LL r = n + 1)
{
    if (al <= l && ar >= r) { setnode(id, l, r, c, 0); return; }
    pushtag(id, l, r), atag[ls(id)] = 0, atag[rs(id)] = 0;
    if (al < m(l, r)) change(al, ar, c, ls(id), l, m(l, r));
    if (ar > m(l, r)) change(al, ar, c, rs(id), m(l, r), r);
    tree[id] = max(tree[ls(id)], tree[rs(id)]); 
}
void add(LL al, LL ar, LL a, LL id = 1, LL l = 1, LL r = n + 1)
{
    if (al <= l && ar >= r) { setnode(id, l, r, inf, a); return; }
    pushtag(id, l, r);
    if (al < m(l, r)) add(al, ar, a, ls(id), l, m(l, r));
    if (ar > m(l, r)) add(al, ar, a, rs(id), m(l, r), r);
    tree[id] = max(tree[ls(id)], tree[rs(id)]);
}
LL findmax(LL al, LL ar, LL id = 1, LL l = 1, LL r = n + 1)
{
    if (al <= l && ar >= r) return tree[id];
    pushtag(id, l, r);
    LL ans = -inf;
    if (al < m(l, r)) ans = max(ans, findmax(al, ar, ls(id), l, m(l, r)));
    if (ar > m(l, r)) ans = max(ans, findmax(al, ar, rs(id), m(l, r), r));
    tree[id] = max(tree[ls(id)], tree[rs(id)]);
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> num[i];
    buildtree();
    while (q--)
    {
        int op, l, r; cin >> op >> l >> r;
        if (op == 1)
        {
            int x; cin >> x;
            change(l, r + 1, x);
        }
        else if (op == 2)
        {
            int x; cin >> x;
            add(l, r + 1, x);
        }
        else if (op == 3)
        {
            //cout << "    ";  for (int i = 1; i <= n; i++) cout << findmax(i, i + 1) << " "; cout << "\n";
            cout << findmax(l, r + 1) << "\n";
        }
    }
    return 0;
}

by Gary0925 @ 2024-11-20 09:47:06

已AC，上面的代码需要改动处：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define inf ((1LL << 63) - 1)
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define f(x) (x >> 1)
#define m(l, r) (l + r + 1 >> 1)
LL n, q, num[1000006], tree[4000006] = { 0 }, ctag[4000006] = { 0 }, atag[4000006] = { 0 };
void buildtree(LL id = 1, LL l = 1, LL r = n + 1)
{
    ctag[id] = inf, atag[id] = 0;
    if (l + 1 == r) tree[id] = num[l];
    else
        buildtree(ls(id), l, m(l, r)),
        buildtree(rs(id), m(l, r), r);
    tree[f(id)] = max(tree[ls(f(id))], tree[rs(f(id))]);
}
void setnode(LL id, LL l, LL r, LL c, LL a)
{
    if (c != inf) ctag[id] = c, atag[id] = 0, tree[id] = c; //改为 atag[id] = a, tree[id] = c + a
    else atag[id] += a, tree[id] += a;
}
void pushtag(LL id, LL l, LL r)
{
    setnode(ls(id), l, m(l, r), ctag[id], atag[id]);
    setnode(rs(id), m(l, r), r, ctag[id], atag[id]);
    ctag[id] = inf, atag[id] = 0;
}
void change(LL al, LL ar, LL c, LL id = 1, LL l = 1, LL r = n + 1)
{
    if (al <= l && ar >= r) { setnode(id, l, r, c, 0); return; }
    pushtag(id, l, r), atag[ls(id)] = 0, atag[rs(id)] = 0; //增加 atag[ls(id)] = 0, atag[rs(id)] = 0
    if (al < m(l, r)) change(al, ar, c, ls(id), l, m(l, r));
    if (ar > m(l, r)) change(al, ar, c, rs(id), m(l, r), r);
    tree[id] = max(tree[ls(id)], tree[rs(id)]); 
}
void add(LL al, LL ar, LL a, LL id = 1, LL l = 1, LL r = n + 1)
{
    if (al <= l && ar >= r) { setnode(id, l, r, inf, a); return; }
    pushtag(id, l, r);
    if (al < m(l, r)) add(al, ar, a, ls(id), l, m(l, r));
    if (ar > m(l, r)) add(al, ar, a, rs(id), m(l, r), r);
    tree[id] = max(tree[ls(id)], tree[rs(id)]);
}
LL findmax(LL al, LL ar, LL id = 1, LL l = 1, LL r = n + 1)
{
    if (al <= l && ar >= r) return tree[id];
    pushtag(id, l, r);
    LL ans = -inf;
    if (al < m(l, r)) ans = max(ans, findmax(al, ar, ls(id), l, m(l, r)));
    if (ar > m(l, r)) ans = max(ans, findmax(al, ar, rs(id), m(l, r), r));
    tree[id] = max(tree[ls(id)], tree[rs(id)]);
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> num[i];
    buildtree();
    while (q--)
    {
        int op, l, r; cin >> op >> l >> r;
        if (op == 1)
        {
            int x; cin >> x;
            change(l, r + 1, x);
        }
        else if (op == 2)
        {
            int x; cin >> x;
            add(l, r + 1, x);
        }
        else if (op == 3)
        {
            cout << findmax(l, r + 1) << "\n";
        }
    }
    return 0;
}