小Z经营一家加油店。小Z加油的方式非常奇怪。他有一排瓶子,每个瓶子有一个容量vi。每次别人来加油,他会让 别人选连续一段的瓶子。他可以用这些瓶子装汽油,但他只有三种操作: 1.把一个瓶子完全加满; 2.把一个瓶子完全倒空; 3.把一个瓶子里的汽油倒进另一个瓶子,直到倒出瓶子空了或者倒进的瓶子满了。 当然,为了回馈用户,小Z会时不时选择连续一段瓶子,给每个瓶子容积都增加x。 为了尽可能给更多的人加油,每次客户来加油他都想知道他能够倒腾出的汽油量最少是多少? 当然他不会一点汽油都不给客户。

 

Input 第一行包括两个数字:瓶子数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

 

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。 Output 对于每个询问输出对应的答案

 

Sample Input3 4 2 3 4 1 1 3 2 2 2 1 1 1 3 1 2 3

Sample Output1 2 4Hint

 

 有可能出现L>R,读入的p不只有0和1,把所有非1操作当成2才能AC

 

 

这个题目是一个线段树+差分

推荐一个差分的博客:https://www.cnblogs.com/cjoierljl/p/8728110.html

学会了这个简单差分之后,就可以把这个题目的区间更新转化成单点更新了,emmm...可能还是不太理解,那就说下具体思路吧。

这个题目一看感觉很难,然后就取看题解,这个看了题解之后发现裴蜀定理+线段树。

讲一下为什么是裴蜀定理+线段树,线段树应该没有什么异议,因为这个有区间更新区间查询,而且n,m的数值很大,不用线段树很容易T。

因为你要进行很多次操作,就可以列一个式子:ax1+bx2+cx3....=ans

这个式子,如果你的数论学的很好的话,就可以知道应该用裴蜀定理,这个裴蜀定理可以自己简单学习一下。

根据裴蜀定理这个最小值应该是gcd(a,b,c,d....),所以我们就应该用线段树来求一个区间的gcd。

为什么又要用到差分呢?

因为如果你每次进行区间更新都是每一个点进行更新(只能这样,不然就无法求gcd),这样子的话,你就会发现T了。

所以我们不这么写,从刚刚的那个博客可以看出,这个可以把区间更新转化成单点更新了,就只需要更新区间左端点和区间右端点+1。

所以总结一下,这个题解法就是:

先对序列进行差分,然后用差分数列进行建树,这个要记录一个和sum和gcd val

然后就是查询,这个查询就是先查左端点的sum,然后再查左端点到右端点之间的差分的val(这个是根据裴蜀定理得出的)

然后就是更新,这个更新是只要对左端点和右端点+1进行更新就可以了。

 

之前是写之前的思路,接下来说说写的过程种碰到的bug,写在代码里了。

其实和普通线段树是差不多的,但是就是会有很多小bug没注意到。

线段树的bug还是很难找的。

 

写一下我对于差分的理解: 如果你碰到你要更新一个区间,给这个区间上的每一个数都加上一个x,让你求n次操作之后求一个区间总和。 又有时间限制,不可以一个一个的去加,这个时候就可以用上差分了。 就是先将这个数列进行差分得到一个差分数列,然后就是对于这个区间的第一位+x, 最后一位的后面一位-x。 这样子操作n次之后再用前缀和求出原来的数列,最后原来的数列再运算即可。

 

#include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <algorithm> #include <queue> #include <vector>
#define inf 0x3f3f3f3f
using namespace std; const int maxn = 1e5 + 10; struct node { int l, r; int sum, val; }tree[maxn*4]; int a[maxn]; int gcd(int a,int b) { return b == 0 ? a : gcd(b, a%b); } void push_up(int id) { tree[id].sum = tree[id << 1].sum + tree[id << 1 | 1].sum; tree[id].val = gcd(tree[id << 1].val, tree[id << 1 | 1].val); } void build(int id,int l,int r)//建树
{ tree[id].l = l; tree[id].r = r; if(tree[id].l==tree[id].r) { tree[id].sum = tree[id].val = a[l]; return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); push_up(id); } int query_sum(int id,int l,int r)//求到第区间第一个的真实值
{ if(l<=tree[id].l&&r>=tree[id].r) { return tree[id].sum; } int mid = (tree[id].l + tree[id].r)>>1, ans = 0; if (l <= mid) ans += query_sum(id << 1, l, r); if(r>mid) ans += query_sum(id << 1 | 1, l, r); return ans; } int query_val(int id,int l,int r)//求区间除开第一个的差分gcd
{ if(l<=tree[id].l&&r>=tree[id].r) { return tree[id].val; } int mid = (tree[id].l + tree[id].r) >> 1, ans = 0; if (l <= mid) ans = gcd(ans, query_val(id << 1, l, r)); if (r > mid) ans = gcd(ans, query_val(id << 1 | 1, l, r)); return ans; } void update(int id,int p,int x) { if (p > tree[id].r) return; if(tree[id].l==tree[id].r) { tree[id].sum += x; tree[id].val += x; return; } int mid = (tree[id].l + tree[id].r) >> 1; if (p <= mid) update(id << 1, p, x); else update(id << 1 | 1, p, x); push_up(id); } int main() { int n, m; 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] - a[i - 1];//要从后往前,注意差分是每一个真实值和这个真实值之前的真实值进行差分
    build(1, 1, n); for (int i = 1; i <= m; i++) { int p, l, r; scanf("%d%d%d", &p, &l, &r); if (l > r) swap(l, r);//这个其实交换不交换都差不多
        if (p == 1) { int exa1 = query_sum(1, 1, l);//去查找第i个数的真实值
            int exa2 = query_val(1, l + 1, r);//i到r之间的gcd
            int ans = abs(gcd(exa1,exa2));//因为是进行差分了,所以gcd之后也有可能有负值
            printf("%d\n", ans); } else { int x; scanf("%d", &x); update(1, l, x);//差分的更新
            update(1, r + 1, -x); } } return 0; }

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄