T1 数据太弱辣,加强一下?
  • 板块学术版
  • 楼主JackMerryYoung
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/10/3 18:09
  • 上次更新2023/10/27 09:00:53
查看原帖
T1 数据太弱辣,加强一下?
224558
JackMerryYoung楼主2022/10/3 18:09

这也过?

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

#define ll __int128_t
// #define ll long long
#define rint register ll

#define TOO_LARGE ((1 << 30) + 114514)
#define lc(x) (x << 1)
#define rc(x) ((x << 1) | 1)
#define myabs(x) (x > 0 ? x : -x)

struct SegmentTree {
    ll cj;
} tree[800005];

ll N, Q;
ll arr[800005];

// ll myabs(ll x)
// {
//     return x > 0 ? x : -x;
// }

void merge(ll p)
{
    if(tree[lc(p)].cj == TOO_LARGE || tree[rc(p)].cj == TOO_LARGE) 
        tree[p].cj = TOO_LARGE;
    else if((tree[lc(p)].cj * tree[rc(p)].cj) > (1 << 30)) 
        tree[p].cj = TOO_LARGE;
    else 
        tree[p].cj = (tree[lc(p)].cj * tree[rc(p)].cj);
}

void build(ll now_l, ll now_r, ll p)
{
    if(now_l == now_r)
    {
        if(arr[now_l] <= (1 << 30))
            tree[p].cj = arr[now_l];
        else
            tree[p].cj =  TOO_LARGE;

        return;
    }

    ll mid = (now_l + now_r) >> 1;
    build(now_l, mid + 0, lc(p));
    build(mid + 1, now_r, rc(p));
    merge(p);
}

void modify(ll now_l, ll now_r, ll x, ll k, ll p)
{
    if(now_l == now_r)
    {
        tree[p].cj = k;
        return;
    }

    ll mid = (now_l + now_r) >> 1;
    if(x <= (mid + 0)) modify(now_l, mid + 0, x, k, lc(p));
    if(x >= (mid + 1)) modify(mid + 1, now_r, x, k, rc(p));
    merge(p);
}

ll getans(ll now_l, ll now_r, ll l, ll r, ll p)
{
    if(l <= now_l && now_r <= r)
        return tree[p].cj;

    // cout << now_l << " " << now_r << " " << l << " " << r << endl;
    ll mid = (now_l + now_r) >> 1;
    ll res = 1;
    if(l <= (mid + 0)) res = res * getans(now_l, mid + 0, l, r, lc(p));
    if(r >= (mid + 1)) res = res * getans(mid + 1, now_r, l, r, rc(p));
    return res;
}

ll fastread()
{
    ll res = 0;
    char ch = getchar(), t = 1;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') t = -1;
        ch = getchar();
    }

    res = ch - '0';
    ch = getchar();
    while(ch >= '0' && ch <= '9')
    {
        res = (res << 1) + (res << 3) + (ch - '0');
        ch = getchar();
    }

    return res * t;
}

void fastwrite(ll x)
{
    if(x == 0)
    {
        puts("0");
        return;
    }
    char cnt = 0, s[40];
    if(x < 0)
        putchar('-'), x = -x;

    while(x)
    {
        s[++ cnt] = x % 10;
        x >>= 1, x /= 5;
    }

    for(char i = cnt; i >= 1; -- i)
        putchar(s[i] + '0');

    putchar('\n');
}

signed main()
{
    // freopen("T1ex2.in", "r", stdin);
    // freopen("T1ex2.ans", "w", stdout);
    N = fastread();
    Q = fastread();
    for(ll i = 1; i <= N; ++ i)
        arr[i] = fastread();

    build(1, N, 1);
    while(Q --)
    {
        ll opr;
        opr = fastread();
        if(opr == 1)
        {
            ll x, k;
            x = fastread();
            k = fastread();
            modify(1, N, x, k, 1);
            arr[x] = k;
        }
        if(opr == 2)
        {
            ll l, r, ans = 1;
            l = fastread();
            r = fastread();
            ans = getans(1, N, l, r, 1);
            if(ans < 0)
            {
                ll lcj, rcj;
                lcj = rcj = 1;
                for(ll i = l; i <= r; ++ i)
                {
                    if(arr[i] < 0)
                    {
                        lcj = getans(1, N, l, i, 1);
                        break;
                    }
                }

                for(ll i = r; i >= l; -- i)
                {
                    if(arr[i] < 0)
                    {
                        rcj = getans(1, N, i, r, 1);
                        break;
                    }
                }

                if(myabs(lcj) > myabs(rcj)) ans /= rcj;
                else                    ans /= lcj;
            }
            if(ans > (1 << 30) || ans <= 0) puts("Too large");
            else                fastwrite(ans);
        }
    }
    return 0;
}
2022/10/3 18:09
加载中...