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