QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#1442 | #852449 | #9774. Same Sum | Wanye | Wanye | Failed. | 2025-01-11 11:58:26 | 2025-01-11 11:58:26 |
詳細信息
Extra Test:
Accepted
time: 0ms
memory: 15912kb
input:
4 1 4 2 3 1 2 1 4
output:
YES
result:
ok YES
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#852449 | #9774. Same Sum | Wanye | WA | 770ms | 78108kb | C++14 | 3.9kb | 2025-01-11 11:55:51 | 2025-01-11 12:03:36 |
answer
#include<bits/stdc++.h>
#define ll __int128
#define N 200005
using namespace std;
inline char nc(){
static char buf[1000000],*p=buf,*q=buf;
return p==q&&(q=(p=buf)+fread(buf,1,1000000,stdin),p==q)?EOF:*p++;
}
inline ll read(){
ll res = 0,w = 1;
char c = nc();
while(c<'0'||c>'9')w=(c=='-'?-1:w),c=nc();
while(c<='9'&&c>='0')res=res*10+c-'0',c=nc();
return res*w;
}
char obuf[1<<21],*p3=obuf;
inline void pc(char c){
p3-obuf<=(1<<20)?(*p3++=c):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=c);
}
inline void write(ll x){
if(x<0) pc('-'),x=-x;
if(x>9) write(x/10);
pc(x%10+'0');
}
struct node{ll s1,s2,s3,mi,ma;}tr[N<<2];
bool operator==(const node&a,const node&b){return a.s1==b.s1&&a.s2==b.s2&&a.s3==b.s3&&a.mi==b.mi&&a.ma==b.ma;}
node operator+(const node&a,const node&b){return (node){a.s1+b.s1,a.s2+b.s2,a.s3+b.s3,min(a.mi,b.mi),max(a.ma,b.ma)};}
ll n,q,i,a[N],opt,l,r,c,tag1[N<<2],tag2[N<<2],b[N],top;
inline void pushup(ll p){
tr[p] = tr[2*p]+tr[2*p+1];
}
inline void pushtag(ll p,ll s,ll t,ll t1,ll t2){
if(t1==-1) swap(tr[p].mi,tr[p].ma),tr[p].mi*=-1,tr[p].ma*=-1;
tr[p].mi += t2,tr[p].ma += t2;
tag1[p] *= t1,tag2[p] *= t1,tr[p].s1 *= t1,tr[p].s2 *= t1*t1,tr[p].s3 *= t1*t1*t1;
tag2[p] += t2,tr[p].s3 += tr[p].s2*3*t2+tr[p].s1*3*t2*t2+(t-s+1)*t2*t2*t2,tr[p].s2 += 2*tr[p].s1*t2+(t-s+1)*t2*t2,tr[p].s1 += (t-s+1)*t2;
}
inline void pushdown(ll p,ll s,ll t){
pushtag(2*p,s,(s+t)/2,tag1[p],tag2[p]);
pushtag(2*p+1,(s+t)/2+1,t,tag1[p],tag2[p]);
tag1[p] = 1,tag2[p] = 0;
}
inline void build(ll s,ll t,ll p){
tag1[p] = 1,tag2[p] = 0;
if(s==t){
tr[p].s1 = a[s],tr[p].s2 = a[s]*a[s],tr[p].s3 = a[s]*a[s]*a[s],tr[p].mi = tr[p].ma = a[s];
return ;
}
build(s,(s+t)/2,2*p),build((s+t)/2+1,t,2*p+1);
pushup(p);
}
inline void add(ll l,ll r,ll c,ll s,ll t,ll p){
if(l<=s&&t<=r) return pushtag(p,s,t,1,c);
if(tag1[p]!=1||tag2[p]) pushdown(p,s,t);
if(l<=(s+t)/2) add(l,r,c,s,(s+t)/2,2*p);
if(r>(s+t)/2) add(l,r,c,(s+t)/2+1,t,2*p+1);
pushup(p);
}
inline void change(ll l,ll r,ll s,ll t,ll p){
if(l<=s&&t<=r) return pushtag(p,s,t,-1,0);
if(tag1[p]!=1||tag2[p]) pushdown(p,s,t);
if(l<=(s+t)/2) change(l,r,s,(s+t)/2,2*p);
if(r>(s+t)/2) change(l,r,(s+t)/2+1,t,2*p+1);
pushup(p);
}
inline ll get_sum(ll l,ll r,ll s,ll t,ll p){
if(l<=s&&t<=r) return tr[p].s1;
if(tag1[p]!=1||tag2[p]) pushdown(p,s,t);
ll ans = 0;
if(l<=(s+t)/2) ans+=get_sum(l,r,s,(s+t)/2,2*p);
if(r>(s+t)/2) ans+=get_sum(l,r,(s+t)/2+1,t,2*p+1);
return ans;
}
inline node query(ll l,ll r,ll s,ll t,ll p){
if(l<=s&&t<=r) return tr[p];
if(tag1[p]!=1||tag2[p]) pushdown(p,s,t);
if(l<=(s+t)/2&&r>(s+t)/2) return query(l,r,s,(s+t)/2,2*p)+query(l,r,(s+t)/2+1,t,2*p+1);
else if(l<=(s+t)/2) return query(l,r,s,(s+t)/2,2*p);
else return query(l,r,(s+t)/2+1,t,2*p+1);
}
int main(){
n=read(),q=read();
for(i=1;i<=n;i++) a[i]=read(),a[i]+=12937817;
build(1,n,1);
ll DELTA = 0;
while(q--){
opt=read();
if(opt==1){
l = read(),r = read(),c = read();
add(l,r,c,1,n,1);
}
if(opt==2){
l = read(),r = read();
DELTA++;
if(DELTA<=1){
top = 0;
for(i=l;i<=r;i++) b[++top]=get_sum(i,i,1,n,1);
if(top%2!=0){
pc('N'),pc('O'),pc('\n');
continue;
}
ll mi = LLONG_MAX,ma = LLONG_MIN;
for(i=1;i<=top/2;i++) mi=min(mi,b[i]+b[top-i+1]),ma=max(ma,b[i]+b[top-i+1]);
if(mi==ma) pc('Y'),pc('E'),pc('S'),pc('\n');
else pc('N'),pc('O'),pc('\n');
continue;
}
ll num = get_sum(l,r,1,n,1);
if(num%((r-l+1)/2)!=0){
pc('N'),pc('O'),pc('\n');
continue;
}
ll Deltaa = num/((r-l+1)/2);
node tmp1 = query(l,r,1,n,1);
change(l,r,1,n,1),add(l,r,Deltaa,1,n,1);
node tmp2 = query(l,r,1,n,1);
add(l,r,-Deltaa,1,n,1),change(l,r,1,n,1);
if(tmp1==tmp2) pc('Y'),pc('E'),pc('S'),pc('\n');
else pc('N'),pc('O'),pc('\n');
}
}
return fwrite(obuf,p3-obuf,1,stdout),0;
}