NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #214756 | #2647. interval | KXG | 100 | 5199ms | 12580kb | C++11 | 2.5kb | 2024-11-21 18:46:46 | 2024-11-22 09:29:49 |
answer
#include <cstdio>
using namespace std;
long long gcd(long long a, long long b) {
if (b == 0) return a;
return gcd(b, a % b);
}
struct segmenttree {
long long a[500010];
long long gcdv[2000010];
void pushup(int p) {
gcdv[p] = gcd(gcdv[p << 1], gcdv[p << 1 | 1]);
}
void build(int p, int l, int r) {
if (l == r) {
gcdv[p] = a[l];
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
pushup(p);
}
void modify(int p, int l, int r, int k, long long x) {
if (l == r) {
gcdv[p] = x;
return;
}
int mid = (l + r) >> 1;
if (k <= mid) {
modify(p << 1, l, mid, k, x);
} else {
modify(p << 1 | 1, mid + 1, r, k, x);
}
pushup(p);
}
int querycnt(int p, int l, int r, long long x) {
if (l == r) {
if (gcdv[p] % x == 0) {
return 0;
} else {
return 1;
}
}
if (gcdv[p] % x == 0) {
return 0;
}
if (gcdv[p << 1] % x != 0 && gcdv[p << 1 | 1] % x != 0) {
return 2;
}
int mid = (l + r) >> 1;
if (gcdv[p << 1 | 1] % x == 0) {
return querycnt(p << 1, l, mid, x);
} else {
return querycnt(p << 1 | 1, mid + 1, r, x);
}
}
int query(int p, int l, int r, int L, int R, long long x) {
if (L <= l && r <= R) {
return querycnt(p, l, r, x);
}
int mid = (l + r) >> 1;
int ans = 0;
if (L <= mid) {
ans += query(p << 1, l, mid, L, R, x);
}
if (R > mid) {
ans += query(p << 1 | 1, mid + 1, r, L, R, x);
}
return ans;
}
} sgt;
int n, m, opt, l, r, x;
long long c;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &sgt.a[i]);
}
sgt.build(1, 1, n);
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%d", &opt);
if (opt == 1) {
scanf("%d%d%lld", &l, &r, &c);
if (sgt.query(1, 1, n, l, r, c) <= 1) {
printf("YES\n");
} else {
printf("NO\n");
}
} else {
scanf("%d%lld", &x, &c);
sgt.modify(1, 1, n, x, c);
}
}
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 4ms
memory: 688kb
input:
4794 52 364 910 468 13650 728 72 5 75 546 273 468 60 360 585 60 175 315 20475 350 18200 18 900 100 4...
output:
NO NO YES NO NO NO NO NO NO NO NO NO YES NO YES YES NO YES NO NO NO NO YES NO YES NO NO NO NO NO NO ...
result:
ok 2239 lines
Test #2:
score: 10
Accepted
time: 3ms
memory: 688kb
input:
4601 117 42 16380 40 6300 84 18200 468 1820 30 4095 2520 2925 840 6552 900 78 273 450 3900 4680 6300...
output:
NO YES NO YES NO YES NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO YES NO YES NO NO YES NO...
result:
ok 2466 lines
Test #3:
score: 10
Accepted
time: 638ms
memory: 12572kb
input:
493909 2340 163800 455 24 1638 130 14 1 182 4200 40 225 600 140 728 936 21 25 81900 520 1800 3 130 6...
output:
NO NO NO YES NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO N...
result:
ok 243064 lines
Test #4:
score: 10
Accepted
time: 646ms
memory: 12444kb
input:
477523 650 9 390 40950 39 1300 5850 600 1638 2184 936 260 16380 3900 1300 12600 11700 546 5 168 14 2...
output:
NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO...
result:
ok 243124 lines
Test #5:
score: 10
Accepted
time: 613ms
memory: 12576kb
input:
494330 7800 56 20 364 36 150 910 4550 780 280 936 163800 1400 8 130 56 936 700 84 14 450 325 650 360...
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 Y...
result:
ok 230459 lines
Test #6:
score: 10
Accepted
time: 588ms
memory: 12448kb
input:
477944 2184 182 105 75 42 3276 36 390 16380 2600 105 10 780 163800 21 504 182 312 13650 650 6552 234...
output:
YES NO NO NO NO NO NO NO YES YES NO YES NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO YES N...
result:
ok 231178 lines
Test #7:
score: 10
Accepted
time: 611ms
memory: 12316kb
input:
461558 5460 36 2340 180 15 819 156 117 210 72 819 312 546 40 300 12600 200 1170 360 105 52 3 175 292...
output:
NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 238940 lines
Test #8:
score: 10
Accepted
time: 601ms
memory: 12580kb
input:
495172 3900 6552 280 6825 35 630 18200 2275 1638 16380 210 45 75 2184 210 975 30 4 100 15 105 100 84...
output:
NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 239975 lines
Test #9:
score: 10
Accepted
time: 764ms
memory: 12488kb
input:
483384 27300 16380 350 200 364 84 210 1 35 6825 910 30 390 504 52 504 1575 350 315 4550 6825 18200 9...
output:
NO NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 239150 lines
Test #10:
score: 10
Accepted
time: 731ms
memory: 12228kb
input:
450191 20475 910 900 39 3 234 40950 3276 11700 175 50 140 1300 15 26 200 18 16380 180 7800 4680 4095...
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 N...
result:
ok 227345 lines
