课程安排

题目链接：

[传智杯 #2 决赛] 课程安排 - 洛谷

---

题目描述

传智播客的课表上按顺序提供 $n$ 节课程，课程可能是 Java、Python 或者前端开发等等，我们用不超过 $n$ 的正数代表每一节课程的种类。学员可以从这个课程序列选取连续的一小段的课程序列，作为一周的学习任务。

为了使学习任务不那么枯燥，学员不想连续上两节相同的课。特殊的，这一周学习任务的开头和结尾也不能是相同的课。为了保证学习效果，一周内至少要学完 $l$ 节课程。

请问，我们有多少种合法的选课方案？

两种选课方案，只要选取的课程序列在原序列的开头和结尾有至少一个位置不一致，那么就可以认为是不同的选课方案。注意，即使 $l$ 是 1，一周只安排一次课也是不合法的，至少需要安排 2 次课。

输入格式

每个测试点由多组数据组成。

第一行为一个整数 $T$，代表数据的组数。

对于每组数据，第一行输入两个正整数 $n$ 和 $l$。接下来一行输入 $n$ 个非负整数 $c_i$ 表示课程种类编号。

输出格式

对于每组数据，输出一行一个数，表示方案数。

样例 #1

样例输入 #1

2
3 1
1 2 3
5 3
1 2 3 1 1

样例输出 #1

3
2

提示

样例解释

对于第一组数据，有 [1,2] 和 [2,3] 和 [1,2,3] 三种方法。

对于第二组数据，由于至少要选 3 门课，只有 [1,2,3] 和 [2,3,1] 两种方法。

数据范围

测试数据不超过 5 组，$1\le N \le 5 \times 10^5$，$1\le l,c_i \le N$

---

题解

以下 l 均为左指针，k为题目中说的 l ，及课程长度。

• 本人错误写法1：

  枚举左端点 l ，双指针找出最后一个 r ，满足 [ l , r ] 中没有两个连续的相同课的位置且 $C_r$ 不等与 $C_l$。显然这样是错的。例如 [ 1 , 2 , 3 , 1 , 2 ] 会在 r=4 结束而不会往后。

• 本人错误写法2：

  枚举左端点 l ，双指针找出最后一个 r ，满足 [ l , r ] 中没有两个连续的相同课的位置，在这期间统计与 $C_l$ 相等且被课程数量满足题目要求数量的个数，在最后统计时减去。这样做如果 r 不重新回到 l 开始统计会导致后面在计数是漏掉一部分情况，例如 [ 1 , 2 , 3 , 2 , 1 , 1 ] 时无法正确计算前指针为 2 的个数，会漏掉。但是如果将 r 重新回到 l 开始计数会导致超时的问题。

• 正解：

  枚举左端点 l ，双指针找出最后一个 r ，满足 [ l , r ] 中没有两个连续的相同课的位置。额外开一个数组 a ，记录下长度满足条件后的所有的课程数目。

  

  例如上面的图片，我们扫完第一遍后得出 a 的数组如下，当 l 向后移动一位时 l + k -1 不在我们需要特殊判断的头尾是否相等的范围内，所以在做完时只需将 a [ l + k - 1 ] - 1 即可。

  完整代码：

  #include <bits/stdc++.h>
  using namespace std;
  #define endl '\n';
  typedef long long ll;
  
  int c[500005] = {0};
  int a[500005] = {0};
  
  void solve()
  {
      int n, k;
      cin >> n >> k;
      for (int i = 1; i <= n; i++)
      {
          cin >> c[i];
      }
      k = max(2, k);
      ll sum = 0;
      int l = 1, r = l;
      while (l <= n)
      {
          r = max(l, r);
  
          while (c[r + 1] != c[r] && r < n)
          {
              r++;
              if (r - l + 1 >= k)
              {
                  a[c[r]]++;
              }
          }
          if (r - l + 1 >= k)
          {
              sum = sum + r - l + 1 - k + 1 - a[c[l]];
              a[c[l + k - 1]]--;
          }
          l++;
      }
      cout << sum << endl;
      return;
  }
  
  int main()
  {
      ios::sync_with_stdio(false);
      cin.tie(0);
      cout.tie(0);
      int t;
      cin >> t;
      while (t--)
      {
          solve();
      }
      return 0;
  }