谁的问题?
  • 板块CF52C Circular RMQ
  • 楼主BIOS
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/8/1 21:43
  • 上次更新2023/11/3 06:27:28
查看原帖
谁的问题?
833124
BIOS楼主2023/8/1 21:43
#include <iostream>
using namespace std;
const int N = 2e5 + 5;
struct node
{
    int l, r, v, add;
} tr[N << 2];
int n, w[N], m, x, y, c, space;
int read()
{
    int res = 0, f = 1;
    char c = getchar();
    while (!isdigit(c))
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (isdigit(c))
        res = res * 10 + c - 48, c = getchar();
    if (c == ' ')
        ++space;
    return res * f;
}
void pushup(int u)
{
    tr[u].v = min(tr[u << 1].v, tr[u << 1 | 1].v);
}
void pushdown(node &u, node &l, node &r)
{
    if (u.add)
    {
        l.add += u.add, r.add += u.add;
        l.v += u.add, r.v += u.add;
        u.add = 0;
    }
}
void pushdown(int u)
{
    pushdown(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
    if (l == r)
        tr[u] = {l, r, w[r], 0};
    else
    {
        tr[u].r = r, tr[u].l = l;
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
void modify(int u, int l, int r, int v)
{
    if (tr[u].l >= l && tr[u].r <= r)
        tr[u].add += v, tr[u].v += v;
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid)
            modify(u << 1, l, r, v);
        if (r > mid)
            modify(u << 1 | 1, l, r, v);
        pushup(u);
    }
}
int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
        return tr[u].v;
    else
    {
        pushdown(u);
        int mid = tr[u].r + tr[u].l >> 1;
        int minv = 0x7f7f7f7f;
        if (l <= mid)
            minv = min(minv, query(u << 1, l, r));
        if (r > mid)
            minv = min(minv, query(u << 1 | 1, l, r));
        return minv;
    }
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    cin >> m;
    build(1, 1, n);
    while (m--)
    {
        space = 0;
        x = read(), y = read(), x++, y++;
        if (space == 2)
        {
            c = read();
            if (x <= y)
                modify(1, x, y, c);
            else
                modify(1, x, n, c), modify(1, 1, y, c);
        }
        else
        {
            if (x <= y)
                cout << query(1, x, y) << "\n";
            else
                cout << min(query(1, x, n), query(1, 1, y)) << "\n";
        }
    }
}

因为输入处理不了,不会快读,所以快读函数照搬的题解,结果我用快读直接TLE,改成cin就能出结果,这是为什么????而且题解的read在他自己的代码里是不会TLE的。

2023/8/1 21:43
加载中...