题目描述
给出 $n$ 个瓶子和无限的水，每个瓶子有一定的容量。每次你可以将一个瓶子装满水，或将A瓶子内的水倒入B瓶子中直到A倒空或B倒满。$m$ 次操作，每次给 $[l,r]$ 内的瓶子容量增加 $x$ ，或询问使用 $[l,r]$ 内瓶子能够凑出的最小体积。
输入
第一行包括两个数字：瓶子数n，事件数m。
第二行包含n个整数，表示每个瓶子的容量vi。
接下来m行，每行先有三个整数fi li ri。
若fi=1表示询问li到ri他最少能倒腾出的汽油量最少是多少？
若fi=2 再读入一个整数x。表示他将li到ri的瓶子容量都增加了x。
1 <= n,m <= 10^5 , 1<=li<=ri<=n , 1<=初始容量,增加的容量<=1000
输出
对于每个询问输出对应的答案
样例输入
3 4
2 3 4
1 1 3
2 2 2 1
1 1 3
1 2 3
样例输出
1
2
4
题解
扩展裴蜀定理+差分+线段树
由 【bzoj2257】瓶子和燃料 的结论，答案为区间 $gcd$ 。
那么问题转化为：区间加、区间求 $gcd$ 。
直接解决这个问题比较困难。我们知道，$gcd(a,b,c)=gcd(a,b-a,c-b)$ ，即区间 $gcd$ 等于 $l$ 位置的数与 $[l+1,r]$ 的差分数组的 $gcd$ 。而区间加在差分数组上表现为单点加减，较容易维护。
因此对原数组求差分数组，修改时在差分数组上进行单点加减，查询时查询差分数组的前缀和及区间 $gcd$ ，最大公约数即为答案。
时间复杂度 $O(nlog n)$ （求 $gcd$ 的 $log$ 在线段树pushup的过程中均摊掉了，因此只有一个 $log$ ）
#include <cstdio>
#include <algorithm>
#define N 100010
#define lson l , mid , x << 1
#define rson mid + 1 , r , x << 1 | 1
using namespace std;
int a[N] , sum[N << 2] , val[N << 2];
inline int gcd(int a , int b)
{
int t;
while(b) t = a , a = b , b = t % b;
return a;
}
inline void pushup(int x)
{
sum[x] = sum[x << 1] + sum[x << 1 | 1] , val[x] = gcd(val[x << 1] , val[x << 1 | 1]);
}
void build(int l , int r , int x)
{
if(l == r)
{
sum[x] = val[x] = a[l] - a[l - 1];
return;
}
int mid = (l + r) >> 1;
build(lson) , build(rson);
pushup(x);
}
void update(int p , int a , int l , int r , int x)
{
if(p > r) return;
if(l == r)
{
sum[x] += a , val[x] += a;
return;
}
int mid = (l + r) >> 1;
if(p <= mid) update(p , a , lson);
else update(p , a , rson);
pushup(x);
}
int qsum(int p , int l , int r , int x)
{
if(l == r) return sum[x];
int mid = (l + r) >> 1;
if(p <= mid) return qsum(p , lson);
else return qsum(p , rson) + sum[x << 1];
}
int qval(int b , int e , int l , int r , int x)
{
if(b > e) return 0;
if(b <= l && r <= e) return val[x];
int mid = (l + r) >> 1 , ans = 0;
if(b <= mid) ans = gcd(ans , qval(b , e , lson));
if(e > mid) ans = gcd(ans , qval(b , e , rson));
return ans;
}
int main()
{
int n , m , i , opt, l , r , x;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]);
build(1 , n , 1);
while(m -- )
{
scanf("%d%d%d" , &opt , &l , &r);
if(opt == 1) printf("%d
" , abs(gcd(qsum(l , 1 , n , 1) , qval(l + 1 , r , 1 , n , 1))));
else scanf("%d" , &x) , update(l , x , 1 , n , 1) , update(r + 1 , -x , 1 , n , 1);
}
return 0;
}