如题,现在我有两个序列长均为 n 的序列:a,b。其中,a 中的元素和 b 中的元素均为正整数。
那么问题是:如果存在以下关系式:
i=1∑nai=i=1∑nbii=1∏nai=i=1∏nbi是否能够重排 a,使得 a=b?
我在考场上用线段树维护以上做法,被第 55 个点卡掉了,最后加了一个异或相等才卡过去。
这是加了异或相等的代码,大佬帮忙看看,是我加、乘写丑了,还是结论本身就有问题?
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
const int MAXN=2e5+10;
#define ls rt<<1
#define rs (rt<<1)|1
#define lson l,mid,rt<<1
#define rson mid+1,r,(rt<<1)|1
struct SegmentTree{
long long sum[MAXN<<2],mul[MAXN<<2],Xor[MAXN<<2];
long long a[MAXN];
inline void pushup(int rt){
sum[rt]=sum[ls]+sum[rs];
mul[rt]=mul[ls]*mul[rs]%mod;
Xor[rt]=Xor[ls]^Xor[rs];
}
void build(int l,int r,int rt){
if(l==r){
sum[rt]=a[l];
mul[rt]=a[r];
Xor[rt]=a[l];
return;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);
}
long long query(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
return sum[rt];
}
int mid=(l+r)>>1;
long long res=0;
if(L<=mid){
res+=query(L,R,lson);
}
if(R>mid){
res+=query(L,R,rson);
}
return res;
}
long long Query(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
return mul[rt];
}
int mid=(l+r)>>1;
long long res=1ll;
if(L<=mid){
res*=Query(L,R,lson);
}
if(R>mid){
res*=Query(L,R,rson);
}
res%=mod;
return res;
}
long long querX(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R){
return Xor[rt];
}
int mid=(l+r)>>1;
long long res=0ll;
if(L<=mid){
res^=querX(L,R,lson);
}
if(R>mid){
res^=querX(L,R,rson);
}
return res;
}
}Ta,Tb;
int n,Q;
long long a[MAXN],b[MAXN];
int main(){
scanf("%d%d",&n,&Q);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;++i){
scanf("%lld",&b[i]);
}
for(int i=1;i<=n;++i){
Ta.a[i]=a[i];
Tb.a[i]=b[i];
}
Ta.build(1,n,1);
Tb.build(1,n,1);
int l,r,L,R;
while(Q--){
scanf("%d%d%d%d",&l,&r,&L,&R);
if(r-l!=R-L){
printf("No");
}
else{
if(Ta.query(l,r,1,n,1)==Tb.query(L,R,1,n,1)&&Ta.Query(l,r,1,n,1)==Tb.Query(L,R,1,n,1)&&Ta.querX(l,r,1,n,1)==Tb.querX(L,R,1,n,1)){
printf("Yes");
}
else{
printf("No");
}
}
putchar('\n');
}
return 0;
}