QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#864963#9774. Same SumlinxuanruiTL 0ms5856kbC++142.9kb2025-01-21 12:13:522025-01-21 12:13:52

Judging History

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

  • [2025-01-21 12:13:52]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:5856kb
  • [2025-01-21 12:13:52]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 2e5 + 5,b1 = 13131,b2 = 1145141,mod = 201110047;
int n,q,a[N],opt,l,r,x;
int qpow(int a,int b){
	int ans = 1;
	while(b){
		if(b & 1)ans = ans * a % mod;
		a = a * a % mod,b >>= 1;
	}
	return ans;
}
struct SegmentTree{
	struct node{
		int l,r,add,maxx,minn,p1,p2;
	}tree[N << 2];
	void pushup(int p){
		tree[p].maxx = max(tree[p << 1].maxx,tree[p << 1 | 1].maxx);
		tree[p].minn = min(tree[p << 1].minn,tree[p << 1 | 1].minn);
		tree[p].p1 = (tree[p << 1].p1 + tree[p << 1 | 1].p1) % mod;
		tree[p].p2 = (tree[p << 1].p2 + tree[p << 1 | 1].p2) % mod;
	}
	void update(int p,int x){
		tree[p].add += x;
		tree[p].maxx += x;
		tree[p].minn += x;
		tree[p].p1 = tree[p].p1 * qpow(b1,x) % mod;
		tree[p].p2 = tree[p].p2 * qpow(qpow(b1,x),mod - 2) % mod;
	}
	void pushdown(int p){
		update(p << 1,tree[p].add),update(p << 1 | 1,tree[p].add);
		tree[p].add = 0;
	}
	void build(int p,int l,int r){
		tree[p].l = l,tree[p].r = r;
		if(l == r){
			tree[p].maxx = tree[p].minn = a[l];
			tree[p].p1 = qpow(b1,a[l]) % mod;
			tree[p].p2 = qpow(qpow(b1,a[l]),mod - 2) % mod;
			return;
		}
		int mid = (l + r) >> 1;
		build(p << 1,l,mid),build(p << 1 | 1,mid + 1,r);
		pushup(p);
	}
	void update(int p,int l,int r,int x){
		if(r < tree[p].l || tree[p].r < l)return;
		if(l <= tree[p].l && tree[p].r <= r)return update(p,x),void();
		pushdown(p);
		update(p << 1,l,r,x),update(p << 1 | 1,l,r,x);
		pushup(p);
	}
	pair<int,int> query(int p,int l,int r){
		if(l <= tree[p].l && tree[p].r <= r)return {tree[p].p1,tree[p].p2};
		pushdown(p);
		int mid = (tree[p].l + tree[p].r) >> 1;
		if(l <= mid && mid < r){
			pair<int,int> t1 = query(p << 1,l,r),t2 = query(p << 1 | 1,l,r);
			return {(t1.first + t2.first) % mod,(t1.second + t2.second) % mod};
		}else if(l <= mid)return query(p << 1,l,r);
		else return query(p << 1 | 1,l,r);
	}
	pair<int,int> query2(int p,int l,int r){
		if(l <= tree[p].l && tree[p].r <= r)return {tree[p].minn,tree[p].maxx};
		pushdown(p);
		int mid = (tree[p].l + tree[p].r) >> 1;
		if(l <= mid && mid < r){
			pair<int,int> t1 = query2(p << 1,l,r),t2 = query2(p << 1 | 1,l,r);
			return {min(t1.first,t2.first),max(t1.second,t2.second)};
		}else if(l <= mid)return query2(p << 1,l,r);
		else return query2(p << 1 | 1,l,r);
	}
}seg;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	for(int i = 1;i <= n;i++)cin >> a[i];
	seg.build(1,1,n);
	while(q--){
		cin >> opt >> l >> r;
		if(opt == 1)cin >> x,seg.update(1,l,r,x);
		else{
			pair<int,int> t = seg.query(1,l,r);
			pair<int,int> t2 = seg.query2(1,l,r);
//			cout << t.first << " " << t.second * qpow(b1,t2.first + t2.second) % mod << endl;
			cout << (t.second * qpow(b1,t2.first + t2.second) % mod == t.first % mod ? "YES\n" : "NO\n");
		}
	}
}

詳細信息

Test #1:

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

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: