QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#1020 | #657810 | #9302. Caesar Cipher | ship2077 | ACAAA | Success! | 2024-10-21 09:31:16 | 2024-10-21 09:31:17 |
詳細信息
Extra Test:
Wrong Answer
time: 1ms
memory: 9772kb
input:
40 1 0 0 9 0 12 25 2 0 0 0 0 0 0 0 0 0 24 0 0 1 1 0 0 24 0 0 0 0 0 0 0 0 0 2 25 12 0 9 0 0 2 1 21 20
output:
yes
result:
wrong answer expected NO, found YES [1st token]
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#657810 | #9302. Caesar Cipher | ACAAA# | WA | 979ms | 68220kb | C++23 | 2.5kb | 2024-10-19 15:30:21 | 2024-10-21 09:31:48 |
answer
#include <algorithm>
#include <iostream>
#include <cmath>
#define int long long
using namespace std;
const int N = 5e5 + 10;
const int base = 13331;
const int mod = 1e9 + 7,p= 65535;
typedef long long ll;
int n, m, a[N],p1[N],p2[N];
struct Node {
int l, r;
ll val,maxn,len,tag;
}tr[N<<2];
void pushup(Node& t, Node& lc, Node& rc) {
t.val = (rc.val + lc.val * p1[rc.len] % mod) % mod;
t.maxn = max(lc.maxn, rc.maxn);
t.len = lc.len + rc.len;
}
void pushup(int k) {
pushup(tr[k], tr[k << 1], tr[k << 1 | 1]);
}
void pushdown(Node& t, Node& lc, Node& rc) {
lc.val = (lc.val + t.tag * p2[lc.len-1] % mod) % mod;
rc.val = (rc.val + t.tag * p2[rc.len-1] % mod) % mod;
lc.maxn += t.tag;
rc.maxn += t.tag;
lc.tag += t.tag;
rc.tag += t.tag;
t.tag = 0;
}
void pushdown(int k) {
pushdown(tr[k], tr[k << 1], tr[k << 1 | 1]);
}
void build(int k, int l, int r) {
if (l == r) {
tr[k] = { l,r,a[l],a[l],1,0 };
return;
}
tr[k] = { l,r };
ll mid = (l + r) >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
pushup(k);
}
void modify(int k, int l, int r,int val) {
if (tr[k].l >= l && tr[k].r <= r && tr[k].maxn < p) {
tr[k].val = (tr[k].val + val * p2[tr[k].len-1] % mod) % mod;
tr[k].maxn += val;
tr[k].tag += val;
return;
}
if (tr[k].l == tr[k].r) {
tr[k].val = tr[k].maxn = 0;
return;
}
pushdown(k);
ll mid = (tr[k].l + tr[k].r) >> 1;
if (l <= mid)modify(k << 1, l, r, val);
if (r > mid)modify(k << 1 | 1, l, r, val);
pushup(k);
}
Node query(int k, int l, int r) {
if (tr[k].l >= l && tr[k].r <= r)
return tr[k];
pushdown(k);
ll mid = (tr[k].l + tr[k].r) >> 1;
if (r <= mid)return query(k << 1, l, r);
else if (l > mid)return query(k << 1 | 1, l, r);
else {
auto lc = query(k << 1, l, r);
auto rc = query(k << 1 | 1, l, r);
Node res;
pushup(res, lc, rc);
return res;
}
}
void solve() {
cin >> n >> m;
p1[0] = p2[0] = 1;
for (int i = 1; i <= n; i++) {
cin >> a[i];
p1[i] = p1[i - 1] * base % mod;
p2[i] = (p2[i - 1] * base + 1) % mod;
}
build(1, 1, n);
for (int i = 1; i <= m; i++) {
int op;
cin >> op;
if (op == 1) {
int l, r;
cin >> l >> r;
modify(1, l, r, 1);
}
else {
int x, y, len;
cin >> x >> y >> len;
bool ans = query(1, x, x + len - 1).val == query(1, y, y + len - 1).val;
cout << (ans == 1 ? "yes\n" : "no\n");
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
while (t--)
solve();
}