QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#835868 | #9774. Same Sum | nb_jzy | RE | 0ms | 7704kb | C++20 | 2.6kb | 2024-12-28 15:06:56 | 2024-12-28 15:06:56 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;
const int mod=1000000000177,P=19260817,maxn=5e5+5,inf=1e12;
int n,q,a[maxn],t[maxn<<2][2],la[maxn<<2],sum[maxn<<2];
struct node{
int sum,p1,p2;
};
int poww(__int128 x,int y){
__int128 res=1;
while(y>0){
if(y&1){
res=res*x%mod;
}
x=x*x%mod;
y>>=1;
}
return res;
}
int cheng(__int128 x,__int128 y){
x*=y;
x%=mod;
return x;
}
void shutdown(int p,int l,int r){
if(la[p]>0){
la[ls(p)]+=la[p],la[rs(p)]+=la[p];
int mid=(l+r)>>1;
sum[ls(p)]+=la[p]*(mid-l+1),sum[rs(p)]+=la[p]*(r-mid);
int mi=poww(P,la[p]);
t[ls(p)][0]=cheng(t[ls(p)][0],mi);t[rs(p)][0]=cheng(t[rs(p)][0],mi);
mi=poww(mi,mod-2);
t[ls(p)][1]=cheng(t[ls(p)][1],mi),t[rs(p)][1]=cheng(t[rs(p)][1],mi);
la[p]=0;
}
}
void build(int p,int l,int r){
if(l==r){
t[p][0]=poww(P,a[l]);t[p][1]=poww(P,inf-a[l]);sum[p]=a[l];
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
t[p][0]=(t[ls(p)][0]+t[rs(p)][0])%mod;
t[p][1]=(t[ls(p)][1]+t[rs(p)][1])%mod;
sum[p]=sum[ls(p)]+sum[rs(p)];
}
void add(int p,int l,int r,int x,int y,int z){
if(l>=x&&r<=y){
la[p]+=z;
int mi=poww(P,z);
t[p][0]=cheng(t[p][0],mi);t[p][1]=cheng(t[p][1],poww(mi,mod-2));
sum[p]+=(r-l+1)*z;
return;
}
shutdown(p,l,r);
int mid=(l+r)>>1;
if(x<=mid&&y>=l){
add(ls(p),l,mid,x,y,z);
}
if(y>mid&&x<=r){
add(rs(p),mid+1,r,x,y,z);
}
t[p][0]=(t[ls(p)][0]+t[rs(p)][0])%mod;
t[p][1]=(t[ls(p)][1]+t[rs(p)][1])%mod;
sum[p]=sum[ls(p)]+sum[rs(p)];
}
node query(int p,int l,int r,int x,int y){
if(l>=x&&r<=y){
return {sum[p],t[p][0],t[p][1]};
}
shutdown(p,l,r);
int mid=(l+r)>>1;
node res={0,0,0},ll;
if(x<=mid&&y>=l){
ll=query(ls(p),l,mid,x,y);
res.sum+=ll.sum,res.p1+=ll.p1,res.p2+=ll.p2;
}
if(y>mid&&x<=r){
ll=query(rs(p),mid+1,r,x,y);
res.sum+=ll.sum,res.p1+=ll.p1,res.p2+=ll.p2;
}
res.p1%=mod,res.p2%=mod;
return res;
}
signed main(){
// freopen("1.in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
int cnt=0;
while(q--){
int op,l,r,v;
cin>>op;
if(op==1){
cin>>l>>r>>v;
add(1,1,n,l,r,v);
}
else{
cin>>l>>r;
cnt++;
node res=query(1,1,n,l,r);
if(res.sum%((r-l+1)/2)==0){
int del=res.sum/((r-l+1)/2);
del=poww(poww(P,inf-del),mod-2);
if(cheng(res.p2,del)==res.p1){
if(cnt==464){
return -1;
}
cout<<"YES\n";
}
else{
cout<<"NO\n";
}
}
else{
cout<<"NO\n";
}
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 7704kb
input:
8 4 1 2 3 4 5 6 7 8 2 1 8 1 1 4 4 2 1 6 2 1 8
output:
YES NO YES
result:
ok 3 token(s): yes count is 2, no count is 1
Test #2:
score: -100
Runtime Error
input:
200000 200000 0 0 0 1 1 0 2 1 1 2 0 1 0 0 0 2 1 0 1 2 2 1 2 1 2 0 0 2 1 2 1 0 0 2 0 2 1 1 1 2 0 0 0 0 2 0 1 0 0 2 2 1 1 0 0 2 1 0 2 0 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 0 1 0 1 1 0 2 1 2 0 2 2 1 1 2 1 2 2 0 0 1 2 0 0 2 2 0 1 2 2 0 0 1 2 1 2 0 2 0 0 2 0 2 1 0 1 1 1 1 2 1 2 0 1 2 1 0 2 1 0 1 1 2 2 0 1 ...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...