关于 O3 优化
查看原帖
关于 O3 优化
602803
_qingshu_楼主2024/2/26 19:28

这一份代码在不开 O3 的情况下会 WA 在 #10 的第 5k 多行,但是手开了 O3 就可以通过了,有没有大佬能解释一下?

#include<bits/stdc++.h>
#pragma GCC optimize("-O3")
using namespace std;
int n,m,num,fa[5200010],op,l,r,x;
int a[5200010],block[5200010],siz[400][100010],last[400][100010],maxx[5200010],pos[5200010],lz[5200010];
inline int find(int id){
    if(fa[id]!=id){
		fa[id]=find(fa[id]);
	}
    return fa[id];
}
inline void pushdown(int id){
    for(int i=(id-1)*num+1;i<=min(n,id*num);i++){
        a[i]=pos[find(i)];
        last[id][a[i]]=siz[id][a[i]]=0;
        a[i]-=lz[id];
    }
    for(int i=(id-1)*num+1;i<=min(n,id*num);i++)fa[i]=0;
    lz[id]=0;
}
inline void update(int i){
	maxx[i]=0;
    for(int j=(i-1)*num+1;j<=min(n,i*num);j++){
        maxx[i]=max(maxx[i],a[j]);
        if(last[i][a[j]])fa[j]=last[i][a[j]];
        else{
        	pos[j]=a[j];
        	last[i][a[j]]=j;
        	fa[j]=j;
		}
        siz[i][a[j]]++;
    }
}
inline void merge(int id,int a,int b){
    if(last[id][b])fa[last[id][a]]=last[id][b];
    else{
        last[id][b]=last[id][a];
        pos[last[id][a]]=b;
    }
    siz[id][b]+=siz[id][a];
    siz[id][a]=last[id][a]=0;
}
inline void fixlz(int id,int X){
    if((X<<1)<=maxx[id]-lz[id]){
        for(int i=lz[id]+1;i<=lz[id]+X;i++){
            if(last[id][i]){
            	merge(id,i,i+X);
			}
        }
        lz[id]+=X;
    }
    else{
        for(int i=maxx[id];i>lz[id]+X;i--){
            if(last[id][i]){
                merge(id,i,i-X);
            }
        }
        maxx[id]=min(maxx[id],lz[id]+X);
    }
}
inline void modify(int lef,int rig,int X){
    pushdown(block[lef]);
    for(int i=lef;i<=min(rig,block[lef]*num);i++){
        if(a[i]>X)a[i]-=X;
    }
    update(block[lef]);
    if(block[lef]!=block[rig]){
		pushdown(block[rig]);
        for(int i=(block[rig]-1)*num+1;i<=rig;i++){
            if(a[i]>X)a[i]-=X;
        }
        update(block[rig]);
    }
    for(int i=block[lef]+1;i<block[rig];i++){
        fixlz(i,X);
    }
}
inline void query(int lef,int rig,int X){
    long long ans=0;
    for(int i=lef;i<=min(rig,block[lef]*num);i++){
        if(pos[find(i)]-lz[block[lef]]==X)ans++;
    }
    if(block[lef]!=block[rig]){
        for(int i=(block[rig]-1)*num+1;i<=rig;i++){
            if(pos[find(i)]-lz[block[rig]]==X)ans++;
        }
    }
    for(int i=block[lef]+1;i<block[rig];i++){
    	if(X+lz[i]>100000)continue;
       	ans+=siz[i][X+lz[i]];
    }
	cout<<ans<<"\n";
}
signed main(){
    cin>>n>>m;num=sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        block[i]=(i-1)/num+1;
    }
    for(int i=1;i<=block[n];i++){
        update(i);
    }
    while(m--){
        cin>>op>>l>>r>>x;
        if(op==1)modify(l,r,x);
        else query(l,r,x);
    } 
}
2024/2/26 19:28
加载中...