QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#864963 | #9774. Same Sum | linxuanrui | TL | 0ms | 5856kb | C++14 | 2.9kb | 2025-01-21 12:13:52 | 2025-01-21 12:13:52 |
Judging History
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 ...