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$
//It is made by Awson on 2017.10.16
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Lr(x) (x<<1)
#define Rr(x) (x<<1|1)
using namespace std;
const int N = 1e5; int n, m;
int opt, l, r, a, k, p;
struct node {
int ls, rs, lp, rp, s;
node () {
}
}sgm[(N<<)+];
int lazy[(N<<)+];
struct segment {
node merge(node a, node b, int l, int mid, int r) {
node tmp;
tmp.ls = a.ls, tmp.rs = b.rs;
tmp.lp = a.lp, tmp.rp = b.rp;
if (a.rs == mid-l+ && a.rp == b.lp) tmp.ls += b.ls;
if (b.ls == r-mid && b.lp == a.rp) tmp.rs += a.rs;
tmp.s = Max(a.s, b.s);
if (a.rp == b.lp) tmp.s = Max(tmp.s, a.rs+b.ls);
return tmp;
}
void build(int o, int l, int r) {
if (l == r) {
sgm[o].lp = sgm[o].rp = ;
sgm[o].ls = sgm[o].rs = sgm[o].s = ;
return;
}
int mid = (l+r)>>;
build(Lr(o), l, mid);
build(Rr(o), mid+, r);
sgm[o] = merge(sgm[Lr(o)], sgm[Rr(o)], l, mid, r);
}
void pushdown(int o) {
sgm[Lr(o)].lp += lazy[o], sgm[Lr(o)].rp += lazy[o];
sgm[Rr(o)].lp += lazy[o], sgm[Rr(o)].rp += lazy[o];
lazy[Lr(o)] += lazy[o], lazy[Rr(o)] += lazy[o];
lazy[o] = ;
}
void update(int o, int l, int r, int a, int b, int key) {
if (a <= l && r <= b) {
sgm[o].lp += key, sgm[o].rp += key;
lazy[o] += key;
return;
}
pushdown(o);
int mid = (l+r)>>;
if (a <= mid) update(Lr(o), l, mid, a, b, key);
if (b > mid) update(Rr(o), mid+, r, a, b, key);
sgm[o] = merge(sgm[Lr(o)], sgm[Rr(o)], l, mid, r);
}
node query(int o, int l, int r, int a, int b) {
if (a <= l && r <= b) return sgm[o];
pushdown(o);
int mid = (l+r)>>;
if (a <= mid && b > mid) {
node t1 = query(Lr(o), l, mid, a, b);
node t2 = query(Rr(o), mid+, r, a, b);
return merge(t1, t2, l, mid, r);
}else if (a <= mid) return query(Lr(o), l, mid, a, b);
else return query(Rr(o), mid+, r, a, b);
}
}T;
void work() {
scanf("%d%d", &n, &m);
T.build(, , n-);
while (m--) {
scanf("%d", &opt);
if (opt == ) {
scanf("%d%d%d%d%d", &l, &r, &a, &k, &p);
if (l != ) T.update(, , n-, l-, l-, a);
if (l <= p-) T.update(, , n-, l, p-, k);
if (p <= r-) T.update(, , n-, p, r-, -k);
if (r != n) T.update(, , n-, r, r, -a-(*p-l-r)*k);
}else {
scanf("%d%d", &l, &r);
if (l == r) printf("1\n");
else printf("%d\n", T.query(, , n-, l, r-).s+);
}
}
}
int main() {
work();
return ;
}