QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#1300#826993#9774. Same Sumship2077huaxiamengjinSuccess!2024-12-23 09:41:052024-12-23 09:41:05

詳細信息

Extra Test:

Wrong Answer
time: 0ms
memory: 16012kb

input:

92 1
0 27835 7771 100000 0 39328 43596 100000 0 45543 1804 100000 0 15065 33189 100000 0 34865 33086 100000 0 31953 49149 100000 0 14280 22015 100000 0 19244 49807 100000 0 35097 26681 100000 0 971 2303 100000 0 32040 17625 100000 0 8393 23792 100000 0 9022 30450 100000 0 34572 13986 100000 0 8393 2...

output:

Yes

result:

wrong answer expected NO, found YES [1st token]

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#826993#9774. Same SumhuaxiamengjinWA 1660ms16748kbC++143.2kb2024-12-22 18:13:152024-12-23 09:46:26

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int NN=998244353;
int mi(int x,int y){
    int sum=1;
    for (;y;y>>=1,x=x*x%NN)
    if(y&1)sum=sum*x%NN;
    return sum;
}
int len=300;
const int bs=1233;
int a[200200],b[200200],c[200200];
int tag[200200],s1[200200],s2[200200];
int mn[200200],mx[200200],col[200200];
int ls[200200],rs[200200];
int n,q;
const int bss=mi(bs,NN-2);
void push(int p,int l,int r,int v){
    // cout<<p<<" "<<l<<" "<<r<<" "<<v<<"\n";
    int ll=ls[p],rr=rs[p];
    int tmp=mi(bs,tag[p]);
    for (int i=ll;i<=rr;i++)a[i]=a[i]*tmp%NN;
    tmp=mi(bs,v);
    for (int i=l;i<=r;i++)a[i]=a[i]*tmp%NN;
    s1[p]=0;
    for (int i=ll;i<=rr;i++)s1[p]=(s1[p]+a[i])%NN;
    tmp=mi(bss,tag[p]);
    for (int i=ll;i<=rr;i++)b[i]=b[i]*tmp%NN;
    tmp=mi(bss,v);
    for (int i=l;i<=r;i++)b[i]=b[i]*tmp%NN;
    s2[p]=0;
    for (int i=ll;i<=rr;i++)s2[p]=(s2[p]+b[i])%NN;
    for (int i=ll;i<=rr;i++)
    c[i]+=tag[p];
    for (int i=l;i<=r;i++)
    c[i]+=v;
// cout<<c[l]<<"~~~~~~~\n";
    mn[p]=1e15,mx[p]=0;
    for (int i=ll;i<=rr;i++)
    mn[p]=min(mn[p],c[i]),mx[p]=max(mx[p],c[i]);
    tag[p]=0;
    
}
int ss1,ss2,mxx,mnn;
void get(int p,int l,int r){
    int ll=ls[p],rr=rs[p];
    int tmp=mi(bs,tag[p]);
    for (int i=ll;i<=rr;i++)a[i]=a[i]*tmp%NN;
    tmp=mi(bss,tag[p]);
    for (int i=ll;i<=rr;i++)b[i]=b[i]*tmp%NN;
    for (int i=ll;i<=rr;i++)c[i]+=tag[p];
    for(int i=l;i<=r;i++)
    ss1=(ss1+a[i])%NN,ss2=(ss2+b[i])%NN;
    for (int i=l;i<=r;i++)
    mxx=max(mxx,c[i]),mnn=min(mnn,c[i]);
    tag[p]=0;
}
signed main(){ 
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for (int i=1,x;i<=n;i++)
    cin>>x,a[i]=mi(bs,x),b[i]=mi(bss,x),c[i]=x;
    int tot=0;
    for (int l=1;;l+=len){
        int r=min(n,l+len-1);
        tot++;ls[tot]=l;rs[tot]=r;
        mn[tot]=1e15,mx[tot]=0;
        for (int i=l;i<=r;i++)
        col[i]=tot,s1[tot]=(s1[tot]+a[i])%NN
    ,s2[tot]=(s2[tot]+b[i])%NN,
    mn[tot]=min(mn[tot],c[i]),
    mx[tot]=max(mx[tot],c[i]);
        if(r==n)break;
    }
    int op,l,r,v;
    while(q--){
        cin>>op;
        if(op==1){
            cin>>l>>r>>v;
            int ll=col[l],rr=col[r];
            if(ll==rr){
                push(ll,l,r,v);
                continue;
            }
            push(ll,l,rs[ll],v);
            push(rr,ls[rr],r,v);
            int tmp=mi(bs,v),tmp2=mi(bss,v);
            for (int i=ll+1;i<rr;i++)
            tag[i]+=v,s1[i]=s1[i]*tmp%NN,s2[i]=s2[i]*tmp2%NN
        ,mn[i]+=v,mx[i]+=v;
        }else{
            cin>>l>>r;
            int ll=col[l],rr=col[r];
            ss1=0,ss2=0;mnn=1e15,mxx=0;
            if(ll==rr){
                get(ll,l,r);
                if(ss2*mi(bs,mxx+mnn)%NN==ss1)cout<<"Yes\n";
                else cout<<"No\n";
                continue;
            }
            get(ll,l,rs[ll]);
            get(rr,ls[rr],r);
            for (int i=ll+1;i<rr;i++)
            ss1=(ss1+s1[i])%NN,ss2=(ss2+s2[i])%NN,
            mxx=max(mxx,mx[i]),mnn=min(mnn,mn[i]);
            // cout<<mnn<<" "<<mxx<<"!!!!\n";
            if(ss2*mi(bs,mxx+mnn)%NN==ss1)cout<<"Yes\n";
            else cout<<"No\n";
        }
    }
}