cf914D. Bash and a Tough Math Puzzle(线段树)
程序员文章站
2022-04-06 11:59:49
题意 "题目链接" Sol 直接在线段树上二分 当左右儿子中的一个不是$x$的倍数就继续递归 由于最多递归到一个叶子节点,所以复杂度是对的 开始时在纠结如果一段区间全是$x$的两倍是不是需要特判,实际上是不需要的。 可以这么想,如果能成功的话,我们可以把那个数改成$1$,这样比$x$大的数就不会对答 ......
题意
sol
直接在线段树上二分
当左右儿子中的一个不是$x$的倍数就继续递归
由于最多递归到一个叶子节点,所以复杂度是对的
开始时在纠结如果一段区间全是$x$的两倍是不是需要特判,实际上是不需要的。
可以这么想,如果能成功的话,我们可以把那个数改成$1$,这样比$x$大的数就不会对答案产生影响了。
不过我的线段树为啥要开6倍空间才能过。。真是狗血、、
#include<bits/stdc++.h> using namespace std; const int maxn = 3e6 + 10, inf = 1e9 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, a[maxn]; #define ls k << 1 #define rs k << 1 | 1 struct node { int l, r, g; }t[maxn]; int gcd(int a, int b) { return (b == 0 ? a : gcd(b, a % b)); } void update(int k) { t[k].g = gcd(t[ls].g, t[rs].g); } void build(int k, int ll, int rr) { t[k] = (node) {ll, rr}; if(ll == rr) {t[k].g = a[ll]; return ;} int mid = t[k].l + t[k].r >> 1; build(ls, ll, mid); build(rs, mid + 1, rr); update(k); } void pointchange(int k, int pos, int val) { if(t[k].l == t[k].r) {t[k].g = val; return ;} int mid = t[k].l + t[k].r >> 1; if(pos <= mid) pointchange(ls, pos, val); else pointchange(rs, pos, val); update(k); } int sum = 0; void intervaltims(int k, int ll, int rr, int val) { if(sum > 1) return ; if(t[k].l == t[k].r) sum++; int mid = t[k].l + t[k].r >> 1; if(ll <= mid && (t[ls].g % val)) intervaltims(ls, ll, rr, val); if(rr > mid && (t[rs].g % val)) intervaltims(rs, ll, rr, val); } main() { n = read(); for(int i = 1; i <= n; i++) a[i] = read(); build(1, 1, n); m = read(); while(m--) { int opt = read(); if(opt == 1) { int l = read(), r = read(), x = read(); sum = 0; intervaltims(1, l, r, x); puts(sum > 1 ? "no" : "yes"); } else { int pos = read(), x = read(); pointchange(1, pos, x); } } } /* */