玄学问题（关于long long和__int128）结果不一样
- 板块P3384 【模板】重链剖分/树链剖分
- 楼主expnoi
- 当前回复4
- 已保存回复4
- 发布时间2023/1/27 02:24
- 上次更新2023/10/24 02:59:14
查看原帖
被骇客银狼阻止的越权访问保存失败
玄学问题（关于long long和__int128）结果不一样
__int128版本，只有10分，但是一错误数据点下载后在洛谷IDE评测同答案文件完全相同。
#include<bits/stdc++.h>
#define int __int128
using namespace std;
inline int read()
{
int s=0,w=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')
w=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
s=(s<<3)+(s<<1)+(c^48);
c=getchar();
}
return s*w;
}
inline void print(int x)
{
if(x<0)putchar('-'),x=-x;
if(x>=10)print(x/10);
putchar(x%10+'0');
return;
}
struct node
{
int v,next;
}e[200010];
struct edge
{
int l,r,sum,len,lazy;
}C[400010];
int n,m,r,p,a[100010],eid=1,head[100010],son[100010],f[100010],id[100010],w[100010],si[100010],top[100010],dep[100010],tot;
inline void insert(int u,int v)
{
e[eid].v=v;
e[eid].next=head[u];
head[u]=eid++;
}
inline void dfs(int u,int fa)
{
int ma=0;
si[u]=1;
f[u]=fa;
dep[u]=dep[fa]+1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa)continue;
dfs(v,u);
si[u]+=si[v];
if(si[v]>ma)son[u]=v;
}
}
inline void dfs1(int u,int Top)
{
id[u]=++tot;
w[tot]=a[u];
top[u]=Top;
if(!son[u])return;
dfs1(son[u],Top);
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==f[u]||v==son[u])continue;
dfs1(v,v);
}
}
inline void pushdown(int id)
{
C[id<<1].lazy+=C[id].lazy;
C[id<<1|1].lazy+=C[id].lazy;
C[id<<1].sum+=C[id<<1].len*C[id].lazy;
C[id<<1|1].sum+=C[id<<1|1].len*C[id].lazy;
C[id].lazy=0;
C[id<<1].lazy%=p;
C[id<<1|1].lazy%=p;
C[id<<1].sum%=p;
C[id<<1|1].sum%=p;
}
inline void build(int id,int l,int r)
{
C[id].l=l;
C[id].r=r;
C[id].len=r-l+1;
if(l==r)
{
C[id].sum=w[l];
return;
}
int mid=l+r>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
C[id].sum=C[id<<1].sum+C[id<<1|1].sum;
C[id].sum%=p;
}
inline void update(int id,int x,int y,int v)
{
if(x<=C[id].l&&C[id].r<=y)
{
C[id].sum+=v*C[id].len;
C[id].lazy+=v;
C[id].sum%=p;
C[id].lazy%=p;
return;
}
pushdown(id);
int mid=C[id].l+C[id].r>>1;
if(x<=mid)update(id<<1,x,y,v);
if(y>mid)update(id<<1|1,x,y,v);
C[id].sum=C[id<<1].sum+C[id<<1|1].sum;
C[id].sum%=p;
}
inline int query(int id,int x,int y)
{
if(x<=C[id].l&&C[id].r<=y)
{
return C[id].sum;
}
pushdown(id);
int mid=C[id].l+C[id].r>>1,sum=0;
if(x<=mid)sum+=query(id<<1,x,y);
if(y>mid)sum+=query(id<<1|1,x,y);
return sum%p;
}
inline void update1(int a,int b,int v)
{
while(top[a]!=top[b])
{
if(dep[top[a]]<dep[top[b]])swap(a,b);
update(1,id[top[a]],id[a],v);
a=f[top[a]];
}
if(dep[a]>dep[b])swap(a,b);
update(1,id[a],id[b],v);
}
inline int query1(int a,int b)
{
int res=0;
while(top[a]!=top[b])
{
if(dep[top[a]]<dep[top[b]])swap(a,b);
res+=query(1,id[top[a]],id[a]);
res%=p;
a=f[top[a]];
}
if(dep[a]>dep[b])swap(a,b);
res+=query(1,id[a],id[b]);
return res%p;
}
signed main()
{
n=read();
m=read();
r=read();
p=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
insert(u,v);
insert(v,u);
}
dfs(r,0);
dfs1(r,r);
build(1,1,n);
while(m--)
{
int op=read(),x,y,z;
if(op==1)
{
x=read();
y=read();
z=read();
update1(x,y,z);
}
if(op==2)
{
x=read();
y=read();
print(query1(x,y)%p);
puts("");
}
if(op==3)
{
x=read();
z=read();
update(1,id[x],id[x]+si[x]-1,z);
}
if(op==4)
{
x=read();
print(query(1,id[x],id[x]+si[x]-1)%p);
puts("");
}
}
}
long long版本，这一方法得到了满分。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
int s=0,w=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')
w=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
s=(s<<3)+(s<<1)+(c^48);
c=getchar();
}
return s*w;
}
inline void print(int x)
{
if(x<0)putchar('-'),x=-x;
if(x>=10)print(x/10);
putchar(x%10+'0');
return;
}
struct node
{
int v,next;
}e[200010];
struct edge
{
int l,r,sum,len,lazy;
}C[400010];
int n,m,r,p,a[100010],eid=1,head[100010],son[100010],f[100010],id[100010],w[100010],si[100010],top[100010],dep[100010],tot;
inline void insert(int u,int v)
{
e[eid].v=v;
e[eid].next=head[u];
head[u]=eid++;
}
inline void dfs(int u,int fa)
{
int ma=0;
si[u]=1;
f[u]=fa;
dep[u]=dep[fa]+1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==fa)continue;
dfs(v,u);
si[u]+=si[v];
if(si[v]>ma)son[u]=v;
}
}
inline void dfs1(int u,int Top)
{
id[u]=++tot;
w[tot]=a[u];
top[u]=Top;
if(!son[u])return;
dfs1(son[u],Top);
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(v==f[u]||v==son[u])continue;
dfs1(v,v);
}
}
inline void pushdown(int id)
{
C[id<<1].lazy+=C[id].lazy;
C[id<<1|1].lazy+=C[id].lazy;
C[id<<1].sum+=C[id<<1].len*C[id].lazy;
C[id<<1|1].sum+=C[id<<1|1].len*C[id].lazy;
C[id].lazy=0;
C[id<<1].lazy%=p;
C[id<<1|1].lazy%=p;
C[id<<1].sum%=p;
C[id<<1|1].sum%=p;
}
inline void build(int id,int l,int r)
{
C[id].l=l;
C[id].r=r;
C[id].len=r-l+1;
if(l==r)
{
C[id].sum=w[l];
return;
}
int mid=l+r>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
C[id].sum=C[id<<1].sum+C[id<<1|1].sum;
C[id].sum%=p;
}
inline void update(int id,int x,int y,int v)
{
if(x<=C[id].l&&C[id].r<=y)
{
C[id].sum+=v*C[id].len;
C[id].lazy+=v;
C[id].sum%=p;
C[id].lazy%=p;
return;
}
pushdown(id);
int mid=C[id].l+C[id].r>>1;
if(x<=mid)update(id<<1,x,y,v);
if(y>mid)update(id<<1|1,x,y,v);
C[id].sum=C[id<<1].sum+C[id<<1|1].sum;
C[id].sum%=p;
}
inline int query(int id,int x,int y)
{
if(x<=C[id].l&&C[id].r<=y)
{
return C[id].sum;
}
pushdown(id);
int mid=C[id].l+C[id].r>>1,sum=0;
if(x<=mid)sum+=query(id<<1,x,y);
if(y>mid)sum+=query(id<<1|1,x,y);
return sum%p;
}
inline void update1(int a,int b,int v)
{
while(top[a]!=top[b])
{
if(dep[top[a]]<dep[top[b]])swap(a,b);
update(1,id[top[a]],id[a],v);
a=f[top[a]];
}
if(dep[a]>dep[b])swap(a,b);
update(1,id[a],id[b],v);
}
inline int query1(int a,int b)
{
int res=0;
while(top[a]!=top[b])
{
if(dep[top[a]]<dep[top[b]])swap(a,b);
res+=query(1,id[top[a]],id[a]);
res%=p;
a=f[top[a]];
}
if(dep[a]>dep[b])swap(a,b);
res+=query(1,id[a],id[b]);
return res%p;
}
signed main()
{
n=read();
m=read();
r=read();
p=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
insert(u,v);
insert(v,u);
}
dfs(r,0);
dfs1(r,r);
build(1,1,n);
while(m--)
{
int op=read(),x,y,z;
if(op==1)
{
x=read();
y=read();
z=read();
update1(x,y,z);
}
if(op==2)
{
x=read();
y=read();
print(query1(x,y)%p);
puts("");
}
if(op==3)
{
x=read();
z=read();
update(1,id[x],id[x]+si[x]-1,z);
}
if(op==4)
{
x=read();
print(query(1,id[x],id[x]+si[x]-1)%p);
puts("");
}
}
}
所以这个问题很玄学，求助各位大佬求原因。
加载中...