leetcode 周赛 503 第 55 名

零、背景

这次比赛最后一题稍微有点难，用到了之前很少用到的分块算法，算是万能的兜底算法了。

本场题型概览如下。
A 题：快慢指针。
B 题：统计。
C 题：贪心。
D 题：分块。

一、限制有序数组中的元素出现次数

题意：给一个有序数组，处理数组，使得相同数字最多出现 k 次。
要求：原地算法，O(1)空间。

思路：快慢指针

由于数组已经有序，统计答案最后一个数字的个数。
如果相等且个数等于 k 次，则需要忽略，否则进入答案，更新统计数据。

二、密码强度

题意：给一个字符串，不同字符有不同的得分，但每个字符的得分最多得一次分，求最终得分。

思路：统计

先使用集合统计去重，然后分别计算分数即可。

三、排序排列的最少操作数

题意：给一个数组，现在只有两个操作，问是否可以使用最少的操作把数组变为升序数组。
操作如下：
1）反转整个数组
2）数组循环左移一次。

思路：贪心

可以发现，首尾元素也算相邻时，不管怎么操作，每个元素的相邻元素都不会变化。
故数组只可能是两种情况，一种是循环升序或者循环降序，如下图所示。

如果数组是循环升序，则循环左移即可得到答案。
但是，这个答案可能不是最优的。

例如对于 1 2 ... n-1, 0 这个数组，循环左移答案是 n-1。
但是先反转数组，再左移一次，再反转数组，答案就是 3。

故，对于循环升序数组，分两种情况。
一种是直接左移，另一种是反转、左移、再反转。

而对于循环降序数组，则也一样存在两种情况。
一种是先反转再左移，另一种是先左移再反转。

这些情况分别贪心判断即可。

四、递增后的数对数量

题意：给两个数组和两个操作。
操作1：对第二个数组区间加上一个值。
操作2：询问，对于第一个数组的位置，第二个数组有多少个位置，两个位置上的数字之和等于指定值。

思路：分块

分析数据范围，第一个数组大小为 5。
显然，每次询问时单独枚举第一个数组的每个位置去求答案即可。

所以问题简化为了给一个数组，有区间加操作，问操作后数组中等于指定值的个数。

如果使用线段树来处理，区间加操作没问题，但是最后的询问无法处理。
线段树解决不了的区间问题，就只能使用万能的分块算法了。

思路：对区间划分为 sqrt(N) 个相等的子区间，则每个区间大小为 sqrt(N)。
关键优化：如果对一个完整的子区间进行操作，则使用延迟标记来 O(1)处理。

基于关键优化，来看下区间操作的复杂度。
一个区间的左端点可能没有覆盖完整的子区间，所以需要暴力扫描对应的子区间，最多循环sqrt(N)次。
对于中间的部分，都是完整覆盖子区间，所以使用延迟标记即可，最多 sqrt(N)个。
对于右端点，同样可能没有完整的覆盖子区间，也需要暴力扫描对应的子区间，最多循环sqrt(N)次。
综合，一次区间操作最多循环 3 * sqrt(N)次。

查询操作与区间操作完全一样，也是最多循环 3*sqrt(N)次。

故每次操作平均都需要 sqrt(N) 的复杂度，q 次操作，复杂度就是 q * sqrt(N)。

理论理解了，该如何分块呢？
很简单，直接对数组大小开方，即可得到一个子区间的大小 B = sqrt(n)。
有了区间大小，每个位置所属的区间就明确了 Bi = i / B。

注意事项：正常区间需要划分为左区间、中间、右区间三个区间，但存在特例，即询问的区间在一个子区间内，此时直接暴力枚举即可。

这里贴一下修改区间的代码，查询的是一样的。

void Update(const int l, const int r, const ll val) {
  int startBlock = l / blockSize;
  int endBlock = r / blockSize;
  if (startBlock == endBlock) {
    for (int i = l; i <= r; i++) {
      blocks[startBlock].cnt[nums[i]]--;
      nums[i] += val;
      blocks[startBlock].cnt[nums[i]]++;
    }
  } else {
    {  // 左半部
      int L = l;
      int R = (startBlock + 1) * blockSize - 1;
      for (int i = L; i <= R; i++) {
        blocks[startBlock].cnt[nums[i]]--;
        nums[i] += val;
        blocks[startBlock].cnt[nums[i]]++;
      }
    }
    {  // 中间
      for (int b = startBlock + 1; b < endBlock; b++) {
        blocks[b].lazy += val;
      }
    }
    {  // 右半部
      int L = endBlock * blockSize;
      int R = r;
      for (int i = L; i <= R; i++) {
        blocks[endBlock].cnt[nums[i]]--;
        nums[i] += val;
        blocks[endBlock].cnt[nums[i]]++;
      }
    }
  }
}

五、最后

这次比赛最后一题需要使用分块算法，很多年没遇到了，应该很多人不会这个算法吧。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code