「BZOJ 5028」小 Z 的加油店

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

Description

题目链接：BZOJ 5028

小 Z 经营一家加油店。小 Z 加油的方式非常奇怪。他有一排共 $n$ 个瓶子，第 $i$ 个瓶子的容量为 $v_i$。每次别人来加油，他会让别人选连续一段的瓶子 $[l,r]$，他可以用这些瓶子装汽油，但他只有三种操作：把一个瓶子完全加满；把一个瓶子完全倒空；把一个瓶子里的汽油倒进另一个瓶子，直到倒出瓶子空了或者倒进的瓶子满了。

现在有 $m$ 个事件，事件的种类一共有 $2$ 种：

  • 1 l r：询问 $[l,r]$ 这一段瓶子能倒出的汽油量最少是多少（不能为 $0$）。
  • 2 l r x：将 $[l,r]$ 这段区间内的瓶子内的容量都增加 $x$。

数据范围：$1\le n,m\le 10^5$，$1\le v_i,x\le 1000$

Solution

根据装汽油的方式，我们可以注意到：区间 $[l,r]$ 这一段瓶子能倒出的汽油量最少为 $\gcd\{v_i\}(l\le i\le r)$。

先考虑没有修改操作，那么我们只要倍增预处理出 $\gcd$ 就行了。如果增加了修改操作，单点修改是非常的，但如果是区间修改就无法维护 $\gcd$，所以需要考虑 $\gcd$ 的性质。根据 $\gcd$ 的一种常见求法辗转相减法，可以得到 $\gcd(a,b)=\gcd(a,b-a)$，所以求区间 $[l,r]$ 的 $\gcd$ 等价于求这个区间的差分数组的 $\gcd$。

于是我们用线段树维护差分数组的区间 $\gcd$ 和区间和，支持单点修改和区间查询即可。注意：由于差分数组上的第 $l$ 个元素的值和它之前的元素有关，所以需要单独查询第 $l$ 个数的值，将这个值和 $[l+1,r]$ 的 $\gcd$ 取 $\gcd$。

时间复杂度：$O(m\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
63
64
65
66
67
 
#include <cstdio>
#include <algorithm>
#define lson rt<<1
#define rson rt<<1|1

const int N=1e5+5;
int n,m,a[N],seg[N<<2],sum[N<<2];

int gcd(int x,int y) {return y?gcd(y,x%y):x;}
void pushup(int rt) {
    sum[rt]=sum[lson]+sum[rson];
    seg[rt]=gcd(seg[lson],seg[rson]);
}
void build(int rt,int l,int r) {
    if(l==r) {
        sum[rt]=seg[rt]=a[l];
        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 k) {
    if(l==r) {
        seg[rt]+=k,sum[rt]+=k;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(x,lson,l,mid,k);
    else modify(x,rson,mid+1,r,k);
    pushup(rt);
}
int querySum(int x,int y,int rt,int l,int r) {
    if(x<=l&&r<=y) return sum[rt];
    int mid=(l+r)>>1,ret=0;
    if(x<=mid) ret+=querySum(x,y,lson,l,mid);
    if(mid<y) ret+=querySum(x,y,rson,mid+1,r);
    return ret;
}
int queryGcd(int x,int y,int rt,int l,int r) {
    if(x<=l&&r<=y) return seg[rt];
    int mid=(l+r)>>1,ret=0;
    if(x<=mid) ret=gcd(ret,queryGcd(x,y,lson,l,mid));
    if(mid<y) ret=gcd(ret,queryGcd(x,y,rson,mid+1,r));
    return ret;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    for(int i=n;i>=1;--i) a[i]-=a[i-1];
    build(1,1,n);
    while(m--) {
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==1) {
            int ans=gcd(querySum(1,l,1,1,n),queryGcd(l+1,r,1,1,n));
            printf("%d\n",std::abs(ans));
        } else {
            int x;
            scanf("%d",&x);
            modify(l,1,1,n,x);
            if(r<n) modify(r+1,1,1,n,-x);
        }
    }
    return 0;
}
0%