图论分块 @ Wings            分类 ACM
发布于 星期四, 八月 5 日, 2021 年
更新于 星期五, 八月 6 日, 2021 年

不会暴力, 分块好难.

参考链接

介绍

$n$ 个点 $m$ 条边的无向图, $q$ 次询问, 每次修改一个点的信息, 或者查询一个点的所有相邻点的信息和. 这样的东西还真没有什么数据结构好维护. 然后就有了图论分块这种优美的暴力, 均摊复杂度 $O(q\sqrt m)$.

图论分块的核心思想是, 将度数多的点和度数少的点分类, 度数少的点暴力, 度数多的点尝试维护答案.

将度数大于 $\sqrt{2m}$ 的点分成一类, 称为重点, 其他点分为一类, 称为轻点, 那么有:

  1. 一个轻点最多和 $\sqrt{2m}$ 个点相邻
  2. 一个重点最多和 $\sqrt{2m}$ 个重点相邻

然后构造一个有向的更新关系, 轻点向和他相邻的重点连有向边, 表示这个轻点被修改后, 需要维护重点的信息; 重点向和它相邻的重点连有向边, 表示这个重点被修改后, 需要维护和它相邻的重点的信息. 那么一次修改加上维护相邻重点, 复杂度是 $O(\sqrt{2m})$ 的. 查询如果是重点, 那么已经维护过了, 直接输出答案即可; 如果是轻点, 那么暴力去算和它相邻的点的信息和即可, 轻点度数不超过 $\sqrt{2m}$, 故一次查询的复杂度也是 $O(\sqrt{2m})$, 总复杂度 $O(q \sqrt{2m}) = O(q \sqrt m)$.

这个思想就是, 如果去维护答案, 修改信息复杂度很高, 如果去维护信息, 统计答案复杂度很高, 那么找一个"平衡点", 维护一些信息, 统计一些答案, 就可以均摊下来了(好像这就是莫队的思想, 咱也不懂, 咱也不敢问).

板题

板题: HDU-4858

代码
int T, n, m, deg[MAXN], S, q, a[MAXN], sum[MAXN];
VI G[MAXN], E[MAXN];

void init() {
  for (int i = 1; i <= n; i++)
    G[i].clear(), E[i].clear(),
    deg[i] = a[i] = sum[i] = 0;
}

int query(int u) {
  if (deg[u] > S)
    return sum[u];
  int res = 0;
  for (int v : G[u])
    res += a[v];
  return res;
}

void update(int u, int d) {
  a[u] += d;
  for (int v : E[u])
    sum[v] += d;
}

void build() {
  for (int i = 1; i <= n; i++)
    for (int v : G[i]) if (deg[v] > S)
      E[i].push_back(v);
}

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &m);
    init();
    for (int i = 1; i <= m; i++) {
      int u, v;
      scanf("%d%d", &u, &v);
      G[u].push_back(v);
      G[v].push_back(u);
      deg[u]++, deg[v]++;
    }
    S = sqrt(2 * m);
    build();
    scanf("%d", &q);
    while (q--) {
      int op, u, d;
      scanf("%d%d", &op, &u);
      if (op)
        printf("%d\n", query(u));
      else {
        scanf("%d", &d);
        update(u, d);
      }
    }
  }
  return 0;
}

当然也可以维护周围点边权的信息和: HDU-4467

这道题就记录三种情况的答案. 重点记录一个 $sum(u, j)$ 表示颜色为 $j$ 的边的权值和. 修改如果是轻点, 那么遍历和它相邻的点, 如果是轻点, 那么直接更新最终答案; 如果是重点, 在更新答案的同时还需要维护 $sum$. 修改如果是重点, 由于已经维护了信息, 直接用 $sum$ 去更新答案即可.

你永远可以相信hdu评测机

这题有重边, 需要去重, 然后还要用邻接表, 否则T到起飞.

代码
struct E {
  int u, v;
  LL w;
  bool operator < (const E &E) const {
    return u == E.u ? v == E.v ? w < E.w : v < E.v : u < E.u;
  }
};
vector<E> edges0;

struct Edge {
  int to, next;
  LL w;
} edges[2][MAXN<<1];
int head[2][MAXN], mm[2];

void addEdge(int g, int u, int v, LL w) {
  edges[g][++mm[g]] = {v, head[g][u], w};
  head[g][u] = mm[g];
}

void addNet(int g, int u, int v, LL w) {
  addEdge(g, u, v, w);
  addEdge(g, v, u, w);
}

int n, m, c[MAXN], deg[MAXN], S, q;
LL ans[5], sum[MAXN][5];

int getAnsId(int a, int b) {
  return a + b;
}

void init() {
  edges0.clear();
  mm[0] = mm[1] = 0;
  ans[0] = ans[1] = ans[2] = 0;
  for (int i = 1; i <= n; i++)
    deg[i] = sum[i][0] = sum[i][1] = 0,
    head[0][i] = head[1][i] = 0;
}

void build() {
  for (int u = 1; u <= n; u++)
    for (int i = head[0][u]; i; i = edges[0][i].next) {
      Edge &e = edges[0][i];
      if (deg[e.to] > S)
        addEdge(1, u, e.to, e.w);
    }
}

void update(int u) {
  c[u] ^= 1;
  for (int i = head[1][u]; i; i = edges[1][i].next) {
    Edge &e = edges[1][i];
    sum[e.to][c[u]] += e.w;
    sum[e.to][c[u]^1] -= e.w;
  }
  if (deg[u] <= S) {
    for (int i = head[0][u]; i; i = edges[0][i].next) {
      Edge &e = edges[0][i];
      ans[getAnsId(c[u], c[e.to])] += e.w;
      ans[getAnsId(c[u]^1, c[e.to])] -= e.w;
    }
  }
  else {
    ans[getAnsId(c[u], 0)] += sum[u][0];
    ans[getAnsId(c[u]^1, 0)] -= sum[u][0];
    ans[getAnsId(c[u], 1)] += sum[u][1];
    ans[getAnsId(c[u]^1, 1)] -= sum[u][1];
  }
}

int main() {
  int kase = 0;
  while (scanf("%d%d", &n, &m) != EOF && ++kase) {
    printf("Case %d:\n", kase);
    init();
    for (int i = 1; i <= n; i++)
      scanf("%d", c+i);
    for (int i = 1; i <= m; i++) {
      int u, v;
      LL w;
      scanf("%d%d%lld", &u, &v, &w);
      if (u > v)
        swap(u, v);
      edges0.push_back({u, v, w});
    }

    sort(edges0.begin(), edges0.end());
    for (int i = 0, j; i < m; i = j) {
      for (j = i + 1; j < m && edges0[i].u == edges0[j].u && edges0[i].v == edges0[j].v; j++)
        edges0[i].w += edges0[j].w;
      addNet(0, edges0[i].u, edges0[i].v, edges0[i].w);
      deg[edges0[i].u]++, deg[edges0[i].v]++;
      ans[getAnsId(c[edges0[i].u], c[edges0[i].v])] += edges0[i].w;
    }

    S = sqrt(m * 2);
    build();
    for (int u = 1; u <= n; u++)
      for (int i = head[1][u]; i; i = edges[1][i].next) {
        Edge &e = edges[1][i];
        sum[e.to][c[u]] += e.w;
      }
    scanf("%d", &q);
    while (q--) {
      char str[10];
      scanf("%s", str);
      if (str[0] == 'A') {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%lld\n", ans[getAnsId(a, b)]);
      }
      else {
        int u;
        scanf("%d", &u);
        update(u);
      }
    }
  }
  return 0;
}

还可以用数据结构维护重点的相邻点信息和, 比如 HDU-6756

写不动了, 咕咕咕.

第二天填坑, 还是写得动的^_^

这道题就是轻点暴力找mex, 重点需要用数据结构维护, 求mex. 这里有一个很神奇的操作, 对每个重点开一颗权值为它的度数+1的权值树状数组, $x$ 位为 $1$ 表示 $x-1$ 在它的周围出现过(树状数组下标从 $1$ 开始, 所以这里要整体平移一下), 并不需要管大于度数+1的数, 因为它不可能是mex, 等于度数的数其实也不用放进去, 因为前面填满就是0到度数-1, 填满了可以直接判, 如果出现等于度数的数, 那么前面一定没有填满. 假设 $mex = p$, 那么 $\forall x < p, presum(x) = x, \forall y \ge p, presum(y) < y$, 满足单调性, 可以二分. 这样查询一个重点的复杂度是 $O(\log m)$. 查询轻点就暴力, 复杂度 $O(\sqrt{2m}) = O(\sqrt m)$. 修改还是需要维护重点, 由于维护的是树状数组, 所以复杂度是 $O(\sqrt {2m} \log m) = O(\sqrt m \log m)$. 总复杂度 $O(q \sqrt m \log m)$

代码

为方便这里把 cnt 放进了 bit 结构体内

struct BIT {
  VI t, cnt;
  int n;
  void init(int _n) {
    n = _n+1;
    t.clear(), cnt.clear();
    t.resize(n+1, 0), cnt.resize(n+1, 0);
  }
  /* 单点修改(加) */
  void update(int pos, int x) {
    for (int i = pos; i <= n; i += lowbit(i))
      t[i] += x;
  }
  /* 查询前缀和 */
  int presum(int pos) {
    int res = 0;
    for (int i = pos; i; i -= lowbit(i))
      res += t[i];
    return res;
  }
  /* 查询区间[l, r]的和 */
  int query(int l, int r) {
    return presum(r) - presum(l-1);
  }

  void add(int x) {
    if (++cnt[x] == 1)
      update(x+1, 1);
  }

  void del(int x) {
    if (--cnt[x] == 0)
      update(x+1, -1);
  }

  int getMex() {
    int l = 1, r = n, res = 1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (presum(mid) < mid)
        res = mid, r = mid - 1;
      else
        l = mid + 1;
    }
    return res-1;
  }

} bit[MAXN];

int T, n, m, a[MAXN], deg[MAXN], S, ans[MAXN], idx, q;
VI G[MAXN], E[MAXN];

void init() {
  for (int i = 1; i <= n; i++)
    G[i].clear(), E[i].clear(),
    deg[i] = 0;
}

void build() {
  for (int u = 1; u <= n; u++)
    for (int v : G[u]) if (deg[v] > S)
      E[u].push_back(v);
}

void update(int u, int x) {
  for (int v : E[u]) if (a[u] < deg[v])
    bit[v].del(a[u]),
    bit[v].add(x);
  a[u] = x;
}

int tmp[MAXN];
int query(int u) {
  if (deg[u] > S)
    return bit[u].getMex();
  else {
    for (int i = 0; i <= deg[u]; i++)
      tmp[i] = 0;
    for (int v : G[u]) if (a[v] < deg[u])
      tmp[a[v]]++;
    for (int i = 0; i <= deg[u]; i++)
      if (!tmp[i])
        return i;
    return deg[u];
  }
}

int main() {
#ifdef GDB
  freopen("X.in", "r", stdin);
  freopen("X.out", "w", stdout);
#endif
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &m);
    init();
    for (int i = 1; i <= n; i++)
      scanf("%d", a + i);
    for (int i = 1; i <= m; i++) {
      int u, v;
      scanf("%d%d", &u, &v);
      G[u].push_back(v);
      G[v].push_back(u);
      deg[u]++, deg[v]++;
    }
    S = sqrt(2 * m);
    build();
    for (int u = 1; u <= n; u++) if (deg[u] > S)
      bit[u].init(deg[u]);
    for (int u = 1; u <= n; u++)
      for (int v : E[u]) if (a[u] < deg[v])
        bit[v].add(a[u]);
    scanf("%d", &q);
    while (q--) {
      int op, u, x;
      scanf("%d%d", &op, &u);
      if (op == 1) {
        scanf("%d", &x);
        update(u, x);
      }
      else
        printf("%d\n", query(u));
    }
  }
  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