社区讨论

求问关于常数

eexCRT
P7809[JRKSJ R2] 01 序列参与者 4已保存回复 7

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@mlhld1jk
此快照首次捕获于
2026/02/11 13:30
上周
此快照最后确认于
2026/02/13 08:05
6 天前
查看原帖
rt，本人卡常后提交的代码如下：
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
char buf[1<<17],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<16,stdin),p1==p2)?EOF:*p1++)
void qread(int &n)
{
    n=0;char c=0;bool f=1;
    for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=0;
    if(!f)for(;'0'<=c&&c<='9';n=n*10+'0'-c,c=getchar());
    else for(;'0'<=c&&c<='9';n=n*10+c-'0',c=getchar());
}
void qwrite(int x)
{
    if(x==0)
    {
        putchar('0');
        return;
    }
    char op[50]={};
    int top=0;
    if(x<0)x=-x,putchar('-');
    for(;x;op[40-++top]=x%10+'0',x/=10);
    fwrite(op+40-top,1,top,stdout);
    putchar('\n');
}
#define MAXN 1000000
int n,m;
int a[MAXN+10];
int nx0[MAXN+10],nx1[MAXN+10];
int f[23][MAXN+10];
int s0[MAXN+10],s1[MAXN+10];
int op,l,r;
signed main()
{
    qread(n);qread(m);
    for(int i=1;i<=n;i++)qread(a[i]);
    nx0[n+1]=nx1[n+1]=n+1;
    for(int i=1;i<=n;i++)
    {
        s0[i]=s0[i-1]+(a[i]==0);
        s1[i]=s1[i-1]+(a[i]==1);
        f[0][i]=s0[i]-s1[i];
    }
    for(int i=n;i>=1;i--)
    {
        nx0[i]=(a[i]==0?i:nx0[i+1]);
        nx1[i]=(a[i]==1?i:nx1[i+1]);
    }
    for(int j=1;j<=20;j++)for(int i=0;i+(1<<j)-1<=n;i++)
        f[j][i]=max(f[j-1][i],f[j-1][i+(1<<j-1)]);
    for(;m--;)
    {
        qread(op);qread(l);qread(r);
        if(op==1)
        {
            int log2n=__lg(r-l+2);
            qwrite(s1[r]-s0[l-1]+max(f[log2n][l-1],f[log2n][r-(1<<log2n)+1]));
        }
        else
        {
            qwrite(nx1[nx0[l]]<=r?2:1);
        }
    }
}
这段代码虽然ST表建立时的时间复杂度去掉常数后是 O(n)O(n)，但是 log⁡2n\log_2 n 始终不比20大，所以我推断下段代码的实际运行时间要比上面的代码少：
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
char buf[1<<17],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<16,stdin),p1==p2)?EOF:*p1++)
void qread(int &n)
{
    n=0;char c=0;bool f=1;
    for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=0;
    if(!f)for(;'0'<=c&&c<='9';n=n*10+'0'-c,c=getchar());
    else for(;'0'<=c&&c<='9';n=n*10+c-'0',c=getchar());
}
void qwrite(int x)
{
    if(x==0)
    {
        putchar('0');
        return;
    }
    char op[50]={};
    int top=0;
    if(x<0)x=-x,putchar('-');
    for(;x;op[40-++top]=x%10+'0',x/=10);
    fwrite(op+40-top,1,top,stdout);
    putchar('\n');
}
#define MAXN 1000000
int n,m;
int a[MAXN+10];
int nx0[MAXN+10],nx1[MAXN+10];
int f[23][MAXN+10];
int s0[MAXN+10],s1[MAXN+10];
int op,l,r;
signed main()
{
    qread(n);qread(m);
    int log2n=__lg(n);
    for(int i=1;i<=n;i++)qread(a[i]);
    nx0[n+1]=nx1[n+1]=n+1;
    for(int i=1;i<=n;i++)
    {
        s0[i]=s0[i-1]+(a[i]==0);
        s1[i]=s1[i-1]+(a[i]==1);
        f[0][i]=s0[i]-s1[i];
    }
    for(int i=n;i>=1;i--)
    {
        nx0[i]=(a[i]==0?i:nx0[i+1]);
        nx1[i]=(a[i]==1?i:nx1[i+1]);
    }
    for(int j=1;j<=log2n;j++)for(int i=0;i+(1<<j)-1<=n;i++)
        f[j][i]=max(f[j-1][i],f[j-1][i+(1<<j-1)]);
    for(;m--;)
    {
        qread(op);qread(l);qread(r);
        if(op==1)
        {
            log2n=__lg(r-l+2);
            qwrite(s1[r]-s0[l-1]+max(f[log2n][l-1],f[log2n][r-(1<<log2n)+1]));
        }
        else
        {
            qwrite(nx1[nx0[l]]<=r?2:1);
        }
    }
}
但是神奇的事情发生了，下面这段代码的实际运行时间要更慢一些，为了防止误差，我还特意重复了3次，但结果平均下来依旧是第一段代码时间更优：
代码1的第1次提交 代码1的第2次提交 代码1的第3次提交
代码2的第1次提交 代码2的第2次提交 代码2的第3次提交
于是想问一下各位大佬，是什么原因导致了这两段代码的效率差异？以后写代码的时候为了追求优秀效率该使用哪种写法？这两段代码的效率差异是否依赖编译器和O2优化？望求解。

回复

共 7 条回复，欢迎继续交流。

正在加载回复...