关于分块大小、数组大小以及O2的玄学问题

P2801 教主的魔法

ouuan @ 2018-09-29 13:45:45

AC代码见下方。

N为数组大小,B为分块大小(具体见代码)

N B O2 结果
1001010 998 AC
1001010 998 AC
1000010 998 WA80
1000010 998 AC
1001010 1000 WA80
1001010 1000 WA80

为什么会出现这种玄学现象...是我哪里写炸了吗?

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

inline int read()
{
    char c;int out=0;
    for (c=getchar();c<'0'||c>'9';c=getchar());
    for (;c>='0'&&c<='9';c=getchar()){out=(out<<3)+(out<<1)+c-'0';}
    return out;
}
void write(int x)
{
    if (x>9){write(x/10);}
    putchar(x%10+'0');
}

const int B=998;
const int N=1001010;

bool cmp(int x,int y);
void bf(int l,int r,int x);
int bq(int l,int r,int x);

int n,q,a[N],b[N],tag[N/B+10],bl[N],ll[N/B+10],rr[N/B+10];
char wtf[10];

int main()
{
    int i,l,r,x,ans;

    n=read();
    q=read();

    for (i=1;i<=n;++i)
    {
        cin>>a[i];
        b[i]=i;
        bl[i]=(i-1)/B+1;
    }

    for (i=1;i<=bl[n];++i)
    {
        ll[i]=i*B-B+1;
        rr[i]=i*B;
        sort(b+ll[i],b+rr[i]+1,cmp);
    }

    rr[bl[n]]=n;

    while (q--)
    {
        scanf("%s",wtf);
        l=read();
        r=read();
        x=read();
        if (wtf[0]=='M')
        {
            if (bl[l]==bl[r])
            {
                bf(l,r,x);
            }
            else
            {
                bf(l,rr[bl[l]],x);
                bf(ll[bl[r]],r,x);
                for (i=bl[l]+1;i<bl[r];++i)
                {
                    tag[i]+=x;
                }
            }
        }
        else
        {
            if (l/B==r/B)
            {
                cout<<bq(l,r,x)<<endl;
            }
            else
            {
                ans=bq(l,rr[bl[l]],x)+bq(ll[bl[r]],r,x);
                for (i=bl[l]+1;i<bl[r];++i)
                {
                    a[N-1]=x-tag[i];
                    ans+=upper_bound(b+ll[i],b+rr[i]+1,N-1,cmp)-b-ll[i];
                }
                cout<<ans<<endl;
            }
        }
    }

    return 0;
}

bool cmp(int x,int y)
{
    return a[x]>a[y];
}

void bf(int l,int r,int x)
{
    for (int i=l;i<=r;++i)
    {
        a[i]+=x;
    }
    sort(b+ll[bl[l]],b+rr[bl[l]]+1,cmp);
}

int bq(int l,int r,int x)
{
    int i,out=0;
    for (i=l;i<=r;++i)
    {
        out+=(a[i]>=x);
    }
    return out;
}

by cecilia_sankta @ 2018-09-29 14:13:33

反正Orz就对了


by ___new2zy___ @ 2018-09-29 14:33:38

ORZ就对了


by 皎月半洒花 @ 2018-09-29 16:49:33

@ouuan 233

我觉得关于O2这方面,优化等级越高,对代码的要求就越严格。换句话说就是,你在O1时代码的不严谨可能导致你程序的出错。大体就体现在这个内存的声明里面,O2中有好多针对内存包括寄存器的限制。

emmm至于这个题而言,我觉得有可能是你的程序执行中内存边界的问题。你在访问所分的块或者执行某些操作时会导致你的越界,而O2对这方面的要求是比较严格的。

233我扯这么多是因为我对这方面比较感兴趣……

最后再引用一下大佬博客里的一些东西,或许会有帮助:

编译器优化级别2(与内存&寄存器相关的) (1)-fforce-mem: 这种优化在任何指令使用变量前, 强制把存放再内存位置中的所有变量都复制到寄存器中。 对于只涉及单一指令的变量, 这样也许不会有很大的优化效果. 但是对于在很多指令(必须数学操作)中都涉及到的变量来说, 这会时很显著的优化, 因为和访问内存中的值相比 ,处理器访问寄存器中的值要快的多。

(7)-fdelete-null-pointer-checks: 这种优化技术扫描生成的汇编语言代码, 查找检查空指针的代码。

(15)-fstrict-aliasing: 这种技术强制实行高级语言的严格变量规则。 对于c和c++程序来说, 它确保不在数据类型之间共享变量. 例如, 整数变量不和单精度浮点变量使用相同的内存位置。

(17)-falign-functions:这个选项用于使函数对准内存中特定边界的开始位置。大多数处理器按照页面读取内存,并且确保全部函数代码位于单一内存页面内, 就不需要叫化代码所需的页面。

总之呢,应该是代码的不规范导致的。

哎呀,答这么多是因为窝觉得楼主这么认真的研究,我很佩服楼主的执着精神啊233

其实就是闲的


by ouuan @ 2018-09-29 17:40:59

@皎月半洒花 感谢Orz

我又仔细检查了一下,发现虽然rr[bl[n]]在最后被设为n,在初始化排序的时候还是越界了...改成下面这样就不会出现1000010 998 O2 WA80了

for (i=1;i<bl[n];++i)
{
    ll[i]=i*B-B+1;
    rr[i]=i*B;
    sort(b+ll[i],b+rr[i]+1,cmp);
}

ll[bl[n]]=bl[n]*B-B+1;
rr[bl[n]]=n;
sort(b+ll[bl[n]],b+rr[bl[n]]+1,cmp);

然而分块大小为1000时的无论是否开O2都会WA使用这种方式未得到解决..


by ouuan @ 2018-09-29 17:48:18

@皎月半洒花 现在解决了...

我第一次写的时候分块方式和现在略有不同,然后改代码的时候忘记把if (l/B==r/B)改掉了...改成if (bl[l]==bl[r])就ok了


by 星小雨 @ 2018-09-29 19:36:21

@ouuan 看起来我没说错就是越界了啊。。


by ouuan @ 2018-09-29 20:29:30

@星小雨 我之前说的不是反问句..可能语气有点小问题QAQ


上一页 |