QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1301#824482#9774. Same Sumship2077ucup-team3161Success!2024-12-23 09:43:252024-12-23 09:47:02

Details

Extra Test:

Wrong Answer
time: 0ms
memory: 32456kb

input:

520 1
0 25844 41452 100000 0 19877 6623 100000 0 27919 26550 100000 0 30876 10014 100000 0 47835 29485 100000 0 28336 14183 100000 0 3974 27287 100000 0 25618 37957 100000 0 7307 24195 100000 0 33264 11277 100000 0 28894 40741 100000 0 33536 35437 100000 0 33466 36307 100000 0 208 33816 100000 0 164...

output:

YES

result:

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

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#824482#9774. Same Sumucup-team3161#WA 549ms92884kbC++173.5kb2024-12-21 14:22:442024-12-23 09:49:08

answer

#include<bits/stdc++.h>
#define For(i,x,y) for (int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (int i=(x);i<(y);i++)
#define Dow(i,x,y) for (int i=(x);i>=(y);i--)
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PA;

inline ll read(){
    ll x;
    scanf("%lld",&x);
    return x;
}

#define int ll

const int N = 2e5+10;
int n,q,a[N];

const int base = 2333;
inline int Mod(int x,int mod){
	return x>=mod?x-mod:x;
}
inline int power(int a,ll b,int mod){
	b%=mod-1;
	int ret=1;
	for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) ret=1ll*ret*a%mod;
	return ret;
}

struct SGT{
    int mod,invb;
	ll mx[N<<2],mn[N<<2],tag[N<<2],tag1[N<<2],tag2[N<<2],s1[N<<2],s2[N<<2];
	inline void init(int _mod){
		mod=_mod;
		invb=power(base,mod-2,mod);
	}
	inline void push_up(int u){
		mx[u]=max(mx[u<<1],mx[u<<1^1]);
		mn[u]=min(mn[u<<1],mn[u<<1^1]);
		s1[u]=Mod(s1[u<<1]+s1[u<<1^1],mod);
		s2[u]=Mod(s2[u<<1]+s2[u<<1^1],mod);
	}
    inline void Build(int u,int l,int r){
		tag1[u]=1;
		tag2[u]=1;
		tag[u]=0;
        if (l==r){
			mx[u]=mn[u]=a[l];
			s1[u]=power(base,a[l],mod);
			s2[u]=power(invb,a[l],mod);
            return;
        }
        int mid=l+r>>1;
        Build(u<<1,l,mid);
        Build(u<<1^1,mid+1,r);
        push_up(u);
    }
	inline void upd(int u,ll x,ll y,ll z){
		tag[u]+=x;
		tag1[u]=1ll*tag1[u]*y%mod;
		tag2[u]=1ll*tag2[u]*z%mod;
		mn[u]+=x;
		mx[u]+=x;
		s1[u]=1ll*s1[u]*y%mod;
		s2[u]=1ll*s2[u]*z%mod;
	}
	inline void push_down(int u){
		if (!tag[u]) return;
		upd(u<<1,tag[u],tag1[u],tag2[u]);
		upd(u<<1^1,tag[u],tag1[u],tag2[u]);
		tag[u]=0;
		tag1[u]=1;
		tag2[u]=1;
	}
	inline void update(int u,int l,int r,int ql,int qr,int x,int pw1,int pw2){
		if (l>=ql&&r<=qr){
			upd(u,x,pw1,pw2);
			return;
		}
		int mid=l+r>>1;
		push_down(u);
		if (ql<=mid) update(u<<1,l,mid,ql,qr,x,pw1,pw2);
		if (qr>mid) update(u<<1^1,mid+1,r,ql,qr,x,pw1,pw2);
		push_up(u);
	}
	inline void update(int l,int r,int x){
		update(1,1,n,l,r,x,power(base,x,mod),power(invb,x,mod));
	}
	inline PA Query1(int u,int l,int r,int ql,int qr){
		if (l>=ql&&r<=qr) return mp(mn[u],mx[u]);
		int mid=l+r>>1;
		push_down(u);
		if (qr<=mid) return Query1(u<<1,l,mid,ql,qr);
		if (ql>mid) return Query1(u<<1^1,mid+1,r,ql,qr);
		auto L=Query1(u<<1,l,mid,ql,qr),R=Query1(u<<1^1,mid+1,r,ql,qr);
		return mp(min(L.fi,R.fi),max(L.se,R.se));
	}
	inline PA Query2(int u,int l,int r,int ql,int qr){
		if (l>=ql&&r<=qr) return mp(s1[u],s2[u]);
		int mid=l+r>>1;
		push_down(u);
		if (qr<=mid) return Query2(u<<1,l,mid,ql,qr);
		if (ql>mid) return Query2(u<<1^1,mid+1,r,ql,qr);
		auto L=Query2(u<<1,l,mid,ql,qr),R=Query2(u<<1^1,mid+1,r,ql,qr);
		return mp(Mod(L.fi+R.fi,mod),Mod(L.se+R.se,mod));
	}
	inline bool check(int s1,int s2,ll mn,ll mx){
		s1=1ll*s1*power(invb,mn,mod)%mod;
		s2=1ll*s2*power(base,mx,mod)%mod;
		return s1==s2;
	}
}T1,T2;

signed main(){
	//freopen("data.in","r",stdin);
	//freopen("g.out","w",stdout);
    n=read(),q=read();
    For(i,1,n) a[i]=read();
	T1.init(1e9+7);
	T2.init(1e9+9);
	T1.Build(1,1,n);
	T2.Build(1,1,n);
	while (q--){
		int op=read(),l=read(),r=read();
		if (op==1){
			int x=read();
			T1.update(l,r,x);
			T2.update(l,r,x);
		} else {
			auto [mn,mx]=T1.Query1(1,1,n,l,r);
			PA t=T1.Query2(1,1,n,l,r);
			if (!T1.check(t.fi,t.se,mn,mx)){
				puts("NO");
				continue;
			}
			
			t=T2.Query2(1,1,n,l,r);
			if (!T2.check(t.fi,t.se,mn,mx)){
				puts("NO");
				continue;
			}

			puts("YES");
		}
	}
}