小白求助，WA on #6~9, TLE on #10

IQ勇士 @ 2022-08-18 10:05:25

#include<iostream>
#include<cstdio>
using namespace std;
const int freak = 2147483647;
int n, q, leftt, rightt, x, op, a[1000001];
struct tree{
    int maxx;
    int tg;
    int tj;
    int l;
    int r;
}t[4000001];
void build(int index, int ll, int rr)
{
    t[index].l = ll;
    t[index].r = rr;
    t[index].tg = freak;
    if(t[index].l == t[index].r)
        t[index].maxx = a[t[index].l];
    else
    {
        int m = (ll + rr) / 2;
        build(index * 2, ll, m);
        build(index * 2 + 1, m + 1, rr);
        t[index].maxx = max(t[index * 2].maxx, t[index * 2 + 1].maxx);
    }
}
bool qb(int l1, int r1, int l2, int r2)
{
    return l1 <= l2 && r1 >= r2;
}
bool noj(int l1, int r1, int l2, int r2)
{
    return l1 > r2 || l2 > r1;
}
void pushdown(int);
void tagging(int, int, int);
void pluss(int L, int R, int index, int xx)
{
    if(noj(L, R, t[index].l, t[index].r))
        return;
    if(qb(L, R, t[index].l, t[index].r))
        tagging(index, 2, xx);
    else
    {
        pushdown(index);
        pluss(L, R, index * 2, xx);
        pluss(L, R, index * 2 + 1, xx);
        t[index].maxx = max(t[index * 2].maxx, t[index * 2 + 1].maxx);
    }
}
void xg(int L, int R, int index, int xx)
{
    if(noj(L, R, t[index].l, t[index].r))
        return;
    if(qb(L, R, t[index].l, t[index].r))
        tagging(index, 1, xx);
    else
    {
        pushdown(index);
        xg(L, R, index * 2, xx);
        xg(L, R, index * 2 + 1, xx);
        t[index].maxx = max(t[index * 2].maxx, t[index * 2 + 1].maxx);
    }
}
int query(int L, int R, int index)
{
    if(noj(L, R, t[index].l, t[index].r))
        return -2147483647;
    if(qb(L, R, t[index].l, t[index].r))
        return t[index].maxx;
    else
    {
        pushdown(index);
        return max(query(L, R, index * 2), query(L, R, index * 2 + 1));
    }
}
int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    for(int i = 1; i <= q; i++)
    {
        cin >> op;
        if(op == 1)
        {
            cin >> leftt >> rightt >> x;
            xg(leftt, rightt, 1, x);
        }
        if(op == 2)
        {
            cin >> leftt >> rightt >> x;
            pluss(leftt, rightt, 1, x);
        }
        if(op == 3)
        {
            cin >> leftt >> rightt;
            cout << query(leftt, rightt, 1) << endl;
        }
    }
    return 0;
}
void pushdown(int index)
{
    tagging(index * 2, 2, t[index].tj);
    tagging(index * 2 + 1, 2, t[index].tj);
    if(t[index].tg != freak)
    {
        tagging(index * 2, 1, t[index].tg);
        tagging(index * 2 + 1, 1, t[index].tg);
    }
    t[index].tj = 0;
    t[index].tg = freak;
}
void tagging(int index, int oper, int xx)
{
    if(oper == 1 && oper != freak)//修改操作
    {
        t[index].maxx = xx;
        t[index].tg = xx;   
    } 
    else
    {
        t[index].maxx += xx;
        t[index].tj += xx;
        if(t[index].tg != freak)
        {
            tagging(index * 2, 1, t[index].tg);
            tagging(index * 2 + 1, 1, t[index].tg);
            t[index].tg = freak;
        }
    }
}

by IQ勇士 @ 2022-08-18 10:27:07

稍作修改之后现在代码长这样，但是评测结果还是跟之前一样

#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int freak = 2147483647;
int n, q, leftt, rightt, x, op, a[1000001];
int readin()
{
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9')
    {
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
struct tree{
    int maxx;
    int tg;
    int tj;
    int l;
    int r;
}t[4000001];
void build(int index, int ll, int rr)
{
    t[index].l = ll;
    t[index].r = rr;
    t[index].tg = freak;
    if(t[index].l == t[index].r)
        t[index].maxx = a[t[index].l];
    else
    {
        int m = (ll + rr) / 2;
        build(index * 2, ll, m);
        build(index * 2 + 1, m + 1, rr);
        t[index].maxx = max(t[index * 2].maxx, t[index * 2 + 1].maxx);
    }
}
bool qb(int l1, int r1, int l2, int r2)
{
    return l1 <= l2 && r1 >= r2;
}
bool noj(int l1, int r1, int l2, int r2)
{
    return l1 > r2 || l2 > r1;
}
void pushdown(int);
void tagging(int, int, int);
void pluss(int L, int R, int index, int xx)
{
    if(noj(L, R, t[index].l, t[index].r))
        return;
    if(qb(L, R, t[index].l, t[index].r))
        tagging(index, 2, xx);
    else
    {
        pushdown(index);
        pluss(L, R, index * 2, xx);
        pluss(L, R, index * 2 + 1, xx);
        t[index].maxx = max(t[index * 2].maxx, t[index * 2 + 1].maxx);
    }
}
void xg(int L, int R, int index, int xx)
{
    if(noj(L, R, t[index].l, t[index].r))
        return;
    if(qb(L, R, t[index].l, t[index].r))
        tagging(index, 1, xx);
    else
    {
        pushdown(index);
        xg(L, R, index * 2, xx);
        xg(L, R, index * 2 + 1, xx);
        t[index].maxx = max(t[index * 2].maxx, t[index * 2 + 1].maxx);
    }
}
int query(int L, int R, int index)
{
    if(noj(L, R, t[index].l, t[index].r))
        return -2147483647;
    if(qb(L, R, t[index].l, t[index].r))
        return t[index].maxx;
    else
    {
        pushdown(index);
        return max(query(L, R, index * 2), query(L, R, index * 2 + 1));
    }
}
signed main()
{
    n = readin();
    q = readin();
    for(int i = 1; i <= n; i++)
        a[i] = readin();
    build(1, 1, n);
    for(int i = 1; i <= q; i++)
    {
        op = readin();
        if(op == 1)
        {
            leftt = readin();
            rightt = readin();
            x = readin();
            xg(leftt, rightt, 1, x);
        }
        if(op == 2)
        {
            leftt = readin();
            rightt = readin();
            x = readin();
            pluss(leftt, rightt, 1, x);
        }
        if(op == 3)
        {
            leftt = readin();
            rightt = readin();
            cout << query(leftt, rightt, 1) << endl;
        }
    }
    return 0;
}
void pushdown(int index)
{
    tagging(index * 2, 2, t[index].tj);
    tagging(index * 2 + 1, 2, t[index].tj);
    if(t[index].tg != freak)
    {
        tagging(index * 2, 1, t[index].tg);
        tagging(index * 2 + 1, 1, t[index].tg);
    }
    t[index].tj = 0;
    t[index].tg = freak;
}
void tagging(int index, int oper, int xx)
{
    if(oper == 1 && oper != freak)//修改操作
    {
        t[index].maxx = xx;
        t[index].tg = xx;
        t[index].tj = 0;    
    } 
    else
    {
        t[index].maxx += xx;
        t[index].tj += xx;
        if(t[index].tg != freak)
        {
            tagging(index * 2, 1, t[index].tg);
            tagging(index * 2 + 1, 1, t[index].tg);
            t[index].tg = freak;
        }
    }
}

by Z1qqurat @ 2022-08-18 10:31:53

代码不太能看啊（

by IQ勇士 @ 2022-08-18 10:33:03

@Wrasar_CJ 马蜂一般，请见谅

by cmaths @ 2022-08-18 14:49:45

@IQ勇士 tj和tg是啥意思

by IQ勇士 @ 2022-08-18 15:32:49

@xjr300098 加法tag和赋值tag

by Blone_Dragon @ 2023-06-25 16:23:57

改成long应该除了超时其他能过