求助

P1253 扶苏的问题

DreamCHN @ 2023-09-29 14:31:03

为什么第十个点TLE了???

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, q;
ll a[1000010];
struct node
{
    ll l, r;
    ll maxn;
    ll add, cover, used;
}tr[4000010];

void pushup(ll u)
{
    tr[u].maxn = max(tr[u << 1].maxn, tr[u << 1 | 1].maxn);
}

void pushdown(ll u)
{
    node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
   if(root.used)
   {
       left.cover = right.cover = root.cover;
       left.add = right.add = root.add;
       left.maxn = right.maxn = root.add + root.cover;
       left.used = right.used = 1;
   }
   else
   {
       left.maxn += root.add;
       right.maxn += root.add;
       left.add += root.add;
       right.add += root.add;
   }

   root.used = root.add = root.cover = 0;
}

void build(ll u, ll l, ll r)
{
    if(l == r)
    {
        tr[u] = {l, r, a[l], 0, 0, 0};
        return;
    }

    tr[u] = {l, r};
    ll mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify2(ll u, ll l, ll r, ll d)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].add += d;
        tr[u].maxn += d;
        return;
    }

    pushdown(u);
    ll mid = tr[u].l + tr[u].r >> 1;
    if(mid >= l)
    modify2(u << 1, l, r, d);
    if(r > mid)
    modify2(u << 1 | 1, l, r, d);
    pushup(u);
}

void modify1(ll u, ll l, ll r, ll d)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].add = 0;
        tr[u].maxn = d;
        tr[u].cover = d;
        tr[u].used = 1;
        return;
    }

    pushdown(u);
    ll mid = tr[u].l + tr[u].r >> 1;
    if(mid >= l)
    modify1(u << 1, l, r, d);
    if(r > mid)
    modify1(u << 1 | 1, l, r, d);
    pushup(u);
}

ll query(ll u, ll l, ll r)
{
    if(tr[u].l >= l && tr[u].r <= r)
    return tr[u].maxn;

    pushdown(u);
    ll mid = tr[u].l + tr[u].r >> 1, res = -1e18;
    if(mid >= l)
    res = query(u << 1, l, r);
    if(r > mid)
    res = max(res, query(u << 1 | 1, l, r));
    return res;
}

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++)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            ll l, r, x;
            cin >> l >> r >> x;
            modify1(1, l, r, x);
        }
        if(op == 2)
        {
            ll l, r, x;
            cin >> l >> r >> x;
            modify2(1, l, r, x);
        }
        if(op == 3)
        {
            ll l, r;
            cin >> l >> r;
            cout << query(1, l, r) << endl;
        }
    }

    return 0;
}

by lhc0707 @ 2023-09-30 12:10:59

main() 里面加上这两行:

ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);

这会让你的输入输出变快,然后你就可以AC了

AC记录


by lhc0707 @ 2023-09-30 12:12:19

下次记得用快一点的输入输出,不加上面那两行的 cincout 太慢了。


by lhc0707 @ 2023-09-30 12:15:14

你这马蜂太恶心了


|