「Codeforces 914D」Bash and a Tough Math Puzzle

发表于 | | 阅读次数:
字数统计: 512 字

Description

题目链接：Codeforces 914D

给定一个长度为 $n$ 的数列 $a_i$ 和 $q$ 次操作，有 $2$ 种操作：

  • 1 l r x：询问是否可以改动至多一个数使得下标在 $[l,r]$ 内的数的的 $\gcd$ 为 $x$。如果可以则输出 $\text{YES}$ 否则输出 $\text{NO}$。
  • 2 i y：将 $a_i$ 修改为 $y$。

数据范围：$1\le n\le 5\times 10^5$，$1\le q\le 4\times 10^5$，$1\le a_i\le 10^9$

Solution

这是一道线段树裸题 QAQ

我们只需要直接查询区间内不能整除 $x$ 的数的数量 $cnt$。

  • 如果 $cnt>1$，那么不可能通过修改至多 $1$ 个数达到要求。
  • 如果 $cnt=1$，那么直接将那个数修改成 $x$ 即可。
  • 如果 $cnt=0$，那么任意选择一个数修改成 $x$ 即可。

时间复杂度：$O(n\log^2 n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#define lson rt<<1
#define rson rt<<1|1

const int N=5e5+5;
int n,q,cnt,seg[N<<2];

int gcd(int x,int y) {
    return y?gcd(y,x%y):x;
}
void pushup(int rt) {
    seg[rt]=gcd(seg[lson],seg[rson]);
}
void build(int rt,int l,int r) {
    if(l==r) {
        scanf("%d",&seg[rt]);
        return;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(rt);
}
void modify(int x,int rt,int l,int r,int val) {
    if(l==r) {
        seg[rt]=val;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(x,lson,l,mid,val);
    else modify(x,rson,mid+1,r,val);
    pushup(rt);
}
void query(int x,int y,int rt,int l,int r,int d) {
    if(cnt>1) return;
    if(l==r) {
        ++cnt;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid&&seg[lson]%d) query(x,y,lson,l,mid,d);
    if(mid<y&&seg[rson]%d) query(x,y,rson,mid+1,r,d);
}
int main() {
    scanf("%d",&n);
    build(1,1,n);
    for(scanf("%d",&q);q--;) {
        int opt;
        scanf("%d",&opt);
        if(opt==1) {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            cnt=0,query(l,r,1,1,n,x);
            puts(cnt>1?"NO":"YES");
        } else {
            int x,k;
            scanf("%d%d",&x,&k);
            modify(x,1,1,n,k);
        }
    }
    return 0;
}
0%