Description
山山最近在玩一款游戏叫战舰世界(steam 游戏太少了),他被大舰巨炮的魅力折服,于是山山开了一局游戏,这次发现目标是一艘战列舰新墨西哥级,舰桥很高,原本应该打在目标身后的圆形水域内的炮弹,都打在了舰桥上,于是落点变成了一条直线。因为新墨西哥中间高两边低,所以按概率算,炮弹命中数中间多,两边少,并且中央区域容易穿透出现高伤害,所以 山山向中间发射的炮弹比两边多,因为他有强迫症,所以一个位置炮弹发射数相对于上一个位置的数目的变化量为 ki(整体大概构成一个山峰状),新墨西哥操纵者因为 OI 的时候玩游戏,脑袋被教练按键盘了,所以站着不动,导致山山能够百发百中,求数轮齐射后,在一段区域的命中数为阶梯增长的长度 (阶梯增长为 A+0K,A+1K· · ·K 随意取,单调增)(为了便于统计伤害,我们把新墨西哥分成 n 段,同时也便于瞄准。
新墨西哥被教练抓着脑袋摁键盘了,我就不信我也 gbhghuyjhhfdhsfdhndxf......
Input
输入文件名为 wows.in。
第一行 n m, 表示新墨西哥被分成 n 段, 山山开炮数和询问命中次数的总数,第二行以后每行开头一个 f,0 表示开炮,1 表示询问
如果开炮 后面还有 5 个参数 l,r,a,k,p表示 山山向 l 到 r 段开炮,l 段开了 a 炮,以后 l + 1 到 p 段分别开 a+k,a+k+k,a+k+k+k···炮, p+1 到 r 段开 a+(p-l-1)k、a+(p-l-2)k···炮
如果询问 后面有 l,r 表示询问区域(保证任意相邻区段数据之差在任何时候在 int 内)
Output
输出文件名为 wows.out。
对于每个询问输出一个数,表示符合要求的最大长度,后跟一个回车
Sample Input
5 3
0 1 5 2 2 3
0 4 5 4 4 5
1 1 5
Sample Output
5
Hint
题解（转载）
题目大意是每一次给一个区间加上两段等差数列
在线询问$l$~$r$之间的最长等差数列
这道题最坑的是题意描述，划掉的递增指的是$k$的系数
只要等差就行
于是先差分一次，$c[i]=a[i+1]-a[i]$那么对于加上$a$,$a+k$,$a+2k$,$a+3k$,$a+2k$,$a+k$这个序列
差分后等价于$a$,$k$,$k$,$k$,$-k$,$-k$,$-a-k$
也就是:$c[l-1]+=a$,$c[l~p-1]+=k$,$c[p~r-1]-=k$,$c[r]=-a-(2*p-l-r)*k$
差分后，询问就变成了求差分数组中最长的一段值相同的连续区间长度$+1$
这个可以用线段树维护
对于每个点，维护以下变量：
$ls$,$rs$:线段最左边/右边连续相同的长度
$lp$,$rp$:线段最左边/右边连续相同的数字
$s$:当前线段最长连续相等区间
延迟标记另用一个数组，因为延迟标记不参与合并操作
合并左右节点的信息：
首先:$c[rt].ls=c[rt*2].ls$,$c[rt].rs=c[rt*2+1].rs$
$c[rt].lp=c[rt*2].lp$,$c[rt].rp=c[rt*2+1].rp$
$c[rt].s=max(c[rt*2].s,c[rt*2+1].s)$
当$c[rt*2]$全为一个数且$c[rt*2].rp$与$c[rt*2+1].lp$相同，那么显然右边区间$ls$都可以作为新区间的$ls$
$rs$的处理同理
接下来考虑两个区间对s的影响
如果$c[rt*2].rp==c[rt*2+1].lp$那么显然这一段可以作为一段新的连续相同序列
$c[rt].s=max(c[rt].s,c[rt*2].rs+c[rt*2+1].ls)$
其实还可以再差分一次，这样就只涉及单点修改，并询问最长的连续$0$的数量$+2$
拿上面举例
一次差分后：$a$,$k$,$k$,$k$,$-k$,$-k$,$-a-k$
二次差分后：$a$,$k-a$,$0$,$0$,$-2k$,$0$,$-a$,$a+k$
1 //It is made by Awson on 2017.10.16 2 #include <map> 3 #include <set> 4 #include <cmath> 5 #include <ctime> 6 #include <queue> 7 #include <stack> 8 #include <vector> 9 #include <cstdio> 10 #include <string> 11 #include <cstdlib> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 #define LL long long 16 #define Max(a, b) ((a) > (b) ? (a) : (b)) 17 #define Min(a, b) ((a) < (b) ? (a) : (b)) 18 #define Lr(x) (x<<1) 19 #define Rr(x) (x<<1|1) 20 using namespace std; 21 const int N = 1e5; 22 23 int n, m; 24 int opt, l, r, a, k, p; 25 struct node { 26 int ls, rs, lp, rp, s; 27 node () { 28 } 29 }sgm[(N<<2)+5]; 30 int lazy[(N<<2)+5]; 31 struct segment { 32 node merge(node a, node b, int l, int mid, int r) { 33 node tmp; 34 tmp.ls = a.ls, tmp.rs = b.rs; 35 tmp.lp = a.lp, tmp.rp = b.rp; 36 if (a.rs == mid-l+1 && a.rp == b.lp) tmp.ls += b.ls; 37 if (b.ls == r-mid && b.lp == a.rp) tmp.rs += a.rs; 38 tmp.s = Max(a.s, b.s); 39 if (a.rp == b.lp) tmp.s = Max(tmp.s, a.rs+b.ls); 40 return tmp; 41 } 42 void build(int o, int l, int r) { 43 if (l == r) { 44 sgm[o].lp = sgm[o].rp = 0; 45 sgm[o].ls = sgm[o].rs = sgm[o].s = 1; 46 return; 47 } 48 int mid = (l+r)>>1; 49 build(Lr(o), l, mid); 50 build(Rr(o), mid+1, r); 51 sgm[o] = merge(sgm[Lr(o)], sgm[Rr(o)], l, mid, r); 52 } 53 void pushdown(int o) { 54 sgm[Lr(o)].lp += lazy[o], sgm[Lr(o)].rp += lazy[o]; 55 sgm[Rr(o)].lp += lazy[o], sgm[Rr(o)].rp += lazy[o]; 56 lazy[Lr(o)] += lazy[o], lazy[Rr(o)] += lazy[o]; 57 lazy[o] = 0; 58 } 59 void update(int o, int l, int r, int a, int b, int key) { 60 if (a <= l && r <= b) { 61 sgm[o].lp += key, sgm[o].rp += key; 62 lazy[o] += key; 63 return; 64 } 65 pushdown(o); 66 int mid = (l+r)>>1; 67 if (a <= mid) update(Lr(o), l, mid, a, b, key); 68 if (b > mid) update(Rr(o), mid+1, r, a, b, key); 69 sgm[o] = merge(sgm[Lr(o)], sgm[Rr(o)], l, mid, r); 70 } 71 node query(int o, int l, int r, int a, int b) { 72 if (a <= l && r <= b) return sgm[o]; 73 pushdown(o); 74 int mid = (l+r)>>1; 75 if (a <= mid && b > mid) { 76 node t1 = query(Lr(o), l, mid, a, b); 77 node t2 = query(Rr(o), mid+1, r, a, b); 78 return merge(t1, t2, l, mid, r); 79 }else if (a <= mid) return query(Lr(o), l, mid, a, b); 80 else return query(Rr(o), mid+1, r, a, b); 81 } 82 }T; 83 void work() { 84 scanf("%d%d", &n, &m); 85 T.build(1, 1, n-1); 86 while (m--) { 87 scanf("%d", &opt); 88 if (opt == 0) { 89 scanf("%d%d%d%d%d", &l, &r, &a, &k, &p); 90 if (l != 1) T.update(1, 1, n-1, l-1, l-1, a); 91 if (l <= p-1) T.update(1, 1, n-1, l, p-1, k); 92 if (p <= r-1) T.update(1, 1, n-1, p, r-1, -k); 93 if (r != n) T.update(1, 1, n-1, r, r, -a-(2*p-l-r)*k); 94 }else { 95 scanf("%d%d", &l, &r); 96 if (l == r) printf("1 "); 97 else printf("%d ", T.query(1, 1, n-1, l, r-1).s+1); 98 } 99 } 100 } 101 int main() { 102 work(); 103 return 0; 104 }