分块80分第5个点TLE求调

myyyIisq2R @ 2023-07-24 11:49:15

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

int n,m;
int a[5000001];
int tag[5000001],L[50001],R[50001],sum[50001],lz[50001];

inline void Change(int l,int r,int k)
{
    if(tag[l] == tag[r])
    {
        for(int i = l; i <= r; i ++)
        {
            a[i] += k;
            sum[tag[i]] += k;
        }
        return;
    }
    for(int i = l; i <= R[tag[l]]; i ++)
    {
        a[i] += k;
        sum[tag[i]] += k;
    }
    for(int i = tag[l] + 1; i < tag[r]; i ++)
    {
        lz[i] += k;
        sum[i] += (R[i] - L[i] + 1) * k;
    }

    for(int i = L[tag[r]]; i <= r; i ++)
    {
        a[i] += k;
        sum[tag[i]] += k;
    }

}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    int len = sqrt(n);
    for(int i = 1; i <= n; i ++)
        tag[i] = (i - 1) / len + 1;
    for(int i = 1; i <= tag[n]; i ++)
    {
        L[i] = R[i - 1] + 1;
        R[i] = min(n,L[i] + len - 1);
    }

    for(int i = 1; i <= n; i ++) cin>>a[i];
    for(int i = 1; i <= tag[n]; i ++)
        for(int j = L[i]; j <= R[i]; j ++)
            sum[i] += a[j];
    for(int i = 1; i <= m; i ++)
    {
        int l,r,k;
        cin>>l>>r>>k;
        Change(l,r,k);
    }
    int minn = INT_MAX;
    for(int i {1}; i<=n; i++)
        minn = min(a[i] + lz[tag[i]],minn);
    cout<<minn;
    return 0;
}

by m1kusama @ 2023-07-24 11:49:59

666

by myyyIisq2R @ 2023-07-24 11:50:26

@_m_i_ku !

by OldDriverTree @ 2023-07-24 11:52:35

@wangmingwei 这时间复杂度本来就不对呀

by furina_superstar @ 2023-07-24 11:54:12

@wangmingwei 你不是过了吗

by m1kusama @ 2023-07-24 11:56:10

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int n,m;
int a[5000001];
int tag[5000001],L[50001],R[50001],sum[50001],lz[50001];

inline void Change(int l,int r,int k)
{
    if(tag[l] == tag[r])
    {
        for(int i = l; i <= r; i ++)
        {
            a[i] += k;
            sum[tag[i]] += k;
        }
        return;
    }
    for(int i = l; i <= R[tag[l]]; i ++)
    {
        a[i] += k;
        sum[tag[i]] += k;
    }
    for(int i = tag[l] + 1; i < tag[r]; i ++)
    {
        lz[i] += k;
        sum[i] += (R[i] - L[i] + 1) * k;
    }

    for(int i = L[tag[r]]; i <= r; i ++)
    {
        a[i] += k;
        sum[tag[i]] += k;
    }

}
inline
int _min(int a,int b){
    if(a<b)return a;
    return b;
}
signed main()
{
    n=read(),m=read();
    int len = sqrt(n);
    for(int i = 1; i <= n; i ++)
        tag[i] = (i - 1) / len + 1;
    for(int i = 1; i <= tag[n]; i ++)
    {
        L[i] = R[i - 1] + 1;
        R[i] = _min(n,L[i] + len - 1);
    }

    for(int i = 1; i <= n; i ++) a[i]=read();
    for(int i = 1; i <= tag[n]; i ++)
        for(int j = L[i]; j <= R[i]; j ++)
            sum[i] += a[j];
    for(int i = 1; i <= m; i ++)
    {
        int l,r,k;
        cin>>l>>r>>k;
        Change(l,r,k);
    }
    int minn = INT_MAX;
    for(int i {1}; i<=n; i++)
        minn = _min(a[i] + lz[tag[i]],minn);
    cout<<minn;
    return 0;
}

by m1kusama @ 2023-07-24 11:56:38

c++98 o2 996ms

by m1kusama @ 2023-07-24 11:59:27

@wangmingwei

by myyyIisq2R @ 2023-07-24 12:04:45

@_m_i_ku 卡常之神？

by m1kusama @ 2023-07-24 14:07:41

@wangmingwei 错误的

by YangJZHello @ 2023-07-26 18:18:49

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

加上这个