2021 牛客多校第二场 A.Arithmetic Progression @ Wings            分类 ACM
发布于 星期日, 八月 8 日, 2021 年
更新于 星期日, 八月 8 日, 2021 年

题目

题意

长度为 $n$ 的序列 $a$, 求有多少个连续子序列, 满足排序以后是一个等差数列.

题解

经典枚举 $r$, 用数据结构维护 $l$, 统计有多少个 $l$ 满足条件. 但是我不会😁.

首先这里有一个很巧妙的转换, 一个数列如果能够排成等差数列, 设公差为 $d$, 有序的话, 相邻两个数的差就是 $d$, 乱序的时候, 根据欧几里得算法, 两两之差的 $gcd = d$, 即 $gcd(|a_2 - a_1|, |a_3 - a_2|, \dots) = d$. 当然有可能过程中某两个 $gcd(|a_{i+1} - a_i|, |a_{i+2} - a_{i+1}|) \ne d$, 但是一定有上述 $d | gcd$. 根据这个性质, 如果一个序列排列后是等差数列, 就有 $\max \{a_i\} - \min \{a_i\} = (r - l) \cdot gcd$, 其中, $gcd$ 表示相邻两两之差的 $gcd$, 共 $r - l$ 个. 如果这个序列排序后不是等差数列, 那么相邻两两差值不相等, 可能有 gcd 不变, 比如 2 4 6 8 12, 但是这样最大值减最小值就会比 $r-l$ 个 gcd 大; 或者 gcd 变小, 比如 2 4 6 8 9, 这样最大值减最小值还是比 $r-l$ 个 gcd 大. 严格证明? 不会! 然后把上面那个等式变型, 有 $\max \{a_i\} - \min \{a_i\} - (r - l) \cdot gcd \ge 0$. 而等于 $0$ 的点, 则是对答案有贡献的点.

枚举$r$, 每个点 $l$ 代表的是区间 $[l, r]$, 在这个点中维护 $[l, r]$ 区间的信息. 主要维护 $\max{a_i} - \min{a_i} - (r - l) \cdot gcd$. 然后对 $[1, r]$ 这些点, 开线段树维护区间信息, 主要是区间最小值(因为最小值为 0, 判断是不是 0 就知道这个区间有没有贡献了), 区间里点值为 $0$ 的个数. 那么每次枚举 $r$, 更新了以后, 答案就加上询问区间 $[1, r]$ 的贡献即可.

现在考虑如何维护. 当 $a_r$ 进来时, 考虑它会不会影响前面的某些 $[l, r]$ 中的最大值或者最小值, 这个用单调队列就可以确定需要更新的区间了. 仔细想想就能出来, 不详细解释了. 更新的话就是去掉原来的贡献, 加上现在的贡献. 然后考虑 $d = |a_r - a_{r-1}|$ 对 gcd 的贡献. 这里显然前面的每个点的 gcd 都要对这个东西再取 gcd, 但是注意到, 如果一段线段树上的区间, 即一些连续的 $[l, r]$ 区间的 gcd 都是一个数(显然这些区间是都是等差数列), 并且 $gcd | d$, 这样这些区间在加上 $a_r$ 后, gcd 不变, 不需要更新了. 只需要在值里减去一个 gcd 即可(即维护 $\max{a_i} - \min{a_i} - (r - l) \cdot gcd$). 如果线段树上区间的 gcd 有不同的, 那么就继续向下递归求解. 所以线段树上还需要记录一个 $gcd$. 当向下做到线段树上一个点时, 也即一个区间 $[l, r]$, 需要更新一下 gcd, 同时也需要维护值(详见代码). 而一次更新的 gcd 是呈平方次递减的, 所以一个线段树上的区间总共更新不会超过 $\log a$ 次. 复杂度可接受.

这里维护的 gcd, 如果对线段树上的区间来说, 左右两边的 gcd 不一样, 那么它就必须更新下去; 换句话说, 只有一样的 gcd, 才可以同时更新, 所以这里还需要一个标记, 可以直接用 $gcd = 0$ 来做标记.

pushup 需要维护的除了最小值外, 还需要有多少个点是最小值, 设为 cnt. 可以先对左区间取最小值, 然后判断左右是不是最小值, 是的话就加上这个子区间的 cnt. 两个都不是就是 0. 当然叶子节点最小值是自己, 所以 $cnt = 1$. 不需要担心叶子节点的值是不是0, 因为可以在查询的时候判断, 如果是0, 才加上cnt, 不是就不加. 同理对线段树上的区间也是一样的. 当然也可以维护 cnt 表示是 0 的有多少个, 这样就可以不用判断直接调用.

说的话好像也说不太明白,,, 还是具体看代码比较好, 复杂度大概是 $O(n \log n + n \log a)$? 有个 gcd 在那我也不知道怎么算.

代码
struct Node {
  int l, r, mid;
  LL mn, tag, d, cnt;
} t[MAXN << 2];

int T, n, topmn, topmx, stkmn[MAXN], stkmx[MAXN];
LL ans, a[MAXN];

/* 更新一条完整的线段 */
void updateNode(int u, LL d) {
  t[u].mn += d;
  t[u].tag += d;   //打上标记, 不再往下
}
/* 将标记下放 */
void pushDown(int u) {
  updateNode(LCH(u), t[u].tag);
  updateNode(RCH(u), t[u].tag);
  t[u].tag = 0;    //取消标记
}
/* 由左右儿子线段合并更新当前线段 */
void pushUp(int u) {
  t[u].cnt = 0;
  t[u].mn = min(t[LCH(u)].mn, t[RCH(u)].mn);
  if (t[u].mn == t[LCH(u)].mn)
    t[u].cnt += t[LCH(u)].cnt;
  if (t[u].mn == t[RCH(u)].mn)
    t[u].cnt += t[RCH(u)].cnt;
  t[u].d = t[LCH(u)].d && t[RCH(u)].d && t[LCH(u)].d == t[RCH(u)].d ? t[LCH(u)].d : 0;
}
/* 递归建树 */
void build(int l, int r, int u) {
  t[u] = Node{l, r, (l+r)>>1, 0ll, 0ll, 0ll, 0ll};
  if (l == r) t[u].cnt = 1;
  else {                             //分成左右两边递归求和
    build(l, t[u].mid, LCH(u));
    build(t[u].mid+1, t[u].r, RCH(u));
    pushUp(u);
  }
}

/* 区间修改 */
void updateVal(int l, int r, LL d, int u = 1) {
  if (t[u].l == l && t[u].r == r)
    updateNode(u, d); // 找到对应线段更新
  else {
    pushDown(u);  // 访问u的儿子线段, 需要先下放标记更新
    if (l > t[u].mid)
      updateVal(l, r, d, RCH(u)); //更新的线段全在该区间右边
    else if (r <= t[u].mid)
      updateVal(l, r, d, LCH(u)); // 全在左边
    else { // 跨越了左右两边
      updateVal(l, t[u].mid, d, LCH(u));
      updateVal(t[u].mid+1, r, d, RCH(u));
    }
    pushUp(u);  // 由儿子线段的更新后的值计算当前线段值
  }
}

void updateGcd(int R, int l, int r, LL d, int u = 1) {
  if (t[u].l == l && t[u].r == r && t[u].d && d % t[u].d == 0)
    updateNode(u, -t[u].d);
  else if (t[u].l == t[u].r) {
    updateNode(u, (R - t[u].l - 1) * t[u].d);
    t[u].d = __gcd(t[u].d, d);
    updateNode(u, -(R - t[u].l) * t[u].d);
  }
  else {
    pushDown(u);  // 访问u的儿子线段, 需要先下放标记更新
    if (l > t[u].mid)
      updateGcd(R, l, r, d, RCH(u)); //更新的线段全在该区间右边
    else if (r <= t[u].mid)
      updateGcd(R, l, r, d, LCH(u)); // 全在左边
    else { // 跨越了左右两边
      updateGcd(R, l, t[u].mid, d, LCH(u));
      updateGcd(R, t[u].mid+1, r, d, RCH(u));
    }
    pushUp(u);  // 由儿子线段的更新后的值计算当前线段值
  }
}

LL query(int l, int r, int u = 1) {
  if (t[u].l == l && t[u].r == r)
    return t[u].mn == 0 ? t[u].cnt : 0;
  pushDown(u);
  if (l > t[u].mid) return query(l, r, RCH(u));
  if (r <= t[u].mid) return query(l, r, LCH(u));
  else return query(l, t[u].mid, LCH(u)) +
        query(t[u].mid+1, r, RCH(u));
}

void init() {
  topmn = topmx = ans = 0;
  build(1, n, 1);
}

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    init();
    for (int i = 1; i <= n; i++)
      scanf("%lld", a + i);
    for (int r = 1; r <= n; r++) {
      while (topmn && a[stkmn[topmn]] > a[r]) {
        updateVal(stkmn[topmn-1]+1, stkmn[topmn], a[stkmn[topmn]]);
        topmn--;
      }
      updateVal(stkmn[topmn]+1, r, -a[r]);
      stkmn[++topmn] = r;
      while (topmx && a[stkmx[topmx]] < a[r]) {
        updateVal(stkmx[topmx-1]+1, stkmx[topmx], -a[stkmx[topmx]]);
        topmx--;
      }
      updateVal(stkmx[topmx]+1, r, a[r]);
      stkmx[++topmx] = r;
      if (r > 1)
        updateGcd(r, 1, r-1, abs(a[r] - a[r-1]));
      ans += query(1, r);
    }
    printf("%lld\n", ans);
  }
  return 0;
}

留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch