2021 牛客多校第五场 I.Interval Queries @ Wings            分类 ACM
发布于 星期五, 八月 20 日, 2021 年
更新于 星期五, 八月 20 日, 2021 年

题目

题意

长度为 $n$ 的序列, $q$ 次查询, 每次询问 $l, r, k$, 对于 $i = 0 : k-1$, 将区间 $[l-i, r+i]$ 中的数去重排序, 最长连续段的长度, 乘以 $(n+1)^i$ 统计到答案中.

$1 \le n, q \le 10^5, 1 \le a_i \le n, 1 \le l - k + 1 \le l \le r \le r + k - 1 \le n, \sum k \le 10^7$

题解

(一开始在想线段树区间合并怎么维护, 突然发现还有个枚举 $i$ 从 $0$ 到 $k$, 人就傻了)

正解是莫队! 作为一个反对莫队选手, 反正我是没看出来是莫队. 现在想想好像挺有道理? 首先是区间询问, 可以离线, 然后线段树做不了, 更多地, 因为一个询问就要拓展 $k$ 次, 而 $\sum k \le 10^7$. 正好如果全给他 $O(1)$ 暴力维护多出来的点 (如果是数据结构的话每次维护多出来的点就是 $O(\log n)$, 就T了), 综上, 莫队没跑了.

然后就是怎么维护连续段的问题了. 题解说用链表, 我不太会, 我这里用的并查集. 然后删除操作很麻烦, 并查集没法删除啊! 如果是链表, 确实可以删除, 但是不好维护删除以后两个链表的大小. 所以需要回滚莫队. 然后多出来的点可以当作临时信息, 就没了. 并查集回滚的话开个栈记录一下修改前的信息, 回滚直接改回去就行了. 链表应该也差不多? 不太清楚.

一点小细节, 回滚还是要注意临时信息一定不要写错(老把永久信息改掉,,,), 并查集在路径压缩的时候一些点的信息会边, 如果是临时信息, 注意记录. 长度小于 $\sqrt n$ 的询问可以直接暴力. 由于 $query_l$ 在不同块的时候, 指针 $r$ 会往回走, 前面说过了不好维护, 而且这里如果再开一个栈进行回滚永久信息的话, 不太方便(其实好像也可以), 所以直接清空所有信息重新开始做这一块的询问即可.

复杂度 $O(\alpha n \sqrt n + \alpha \sum k)$, $\alpha$ 是因为并查集路径压缩要记录回滚信息. 如果用链表应该不带 $\alpha$.

代码
int n, q, block_size, id[MAXN], a[MAXN], cnt[MAXN], tmpcnt[MAXN], ans[MAXN], pw[MAXN];
int getBlockR(int block_id) { return min(block_id * block_size, n); }
int getBlockL(int block_id) { return getBlockR(block_id-1) + 1; }
struct Query {
  int idx, l, r, k;
  bool operator < (const Query &Q) const {
    return id[l] == id[Q.l] ? r < Q.r : id[l] < id[Q.l];
  }
};

vector<Query> query[MAXB];
struct Node {
  int u, f, s;
};
vector<Node> stk;

int fa[MAXN], sz[MAXN];
void init(int n) {
  for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
}
int find(int x, int flag_tmp = false) {
  if (x == fa[x])
    return x;
  if (flag_tmp)
    stk.push_back({x, fa[x], sz[x]});
  return fa[x] = find(fa[x], flag_tmp);

}
// 返回合并后的大小
int uni(int x, int y, bool flag_tmp) {
  int fx = find(x, flag_tmp), fy = find(y, flag_tmp);
  if (fx == fy)
    return 0;
  if (flag_tmp) {
    stk.push_back({fx, fa[fx], sz[fx]});
    stk.push_back({fy, fa[fy], sz[fy]});
  }
  fa[fx] = fy;
  sz[fy] += sz[fx];
  return sz[fy];
}

bool vis[MAXN], tmpvis[MAXN];

int add(int c, bool flag_tmp = false) {
  int mx = 1;
  if (vis[c+1] || tmpvis[c+1])
    mx = max(mx, uni(c, c+1, flag_tmp));
  if (vis[c-1] || tmpvis[c-1])
    mx = max(mx, uni(c, c-1, flag_tmp));
  if (flag_tmp)
    tmpvis[c] = 1;
  else
    vis[c] = 1;
  return mx;
}

void rollback() {
  memset(tmpvis, 0, sizeof(tmpvis));
  while (stk.size()) {
    auto[u, f, s] = stk.back();
    stk.pop_back();
    fa[u] = f, sz[u] = s;
  }
}

void solve() {
  init(n);
  for (auto[idx, l, r, k] : query[0]) {
    int mx = 1;
    for (int p = l; p <= r; p++)
      mx = max(mx, add(a[p]));
    int res = mx;
    for (int i = 1; i < k; i++) {
      mx = max(mx, add(a[r+i]));
      mx = max(mx, add(a[l-i]));
      res = pls(res, mult(mx, pw[i]));
    }
    ans[idx] = res;
    // 结束, 重置ufs
    for (int i = l-k; i <= r+k; i++)
      fa[a[i]] = a[i], sz[a[i]] = 1, vis[a[i]] = 0;
  }

  for (int i = 1; i <= MAXB-30; i++) if (query[i].size()) {
    init(n);
    memset(vis, 0, sizeof(vis));
    sort(query[i].begin(), query[i].end());
    int l = getBlockL(id[query[i][0].l]+1), r = l-1;
    int mx = 1;
    for (Query Q : query[i]) {
      // 维护永久信息
      while (r < Q.r)
        mx = max(mx, add(a[++r]));
      // 暴力维护临时信息
      int tmpmx = mx;
      for (int j = Q.l; j <= min(Q.r, getBlockR(id[Q.l])); j++)
        tmpmx = max(tmpmx, add(a[j], 1));

      int res = tmpmx;
      for (int i = 1; i < Q.k; i++) {
        tmpmx = max(tmpmx, add(a[Q.r+i], 1));
        tmpmx = max(tmpmx, add(a[Q.l-i], 1));
        res = pls(res, mult(tmpmx, pw[i]));
      }
      ans[Q.idx] = res;

      // 回滚临时信息
      rollback();
    }
  }
}

int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++)
    scanf("%d", a + i);

  pw[0] = 1;
  for (int i = 1; i <= n; i++)
    pw[i] = mult(pw[i-1], n+1);

  block_size = sqrt(n);
  for (int i = 1; i <= n; i++)
    id[i] = (i-1) / block_size + 1;

  for (int i = 1; i <= q; i++) {
    int l, r, k;
    scanf("%d%d%d", &l, &r, &k);
    // 区间长度小于 sqrt n 的可以直接暴力, 存在 query[0] 里暴力
    if (r - l + 1 <= block_size)
      query[0].push_back({i, l, r, k});
    // 其他莫队做, 由于回滚较麻烦, 所以每块重新开始做, 按块分
    else
      query[id[l]].push_back({i, l, r, k});
  }

  solve();

  for (int i = 1; i <= q; i++)
    printf("%d\n", ans[i]);

  return 0;
}

大常数选手喜提用时 rk-5. 懒得截图了QAQ.

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

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