线段树最后一个点TLE，有人能帮帮优化吗

Sakuya_maid @ 2023-07-20 14:00:38

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

constexpr int N = 2e6 + 5;

int w[N];

struct Node
{
    int l, r, f, val;
}stg[N * 4];

void pushup(int k)
{
    stg[k].val = min(stg[k << 1].val, stg[k << 1 | 1].val);
}

inline void build(int l, int r, int k = 1)
{
    stg[k].l = l, stg[k].r = r;

    if(l == r)
    {
        stg[k].val = w[l];
        return;
    }

    int mid = (l + r) >> 1;

    if(l <= mid)build(l, mid, k << 1);
    if(r > mid)build(mid + 1, r, k << 1 | 1);

    pushup(k);
}

inline int query(int x, int y, int k = 1)
{
    int l = stg[k].l, r = stg[k].r;

    if(x <= l && y >= r)
    {
        return stg[k].val;
    }

    int mid = (l + r) >> 1, v = 999999999;

    if(x <= mid)v = min(query(x, y, k << 1), v);
    if(y > mid)v = min(v, query(x, y, k << 1 | 1));

    return v;
}

void solve()
{
    int n, m;

    cin >> n >> m;

    for(int i = 1; i <= n; ++ i)cin >> w[i];

    build(1, n);

    for(int i = 1; i <= n; ++ i)
    {
        if(i == 1)cout << 0 << '\n';
        else if(i == 2)cout << w[1] << '\n';
        else{
            int l = max(1, i - m);
            int r = i - 1;
            cout << query(l, r) << '\n';
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // int T;
    // for (cin >> T; T -- ; )
        solve();

}

by LgxTpre @ 2023-07-20 14:15:46

@Sakuya_maid 吸个氧

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2e6 + 5;

namespace FastIO
{
    template<typename T=int> inline T read()
    {
        T s=0,w=1; char c=getchar();
        while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
        while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
        return s*w;
    }
    template<typename T> inline void read(T &s)
    {
        s=0; int w=1; char c=getchar();
        while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
        while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
        s=s*w;
    }
    template<typename T,typename... Args> inline void read(T &x,Args &...args)
    {
        read(x),read(args...);
    }
    template<typename T> inline void write(T x,char ch)
    {
        if(x<0) x=-x,putchar('-');
        static char stk[25]; int top=0;
        do {stk[top++]=x%10+'0',x/=10;} while(x);
        while(top) putchar(stk[--top]);
        putchar(ch);
        return;
    }
}
using namespace FastIO;

int w[N];

struct Node
{
    int l, r, f, val;
}stg[N * 4];

void pushup(int k)
{
    stg[k].val = min(stg[k << 1].val, stg[k << 1 | 1].val);
}

inline void build(int l, int r, int k = 1)
{
    stg[k].l = l, stg[k].r = r;

    if(l == r)
    {
        stg[k].val = w[l];
        return;
    }

    int mid = (l + r) >> 1;

    if(l <= mid)build(l, mid, k << 1);
    if(r > mid)build(mid + 1, r, k << 1 | 1);

    pushup(k);
}

inline int query(int x, int y, int k = 1)
{
    int l = stg[k].l, r = stg[k].r;

    if(x <= l && y >= r)
    {
        return stg[k].val;
    }

    int mid = (l + r) >> 1, v = 999999999;

    if(x <= mid)v = min(query(x, y, k << 1), v);
    if(y > mid)v = min(v, query(x, y, k << 1 | 1));

    return v;
}

void solve()
{
    int n, m;

    read(n, m);

    for(int i = 1; i <= n; ++ i)read(w[i]);

    build(1, n);

    for(int i = 1; i <= n; ++ i)
    {
        if(i == 1)cout << 0 << '\n';
        else if(i == 2)cout << w[1] << '\n';
        else{
            int l = max(1, i - m);
            int r = i - 1;
            write(query(l, r),'\n');
        }
    }
}

int main()
{

        solve();

}

by Sakuya_maid @ 2023-07-20 15:09:57

@LgxTpre 草，我前面忘开O2了，谢谢大佬了