QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#865057#9774. Same SummaxiaomengTL 0ms42848kbC++236.5kb2025-01-21 14:23:112025-01-21 14:23:12

Judging History

你现在查看的是最新测评结果

  • [2025-01-21 14:23:12]
  • 评测
  • 测评结果：TL
  • 用时：0ms
  • 内存：42848kb
查看
  • [2025-01-21 14:23:11]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=200005;
int n,q,a[N];
struct addseg{
	struct node{
		int l,r,x,add;
	}tree[N<<2];
	inline void pushup(int x){
		tree[x].x=tree[x<<1].x+tree[x<<1|1].x;
	}
	inline void spread(int x){
		if(tree[x].add){
			tree[x<<1].x+=tree[x].add*(tree[x<<1].r-tree[x<<1].l+1);
			tree[x<<1|1].x+=tree[x].add*(tree[x<<1|1].r-tree[x<<1|1].l+1);
			tree[x<<1].add+=tree[x].add;
			tree[x<<1|1].add+=tree[x].add;
			tree[x].add=0;
		}
	}
	inline void build(int a[],int x,int l,int r){
		tree[x].l=l,tree[x].r=r;
		if(l==r){
			tree[x].x=a[l];
			return;
		}
		int mid=l+r>>1;
		build(a,x<<1,l,mid);
		build(a,x<<1|1,mid+1,r);
		pushup(x);
	}
	inline void add(int x,int l,int r,int v){
		int L=tree[x].l,R=tree[x].r;
		if(l>R||L>r)return;
		if(l<=L&&R<=r){
			tree[x].add+=v;
			tree[x].x+=v*(R-L+1);
			return;
		}
		spread(x);
		add(x<<1,l,r,v);
		add(x<<1|1,l,r,v);
		pushup(x);
	}
	inline int query(int x,int l,int r){
		int L=tree[x].l,R=tree[x].r;
		if(l>R||L>r)return 0;
		if(l<=L&&R<=r){
			return tree[x].x;
		}
		spread(x);
		return query(x<<1,l,r)+query(x<<1|1,l,r);
	}
}t;
template<int base,int mod>
struct hashseg{
	struct node{
		int l,r,x,add;
	}tree[N<<2];
	int M;
	hashseg(){
		M=mod;
	}
	inline int fp(int y){
		int r=1,b=base;
		while(y){
			if(y&1)(r*=b)%=mod;
			(b*=b)%=mod;
			y>>=1;
		}
		return r;
	}
	inline void pushup(int x){
		tree[x].x=(tree[x<<1].x+tree[x<<1|1].x)%mod;
	}
	inline void spread(int x){
		if(tree[x].add){
			int z=fp(tree[x].add);
			(tree[x<<1].x*=z)%=mod;
			(tree[x<<1|1].x*=z)%=mod;
			tree[x<<1].add+=tree[x].add;
			tree[x<<1|1].add+=tree[x].add;
			tree[x].add=0;
		}
	}
	inline void build(int a[],int x,int l,int r){
		tree[x].l=l,tree[x].r=r;
		if(l==r){
			tree[x].x=fp(a[l]);
			return;
		}
		int mid=l+r>>1;
		build(a,x<<1,l,mid);
		build(a,x<<1|1,mid+1,r);
		pushup(x);
	}
	inline void add(int x,int l,int r,int v){
		int L=tree[x].l,R=tree[x].r;
		if(l>R||L>r)return;
		if(l<=L&&R<=r){
			int z=fp(v);
			(tree[x].x*=z)%=mod;
			return;
		}
		spread(x);
		add(x<<1,l,r,v);
		add(x<<1|1,l,r,v);
		pushup(x);
	}
	inline int query(int x,int l,int r){
		int L=tree[x].l,R=tree[x].r;
		if(l>R||L>r)return 0;
		if(l<=L&&R<=r){
			return tree[x].x;
		}
		spread(x);
		return query(x<<1,l,r)+query(x<<1|1,l,r);
	}
};
hashseg<1265724354,2046789037>t1265724354_2046789037;
hashseg<1806181529,2046789037>it1265724354_2046789037;
hashseg<1888785031,2046789037>t1888785031_2046789037;
hashseg<1176595799,2046789037>it1888785031_2046789037;
hashseg<971572227,2046789037>t971572227_2046789037;
hashseg<198652986,2046789037>it971572227_2046789037;
hashseg<1265724354,2047439651>t1265724354_2047439651;
hashseg<471460745,2047439651>it1265724354_2047439651;
hashseg<1888785031,2047439651>t1888785031_2047439651;
hashseg<1959377545,2047439651>it1888785031_2047439651;
hashseg<971572227,2047439651>t971572227_2047439651;
hashseg<1670262305,2047439651>it971572227_2047439651;
hashseg<1265724354,2053452277>t1265724354_2053452277;
hashseg<913270818,2053452277>it1265724354_2053452277;
hashseg<1888785031,2053452277>t1888785031_2053452277;
hashseg<673189043,2053452277>it1888785031_2053452277;
hashseg<971572227,2053452277>t971572227_2053452277;
hashseg<1283679343,2053452277>it971572227_2053452277;
inline int chk(int y,int z){
	int s=t.query(1,y,z),len=z-y+1;
	if(s%(len>>1))return 0;
	int m=s/(len>>1);
	if(t1265724354_2046789037.query(1,y,z)!=it1265724354_2046789037.query(1,y,z)*t1265724354_2046789037.fp(m)%t1265724354_2046789037.M)return 0;
	if(t1888785031_2046789037.query(1,y,z)!=it1888785031_2046789037.query(1,y,z)*t1888785031_2046789037.fp(m)%t1888785031_2046789037.M)return 0;
	if(t971572227_2046789037.query(1,y,z)!=it971572227_2046789037.query(1,y,z)*t971572227_2046789037.fp(m)%t971572227_2046789037.M)return 0;
	if(t1265724354_2047439651.query(1,y,z)!=it1265724354_2047439651.query(1,y,z)*t1265724354_2047439651.fp(m)%t1265724354_2047439651.M)return 0;
	if(t1888785031_2047439651.query(1,y,z)!=it1888785031_2047439651.query(1,y,z)*t1888785031_2047439651.fp(m)%t1888785031_2047439651.M)return 0;
	if(t971572227_2047439651.query(1,y,z)!=it971572227_2047439651.query(1,y,z)*t971572227_2047439651.fp(m)%t971572227_2047439651.M)return 0;
	if(t1265724354_2053452277.query(1,y,z)!=it1265724354_2053452277.query(1,y,z)*t1265724354_2053452277.fp(m)%t1265724354_2053452277.M)return 0;
	if(t1888785031_2053452277.query(1,y,z)!=it1888785031_2053452277.query(1,y,z)*t1888785031_2053452277.fp(m)%t1888785031_2053452277.M)return 0;
	if(t971572227_2053452277.query(1,y,z)!=it971572227_2053452277.query(1,y,z)*t971572227_2053452277.fp(m)%t971572227_2053452277.M)return 0;
	return 1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	t.build(a,1,1,n);
	t1265724354_2046789037.build(a,1,1,n);
	it1265724354_2046789037.build(a,1,1,n);
	t1888785031_2046789037.build(a,1,1,n);
	it1888785031_2046789037.build(a,1,1,n);
	t971572227_2046789037.build(a,1,1,n);
	it971572227_2046789037.build(a,1,1,n);
	t1265724354_2047439651.build(a,1,1,n);
	it1265724354_2047439651.build(a,1,1,n);
	t1888785031_2047439651.build(a,1,1,n);
	it1888785031_2047439651.build(a,1,1,n);
	t971572227_2047439651.build(a,1,1,n);
	it971572227_2047439651.build(a,1,1,n);
	t1265724354_2053452277.build(a,1,1,n);
	it1265724354_2053452277.build(a,1,1,n);
	t1888785031_2053452277.build(a,1,1,n);
	it1888785031_2053452277.build(a,1,1,n);
	t971572227_2053452277.build(a,1,1,n);
	it971572227_2053452277.build(a,1,1,n);
	while(q--){
		int x,y,z,w;
		cin>>x>>y>>z;
		if(x&1){
			cin>>w;
			t.add(1,y,z,w);
			t1265724354_2046789037.add(1,y,z,w);
			it1265724354_2046789037.add(1,y,z,w);
			t1888785031_2046789037.add(1,y,z,w);
			it1888785031_2046789037.add(1,y,z,w);
			t971572227_2046789037.add(1,y,z,w);
			it971572227_2046789037.add(1,y,z,w);
			t1265724354_2047439651.add(1,y,z,w);
			it1265724354_2047439651.add(1,y,z,w);
			t1888785031_2047439651.add(1,y,z,w);
			it1888785031_2047439651.add(1,y,z,w);
			t971572227_2047439651.add(1,y,z,w);
			it971572227_2047439651.add(1,y,z,w);
			t1265724354_2053452277.add(1,y,z,w);
			it1265724354_2053452277.add(1,y,z,w);
			t1888785031_2053452277.add(1,y,z,w);
			it1888785031_2053452277.add(1,y,z,w);
			t971572227_2053452277.add(1,y,z,w);
			it971572227_2053452277.add(1,y,z,w);
		}else{
			cout<<"no\0yes"+chk(y,z)*3<<'\n';
		}
	}
    return 0;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 42848kb

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
Time Limit Exceeded

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
...

result:
English 繁體中文 简体中文

Server Time: 2025-01-22 21:39:21 | OpenSource Project