[测试题]wows

以你之姓@ 2021-10-25 12:28 254阅读 0赞

## 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 ##

## Hint ##

![1184731-20171016162022146-1066996416.png][]

## 题解（转载） ##

[\->原文地址<-][-_-]

题目大意是每一次给一个区间加上两段等差数列

在线询问$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\n");
     97             else printf("%d\n", T.query(1, 1, n-1, l, r-1).s+1);
     98         }
     99     }
    100 }
    101 int main() {
    102     work();
    103     return 0;
    104 }

转载于:https://www.cnblogs.com/NaVi-Awson/p/7678835.html

[1184731-20171016162022146-1066996416.png]: /images/20211025/3c92ecb6991a4b94a11f04f47f0bef52.png
[-_-]: http://www.cnblogs.com/Y-E-T-I/p/7677577.html