这是 UB 吗？
查看原帖
这是 UB 吗？
678881
Vocaloid世末歌者楼主2024/8/17 07:23
#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL int
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 LL
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
    x=0;
    i128 f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	x*=f;
}
void write(i128 x)
{
    if(x<0)
    {
    	putchar('-');
    	x=-x;
    }
    if(x>9)write(x/10);
    putchar((x%10)^48);
}
LL n,m;
LL L[5010],R[5010],wch[5010];
struct que
{
	LL op,x,y,len,dir,sum;
}q[100010];
struct szsz
{
	LL cc[20010],p[110];
	void clr()
	{
		rep(i,1,2*n,1)cc[i]=0;
		rep(i,1,wch[2*n],1)p[i]=0;
	}
	void add(LL x,LL v)
	{
		cc[x]+=v;
		p[wch[x]]+=v;
	}
	LL qu(LL x)
	{
		LL op=wch[x],sum=0;
		repn(i,1,op,1)
		{
			sum+=p[i];
		}
		rep(i,L[op],x,1)sum+=cc[i];
		return sum;
	}
}cgc1[5010],cgc2[110],g[110];
void sol(LL x)
{
	rep(i,1,n,1)
	{
		cgc1[i].clr();
	}
	rep(i,1,wch[n],1)
    {
        cgc2[i].clr();
        g[i].clr();
    }
    rep(i,1,m,1)
	{
		if(q[i].dir&&q[i].dir!=x)continue;
		if(q[i].op==1)
		{
			LL l=q[i].x-q[i].len,r=q[i].x,wchl=wch[l],wchr=wch[r];
			if(wchl==wchr)
			{
				rep(j,l,r,1)
				{
					cgc1[j].add(q[i].y,1);
					cgc1[j].add(q[i].y+(j-l+1),-1);
				}
			}
			else
			{
				LL p=q[i].y-l+n;
				rep(j,l,R[wchl],1)
				{
					cgc1[j].add(q[i].y,1);
					cgc1[j].add(q[i].y+(j-l+1),-1);
				}
				repn(j,wchl+1,wchr,1)
				{
					g[j].add(p+1,-1);
					cgc2[j].add(q[i].y,1);
				}
				rep(j,L[wchr],r,1)
				{
					cgc1[j].add(q[i].y,1);
					cgc1[j].add(q[i].y+(j-l+1),-1);
				}
			}
		}
		else
		{
			q[i].sum+=cgc1[q[i].x].qu(q[i].y);
			q[i].sum+=g[wch[q[i].x]].qu(q[i].y-q[i].x+n);
			q[i].sum+=cgc2[wch[q[i].x]].qu(q[i].y);
		}
	}
}
int main()
{
//	freopen("triangle.in","r",stdin);
//	freopen("triangle.out","w",stdout);
	cin>>n>>m;
    LL blo=sqrt(n);
    rep(i,1,2*n,1)
    {
    	wch[i]=(i-1)/blo+1;
    	if(wch[i]!=wch[i-1])
    	{
    		L[wch[i]]=i;
    		R[wch[i-1]]=i-1;
		}
	}
	R[wch[2*n]]=2*n;
	rep(i,1,m,1)
	{
		cin>>q[i].op;
		if(q[i].op==1)
		{
			cin>>q[i].dir>>q[i].x>>q[i].y>>q[i].len;
		}
		else
		{
			cin>>q[i].x>>q[i].y;
		}
	}
	sol(3);
	rep(i,1,m,1)
	{
		q[i].x=n-q[i].x+1;
	}
	sol(1);
	rep(i,1,m,1)
	{
		q[i].y=n-q[i].y+1;
	}
	sol(2);
	rep(i,1,m,1)
	{
		q[i].x=n-q[i].x+1;
	}
	sol(4);
	rep(i,1,m,1)
	{
		if(q[i].op==2)
		{
			cout<<q[i].sum<<endl;
		}
	}
    return 0;
}

这是我最开始的代码，WA 20 pts。（站外题）

#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL int
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 LL
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
    x=0;
    i128 f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	x*=f;
}
void write(i128 x)
{
    if(x<0)
    {
    	putchar('-');
    	x=-x;
    }
    if(x>9)write(x/10);
    putchar((x%10)^48);
}
LL n,m;
struct que
{
	LL op,x,y,len,dir,sum;
}q[100010];
LL L[5010],R[5010],wch[5010];
struct szsz
{
	LL cc[20010],p[110];
	void clr()
	{
		rep(i,1,2*n,1)cc[i]=0;
		rep(i,1,wch[2*n],1)p[i]=0;
	}
	void add(LL x,LL v)
	{
		cc[x]+=v;
		p[wch[x]]+=v;
	}
	LL qu(LL x)
	{
		LL op=wch[x],sum=0;
		repn(i,1,op,1)
		{
			sum+=p[i];
		}
		rep(i,L[op],x,1)sum+=cc[i];
		return sum;
	}
}cgc1[5010],cgc2[110],g[110];
void sol(LL x)
{
	rep(i,1,n,1)
	{
		cgc1[i].clr();
	}
	rep(i,1,wch[n],1)
    {
        cgc2[i].clr();
        g[i].clr();
    }
    rep(i,1,m,1)
	{
		if(q[i].dir&&q[i].dir!=x)continue;
		if(q[i].op==1)
		{
			LL l=q[i].x-q[i].len,r=q[i].x,wchl=wch[l],wchr=wch[r];
			if(wchl==wchr)
			{
				rep(j,l,r,1)
				{
					cgc1[j].add(q[i].y,1);
					cgc1[j].add(q[i].y+(j-l+1),-1);
				}
			}
			else
			{
				LL p=q[i].y-l+n;
				rep(j,l,R[wchl],1)
				{
					cgc1[j].add(q[i].y,1);
					cgc1[j].add(q[i].y+(j-l+1),-1);
				}
				repn(j,wchl+1,wchr,1)
				{
					g[j].add(p+1,-1);
					cgc2[j].add(q[i].y,1);
				}
				rep(j,L[wchr],r,1)
				{
					cgc1[j].add(q[i].y,1);
					cgc1[j].add(q[i].y+(j-l+1),-1);
				}
			}
		}
		else
		{
			q[i].sum+=cgc1[q[i].x].qu(q[i].y);
			q[i].sum+=g[wch[q[i].x]].qu(q[i].y-q[i].x+n);
			q[i].sum+=cgc2[wch[q[i].x]].qu(q[i].y);
		}
	}
}
int main()
{
//	freopen("triangle.in","r",stdin);
//	freopen("triangle.out","w",stdout);
	cin>>n>>m;
    LL blo=sqrt(n);
    rep(i,1,2*n,1)
    {
    	wch[i]=(i-1)/blo+1;
    	if(wch[i]!=wch[i-1])
    	{
    		L[wch[i]]=i;
    		R[wch[i-1]]=i-1;
		}
	}
	R[wch[2*n]]=2*n;
	rep(i,1,m,1)
	{
		cin>>q[i].op;
		if(q[i].op==1)
		{
			cin>>q[i].dir>>q[i].x>>q[i].y>>q[i].len;
		}
		else
		{
			cin>>q[i].x>>q[i].y;
		}
	}
	sol(3);
	rep(i,1,m,1)
	{
		q[i].x=n-q[i].x+1;
	}
	sol(1);
	rep(i,1,m,1)
	{
		q[i].y=n-q[i].y+1;
	}
	sol(2);
	rep(i,1,m,1)
	{
		q[i].x=n-q[i].x+1;
	}
	sol(4);
	rep(i,1,m,1)
	{
		if(q[i].op==2)
		{
			cout<<q[i].sum<<endl;
		}
	}
    return 0;
}

这是我后来 AC 的代码。

中间只是换了几个数组的定义位置。

求助这是 UB 吗

2024/8/17 07:23