QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#1294#826983#9774. Same Sumship2077huaxiamengjinSuccess!2024-12-22 18:12:532024-12-22 18:12:54

詳細信息

Extra Test:

Time Limit Exceeded

input:

200000 200000
35280 79907 126669 20853 5904 26379 111996 27020 18853 26339 114117 61762 71944 178249 49282 168970 48909 144170 167054 141186 101956 170933 21110 114294 54060 111728 170297 181925 151353 110394 82900 20420 152744 62885 13685 141356 57025 157555 105400 142344 80761 70770 240 137884 196...

output:


result:


ID题目提交者结果用时内存语言文件大小提交时间测评时间
#826983#9774. Same SumhuaxiamengjinTL 1760ms16412kbC++143.2kb2024-12-22 17:54:382024-12-22 18:26:06

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=350;
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";
        }
    }
}