萌新求助

P4513 小白逛公园

lonely_cyx @ 2022-09-17 21:51:29

代码

#pragma G++ optimize(2)
#pragma G++ optimize(3)
#pragma G++ optimize("Ofast")
#pragma G++ optimize("inline")
#pragma G++ optimize("-fgcse")
#pragma G++ optimize("-fgcse-lm")
#pragma G++ optimize("-fipa-sra")
#pragma G++ optimize("-ftree-pre")
#pragma G++ optimize("-ftree-vrp")
#pragma G++ optimize("-fpeephole2")
#pragma G++ optimize("-ffast-math")
#pragma G++ optimize("-fsched-spec")
#pragma G++ optimize("unroll-loops")
#pragma G++ optimize("-falign-jumps")
#pragma G++ optimize("-falign-loops")
#pragma G++ optimize("-falign-labels")
#pragma G++ optimize("-fdevirtualize")
#pragma G++ optimize("-fcaller-saves")
#pragma G++ optimize("-fcrossjumping")
#pragma G++ optimize("-fthread-jumps")
#pragma G++ optimize("-funroll-loops")
#pragma G++ optimize("-fwhole-program")
#pragma G++ optimize("-freorder-blocks")
#pragma G++ optimize("-fschedule-insns")
#pragma G++ optimize("inline-functions")
#pragma G++ optimize("-ftree-tail-merge")
#pragma G++ optimize("-fschedule-insns2")
#pragma G++ optimize("-fstrict-aliasing")
#pragma G++ optimize("-fstrict-overflow")
#pragma G++ optimize("-falign-functions")
#pragma G++ optimize("-fcse-skip-blocks")
#pragma G++ optimize("-fcse-follow-jumps")
#pragma G++ optimize("-fsched-interblock")
#pragma G++ optimize("-fpartial-inlining")
#pragma G++ optimize("no-stack-protector")
#pragma G++ optimize("-freorder-functions")
#pragma G++ optimize("-findirect-inlining")
#pragma G++ optimize("-fhoist-adjacent-loads")
#pragma G++ optimize("-frerun-cse-after-loop")
#pragma G++ optimize("inline-small-functions")
#pragma G++ optimize("-finline-small-functions")
#pragma G++ optimize("-ftree-switch-conversion")
#pragma G++ optimize("-foptimize-sibling-calls")
#pragma G++ optimize("-fexpensive-optimizations")
#pragma G++ optimize("-funsafe-loop-optimizations")
#pragma G++ optimize("inline-functions-called-once")
#pragma G++ optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[10000010];
int dp[10000010];
int n;
inline void operation1(int x,int y)
{
    a[x]=y;
}
inline int operation2(int l,int r)
{
    memset(dp,0,sizeof(dp));
    int maxn=-0x7f7f7f7f;
    for(int i=l;i<=r;i++)
    {
        if(i<2)
        {
            dp[i]=a[i];
        }
        else
        {
            dp[i]=max(a[i],dp[i-1]+a[i]);
        }
        maxn=max(dp[i],maxn);
    }
    return maxn;
}
inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}
inline int read() 
{
     bool f=false; 
     int x=0;
     char ch=getchar();
     while(ch<'0'||ch>'9') 
     {
         if(ch=='-') 
         {
            f=true;
         }
         ch=getchar();
     }
     while(ch>='0'&&ch<='9') 
     {
         x=(x<<1)+(x<<3)+ch-'0';
         ch=getchar();
     }
     return f?-x:x;
 }
signed main()
{
    int q;
    n=read();
    q=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    while(q--)
    {
        int op;
        op=read();
        if(op==2)
        {
            int x,y;
            x=read();
            y=read();
            operation1(x,y);
         } 
        if(op==1)
        {
            int l,r;
            l=read();
            r=read();
            if(l>r)
            {
                swap(l,r);
            }
            write(operation2(l,r));
            putchar('\n');
        }
    }
    return 0;
}

18pts


by Node_Edge @ 2022-09-17 22:02:20

@hyzhuo 这不得 T 飞吗


by Francais_Drake @ 2022-09-20 17:37:50

  1. 数组只需要 5e5 范围你开到了 1e8

建议线段树/平衡树/分块


by Francais_Drake @ 2022-09-20 17:40:27

@hyzhuo


|