2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)

tiger2005 · 2023-10-02 20:54:51 · 个人记录

比赛在这里。题解按照难度排序。

I - Absolute Game

从 Bob 的视角参考这个游戏。能不能做到保留距离最终的 x 最近的 y 呢？答案是肯定的。

我们对 Alice 手中的数组 a 中每一个元素 a_i 找到使得 |a_i - b_j| 最小的 j，然后称 b_j 被 a_i 绑定。假设在一轮中，双方的数组均剩余 N 个元素，此时 Alice 取走了一个元素，考虑 Bob 手中的 N 个元素，由于此时 Alice 手中只有 N - 1 个元素，那么必然有至少一个元素没有被绑定，取出一个即可。

在这种策略下，最终剩余的 y 被 x 绑定，自然达到 Bob 期望的最小化 |x - y| 的想法。Alice 自然知道 Bob 的这道思路，所以也只能尽量选取 i 使得 \min_{j=1}^{n} |a_i - b_j| 最大。我们就得到了答案。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int ans = 0;
  int n; cin >> n;
  vector<int> a(n), b(n);
  for (auto &e: a)
    cin >> e;
  for (auto &e: b)
    cin >> e;
  for (int i = 0; i < n; i ++) {
    int u = 1e9;
    for (int j = 0; j < n; j ++)
      u = min(u, abs(a[i] - b[j]));
    ans = max(ans, u);
  }
  printf("%d", ans);
  return 0;
}

J - Graph and Cycles

考虑 f(e_i, e_{i+1})，发现取出的两条路径共点，因此考虑将贡献转移到点上考虑。

对于每个点，存在 n - 1 条出边。根据环的特性，这些边必然被两两分组，一组中的两条边在某个环路径上相邻，带来 f 函数创造的贡献。

为了使得这个贡献最小，考虑将权值最低和次低的边分为一组，以此类推。这显然给我们带来最少的贡献，而由于环的特性，任何一种分组都是可行的，故对每个点计算两两一组的边权最大值的和即可。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n; cin >> n;
  vector v(n + 1, vector<int>());
  long long ans = 0;
  for (int i = 1, a, b, c; i <= (n * (n - 1) / 2); i ++) {
    cin >> a >> b >> c;
    v[a].emplace_back(c);
    v[b].emplace_back(c);
  }
  for (int i = 1; i <= n; i ++) {
    auto &vec = v[i];
    sort(vec.begin(), vec.end());
    for (int i = 1; i < n; i += 2)
      ans += vec[i];
  }
  printf("%lld\n", ans);
  return 0;
}

D - Cycle String?

分类讨论，难点在读懂题目在写啥。

首先考虑将 s 从小到大排序得到 s'。不难发现，只要所有字母出现的次数都不超过 n，那么 s' 就是一个符合题意的字符串。

否则存在一个“众字符”，在源字符串中出现了至少 n + 1 次。我们考虑把其中 n 个字符拿出来，然后把剩余的也拿出来，得到两个只含一种字符的字符串。不难发现，如果能在中间 两个区域 随便塞其他字符，就能达到目的。“两个”是因为串是循环的。

有一个 corner case：对于出现了 2n - 2 个 a 和 2 个 b 类型的情况，是不存在解的。判一下这个就做完了。

#include <bits/stdc++.h>
using namespace std;

int main() {
  string s; cin >> s;
  vector<int> cnt(26);
  for (auto e: s)
    ++ cnt[e - 'a'];
  vector<pair<int, int>> vp;
  for (int i = 0; i < 26; i ++) if (cnt[i])
    vp.emplace_back(cnt[i], i);
  int n = s.size() / 2;
  sort(vp.begin(), vp.end());
  reverse(vp.begin(), vp.end());
  if (vp[0].first <= n) {
    puts("YES");
    sort(s.begin(), s.end());
    printf("%s\n", s.c_str());
  }
  else if (vp[0].first >= 2 * n - 1) {
    puts("NO");
  }
  else if (vp[0].first == 2 * n - 2) {
    if (vp[1].first == 2)
      puts("NO");
    else {
      puts("YES");
      printf("%s", string(n - 1, vp[0].second + 'a').c_str());
      putchar(vp[1].second + 'a');
      printf("%s", string(n - 1, vp[0].second + 'a').c_str());
      putchar(vp[2].second + 'a');
    }
  }
  else {
    puts("YES");
    vector<int> rst;
    auto [num, ch] = vp[0];
    for (int i = 1; i < (int)vp.size(); i ++) {
      auto [_num, _ch] = vp[i];
      while (_num --)
        rst.push_back(_ch);
    }
    int lst = 0, ptr = 0;
    for (int i = 1; i <= 2 * n; i ++) {
      if (num != 0 && lst != n) {
        ++ lst;
        -- num;
        putchar('a' + ch);
      }
      else {
        lst = 0;
        putchar(rst[ptr ++] + 'a');
      }
    }
  }
  return 0;
}

F - Game on a Tree

有人以为只考虑父亲和儿子，导致交了贼多发错解。

考虑在祖先后代图上找一个最大匹配。如果能找到完美匹配的话，那么 Bob 将会稳操胜券——只要 Alice 这一步到达一个地方，Bob 只需要取到最大匹配上对应的位置即可。

问题来到了最大匹配不为完美匹配的部分，假设 Alice 手中有一个最大匹配，那么只需要选择一个没有被匹配的点起手即可。随后 Bob 就会在匹配里遇到和前面一样的问题——Bob 跳到哪里，Alice 只需要跳到最大匹配上的对应点即可。

Bob 可以跳到一个没有被匹配的点吗？不妨假设的确存在这么一种情况 x \to a_1 \to b_1 \to \cdots \to b_k \to y，其中 (a_i, b_i) 代表一个匹配，而 x 和 y 都没有被匹配。注意到祖先后代关系是相互的，那么考虑如下匹配：

(x, a_1), (b_1, a_2), \cdots, (b_k, y)

自然也是一个符合条件的匹配，同时比原先的匹配还多一个，和“最大匹配”的假设形成冲突。故 Bob 无法跳出最大匹配，胜利的人自然就是 Alice 了。

#include <bits/stdc++.h>
using namespace std;

vector<int> g[100010];

int main() {
  int n; cin >> n;
  for (int i = 1, a, b; i < n; i++) {
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  auto dfs = [&] (auto self, int x, int f) -> int {
    int cnt = -1;
    for (auto v: g[x]) if (v != f)
      cnt += self(self, v, x);
    return abs(cnt);
  };

  puts(!dfs(dfs, 1, -1) ? "Bob" : "Alice");
  return 0;
}

G - Projection

首先考虑最多的部分。对于空间上的一个位置，只要两个投影方向上都存在阴影，那么在这里放一个方块显然是可行的，也会尽可能满足阴影的限制。当然，其他位置显然都是不能放的，所以这形成了最大的方块序列。判定无解也只需要对这个序列判断。

接下考虑最少的部分。逐层考虑，每一层根据如下方式填入方块即可：

  - - -
| X  
| X  
| X  
|   X 
|     X

上面展示了一层中左侧投影块数多于后侧投影块数的构造方法，反之亦然。

#include <bits/stdc++.h>
using namespace std;

int n, m, h;
char A[110][110], B[110][110];
bool sdwa[110][110], sdwb[110][110];

int main() {
  scanf("%d%d%d", &n, &m, &h);
  for (int i = 1; i <= n; i ++)
    scanf(" %s", A[i] + 1);
  for (int i = 1; i <= n; i ++)
    scanf(" %s", B[i] + 1);
  vector<tuple<int, int, int>> vmax, vmin;
  for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= m; j ++) if (A[i][j] == '1') {
      for (int k = 1; k <= h; k ++) if (B[i][k] == '1')
        vmax.emplace_back(i, j, k);
    }

  for (auto [a, b, c]: vmax)
    sdwa[a][b] = sdwb[a][c] = true;
  for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= m; j ++)
      if (sdwa[i][j] != A[i][j] - '0')
        return puts("-1"), 0;

  for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= h; j ++)
      if (sdwb[i][j] != B[i][j] - '0')
        return puts("-1"), 0;

  for (int i = 1; i <= n; i ++) {
    vector<int> pos1, pos2;
    for (int j = 1; j <= m; j ++)
      if (A[i][j] == '1')
        pos1.emplace_back(j);
    for (int j = 1; j <= h; j ++)
      if (B[i][j] == '1')
        pos2.emplace_back(j);
    for (int j = 0; j < (int)max(pos1.size(), pos2.size()); j ++) {
      int p1 = (int)pos1.size() - 1 - j;
      int p2 = (int)pos2.size() - 1 - j;
      p1 = max(p1, 0);
      p2 = max(p2, 0);
      vmin.emplace_back(i, pos1[p1], pos2[p2]);
    }
  }

  sort(vmax.begin(), vmax.end());
  sort(vmin.begin(), vmin.end());
  printf("%d\n", (int)vmax.size());
  for (auto [a, b, c]: vmax)
    printf("%d %d %d\n", a - 1, b - 1, c - 1);
  printf("%d\n", (int)vmin.size());
  for (auto [a, b, c]: vmin)
    printf("%d %d %d\n", a - 1, b - 1, c - 1);

  return 0;
}

E - Life Transfer

汽车显然是一个老玩家带一些小孩。

考虑枚举用几辆车，假设为 x 辆，那么我们肯定会让最老的 x 个人开车搭载最小的 (k-1)x 个人。对于需要开车或者开摩托的人，需要根据对年龄的需求分为“获得年龄”和“贡献年龄”两种，那么对于一种情况，只需要判断：

没有人需要获得超过 d 岁的年龄；
贡献年龄的总和不少于获得年龄的总和。

不要忘了坐车的人也能贡献年龄。最后记得给全部坐车的部分判断一下。

#include <bits/stdc++.h>
using namespace std;

int n, k;

int lc, pc, lm, pm, t, d;
int a[100010];

int main() {
  cin >> n >> k >> lc >> pc >> lm >> pm >> t >> d;
  for (int i = 1; i <= n; i ++)
    cin >> a[i];
  sort(a + 1, a + n + 1);

  int L = 1, R = n;
  long long ans = -1;
  multiset<int> Lpos, Rpos;
  long long lsum = 0, rsum = 0;
  auto check = [&] () {
    if (Lpos.empty())
      return true;
    if (*Lpos.rbegin() > d)
      return false;
    return lsum <= rsum;
  };

  auto upd = [&] (long long v) {
    if (ans == -1)
      ans = v;
    else
      ans = min(ans, v);
  };

  auto addP = [&] (int x, int lmt = lm) {
    if (x < lmt) {
      x = lmt - x;
      Lpos.insert(x);
      lsum += x;
    }
    if (x > lmt) {
      x -= lmt;
      x = min(x, d);
      Rpos.insert(x);
      rsum += x;
    }
  };

  auto remP = [&] (int x, int lmt = lm) {
    if (x < lmt) {
      x = lmt - x;
      Lpos.erase(Lpos.find(x));
      lsum -= x;
    }
    if (x > lmt) {
      x -= lmt;
      x = min(x, d);
      Rpos.erase(Rpos.find(x));
      rsum -= x;
    }
  };

  long long cur = 0;
  for (int i = 1; i <= n; i ++)
    addP(a[i], lm);

  while (L - 1 <= R) {
    if (check())
      upd(cur + 1ll * (R - L + 1) * pm + lsum * t);
    if (L - 1 == R)
      break;
    remP(a[R], lm);
    addP(a[R --], lc);
    for (int c = 1; c < k && L <= R; c ++) {
      remP(a[L], lm);
      addP(a[L ++], 1);
    }
    cur += pc;
  }

  printf("%lld", ans);
  return 0;
}

B - Level Up

显然是一个 DP 题。

首先考虑第一天的策略。众所周知，按照经验值从小到大的顺序执行任务，显然更容易达成可控的经验溢出。所以我们可以得到一个 DP 顺序——将所有任务按照 x 值从小到大排列，然后钦定第一个等级按照此顺序完成任务。

对于两个等级执行的任务序列，显然需要共同考虑，对每个新的元素考虑是放弃，还在放在这两个序列中的一个。

定义状态 f_{e,i,j} 表示考虑前 e 个元素，第一个等级还差 i > 0 个经验，第二天还差 j 个经验的最少时间；g_{e,j} 代表考虑前 e 个元素，第一个等级已经完成，第二个等级中包括溢出的经验和完成任务得到的经验，还差 j 个经验的最少时间。e 维度显然需要滚动掉（甚至完全不需要滚动）。

具体的转移在下方的代码中，我认为足够清晰了。

#include <bits/stdc++.h>
using namespace std;

int n, s1, s2;
int x[510], t[510], y[510], r[510];

long long f[510][510], g[510];

int main() {
  scanf("%d%d%d", &n, &s1, &s2);
  for (int i = 1; i <= n; i ++)
    scanf("%d%d%d%d", &x[i], &t[i], &y[i], &r[i]);
  // x[i] increasing
  for (int i = 1; i <= n; i ++)
    for (int j = i + 1; j <= n; j ++) if (x[i] >= x[j])
      swap(x[i], x[j]), swap(y[i], y[j]), swap(t[i], t[j]), swap(r[i], r[j]);

  memset(f, 0x3f, sizeof f);
  memset(g, 0x3f, sizeof g);
  long long INF = g[0];
  f[s1][s2] = 0;
  for (int i = 1; i <= n; i ++) {
    // g -> g
    for (int j = 0; j <= s2; j ++) {
      int tow = max(0, j - y[i]);
      g[tow] = min(g[tow], g[j] + r[i]);
    }
    // f -> f/g
    for (int p = 1; p <= s1; p ++)
      for (int q = 0; q <= s2; q ++) {
        // use as g
        {
          int tow = max(0, q - y[i]);
          f[p][tow] = min(f[p][tow], f[p][q] + r[i]);
        }
        // use as f
        if (p > x[i])
          f[p - x[i]][q] = min(f[p - x[i]][q], f[p][q] + t[i]);
        else {
          int overf = x[i] - p;
          int tow = max(0, q - overf);
          g[tow] = min(g[tow], f[p][q] + t[i]);
        }
      }
  }

  printf("%lld\n", g[0] == INF ? -1 : g[0]);
  return 0;
}

C - Find the Array

卡密题目。

首先考虑获得一些元素 S 相对于某个元素 a_p 的差值，显然只需要分别查询 S 和 S \cup \{p\} 的相对差值集合，然后相减即可。

假设我们拥有一个元素 a_{pv}，并保证其是数组的最大值或者最小值。只需要考虑如何根据上述信息获得每个元素相当于 a_{pv} 的差值。

考虑二进制分组，每一组 S_u 储存了 [1,n] 中不等于 pv，且二进制位上第 u 位为 1 的位置集合。

我们可以直接利用这些元素相对于 a_{pv} 的差值得到我们想要的结果。假设对 S_{1..4}，查询结果为 M_{1..4}，考虑第 5 个位置，这个差值显然在 M_1 和 M_3 中，而不在 M_2 和 M_4 中。由于二进制的性质，这些性质足以锁定这个位置的元素和 a_{pv} 的差。这一部分预计会使用 16 次询问 2，另加 2 次询问 1 获取极值和相对方向。

接下来考虑如何得到一个 pv。首先询问全集的相对差值集合，得到极差 d，然后只需要二分出使得 [1, p] 集合的相对差值集合存在 d 的最小 p，就能找到最大值和最小值中出现在右侧的值对应的位置，也就得到了一个 pv。这一部分预计会使用 8+1 次询问 2。

#include <bits/stdc++.h>
using namespace std;

vector<int> ask2(vector<int> v) {
  if (v.size() <= 1)
    return {};
  int n = v.size();
  printf("2 %d", n);
  for (auto e: v)
    printf(" %d", e);
  puts("");
  fflush(stdout);
  vector<int> res;
  for (int i = n * (n - 1) / 2, a; i > 0; i --) {
    scanf("%d", &a);
    res.push_back(a);
  }
  return res;
}

int ask1(int x) {
  printf("1 %d\n", x);
  fflush(stdout);
  scanf("%d", &x);
  return x;
}

pair<vector<int>, vector<int>> half(vector<int> x) {
  vector<int> v1, v2;
  bool flg = false;
  for (auto e: x) {
    (flg ? v2 : v1).push_back(e);
    flg ^= 1;
  }
  return {v1, v2};
}

int delta(vector<int> v) {
  if (v.empty())
    return 0;
  return *max_element(v.begin(), v.end());
}

vector<int> merge(vector<int> v1, vector<int> v2) {
  for (auto e: v2)
    v1.push_back(e);
  return v1;
}

vector<int> cross(vector<int> v1, vector<int> v2) {
  vector<int> res{};
  int ptr = 0;
  for (auto e: v1) {
    while (ptr != (int)v2.size() && v2[ptr] < e)
      ++ ptr;
    if (ptr < (int)v2.size() && v2[ptr] == e)
      res.push_back(e), ++ ptr;
  }
  return res;
}

vector<int> removal(vector<int> v1, vector<int> v2) {
  vector<int> res{};
  int ptr = 0;
  for (auto e: v2) {
    while (ptr != (int)v1.size() && v1[ptr] < e)
      res.push_back(v1[ptr ++]);
    if (ptr < (int)v1.size() && v1[ptr] == e)
      ++ ptr;
  }
  while (ptr != (int)v1.size())
    res.push_back(v1[ptr ++]);
  return res;
}

int n;

int main() {
  scanf("%d", &n);
  if (n == 1) {
    printf("3 %d\n", ask1(1));
    fflush(stdout);
    return 0;
  }
  vector<int> who_asked;
  for (int i = 1; i <= n; i ++)
    who_asked.push_back(i);
  int d = delta(ask2(who_asked));

  int bound = 0;

  {
    int l = 1, r = n, m;
    while (l < r - 1) {
      m = (l + r) >> 1;
      vector<int> v;
      for (int i = 1; i <= m; i ++)
        v.push_back(i);
      if (delta(ask2(v)) == d)
        r = m;
      else
        l = m;
    }
    bound = r;
  }

  int l = 0;
  while ((1 << l) <= n)
    l ++;

  vector basic(l, vector<int>());

  for (int i = 0; i < l; i ++) {
    vector<int> wt;
    for (int j = 1; j <= n; j ++) if (j != bound && ((j >> i) & 1))
      wt.push_back(j);
    auto v1 = ask2(wt);
    wt.push_back(bound);
    auto v2 = ask2(wt);
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    basic[i] = removal(v2, v1);
  }

  vector<int> D(n + 1);
  for (int i = 1; i <= n; i ++) if (i != bound) {
    vector<int> u;
    for (int j = 0; j < l; j ++) if ((i >> j) & 1) {
      if (u.empty())
        u = basic[j];
      else
        u = cross(u, basic[j]);
    }
    for (int j = 0; j < l; j ++) if (!((i >> j) & 1))
      u = removal(u, basic[j]);
    assert(u.size() == 1);
    D[i] = u[0];
  }

  int final = ask1(bound == 1 ? 2 : 1);
  int bval = ask1(bound);
  int direct = (bval > final) ? -1 : 1;
  printf("3 ");
  for (int i = 1; i <= n; i ++)
    printf("%d ", D[i] * direct + bval);
  puts("");
  fflush(stdout);
  return 0;
}

A - Max or Min

先对三种值进行讨论，假设为 -1，0 和 1，并且目标是全部变成 0。

操作过程中抹去一个 0 显然不会更优，因此考虑破环为链，对相邻两个 0 之间的部分考虑即可。

对于中间这部分只包含 -1 和 1 的串，对所有情况进行考虑可以找到一个重要的分析量——“跳变”。对相邻两个元素，如果两者不相同，则认为产生一个“跳变”。如果将跳变记为 1，不跳变记为 0，那么就会产生一个 01 串。

接下考虑对这个 01 串进行操作会发生什么（01 串为空时代表两个 0 之间夹着一个 -1 或者 1，显然通过一步操作就能替换为 0）：

将原先序列中最左边和最右边的元素变成 0，等价于去除这个串中左侧或者右侧的一个字符，需要保证这个字符是 0；
在边缘处将 0, 1, -1 类型变为 0, 1, 1 类型，区别是前者不能将中间部分换为 0，而后者可以。这个操作会将这个串中左侧或者右侧的 1 换成 0；
在中间部分将 1, -1, 1 类型变成 1, 1, 1 类型，在串中相当于把两个相邻的 1 变成 0；
在中间部分将 1, 1, -1 类型变成 1, -1, -1 类型，相当于在串中把 01 和 10 互相转换，或者把 1 位移了一下。

考虑在每次操作后自动执行第一个操作，保证左边和右边卡着一个 1，或者成功清空。那么只需要考虑把这个串中的 1 全部变成 0 的时间。

不难发现，第四个操作效率极低，只是交换 1 和 0，没有进行消除。事实上，这个移动显然需要用在将两个 1 靠拢起来才具有占优的可能，但是“挪至少一位，然后两个一起消除”所需的步数至少也得是 2，甚至不如一个个把 1 消掉，故我们断言——操作四啥用没有。

通过前面的讨论，我们知道：只要能合理分配操作的顺序，其实操作二中对 1 位置的限制完全不必要，那么对于一个连续的、长度为 l 的全 1 串，所需的步数就等于 \lceil \dfrac l 2 \rceil！

故只需要时刻维护这个跳变字符串（这个串只会发生最多 4n 次单个位置的变化），通过 Tag 上传在线段树上维护区间答案即可。

代码中对 Tag 的设计利用的是状态自动机，当然也可以用普通的设计思路考虑细节。

#include <bits/stdc++.h>
using namespace std;

vector<int> idx[200010];

int n, m;
int y[400010];
struct Tag {
  pair<int, char> forw[3];
  Tag() {
    for (int i = 0; i < 3; i ++)
      forw[i] = {0, i};
  }
  Tag operator + (const Tag &t) const {
    Tag res;
    for (int i = 0; i < 3; i ++) {
      auto [num, pos] = forw[i];
      auto [num2, pos2] = t.forw[(int)pos];
      res.forw[i] = {num + num2, pos2};
    }
    return res;
  }
  int get() {
    auto &[n, p] = forw[0];
    return n + (p != 0);
  }
} tr[1600010];

Tag one, zero;
void pu(int x) {
  tr[x] = tr[x << 1] + tr[x << 1 | 1];
}

void mdf(int x, int l, int r, int p, int k) {
  if (l == r)
    return tr[x] = (k == 0 ? zero : one), void();
  int m = (l + r) >> 1;
  if (p <= m)
    mdf(x << 1, l, m, p, k);
  else
    mdf(x << 1 | 1, m + 1, r, p, k);
  pu(x);
}
Tag que(int x, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr)
    return tr[x];
  int m = (l + r) >> 1;
  Tag res;
  if (ll <= m)
    res = que(x << 1, l, m, ll, rr);
  if (rr > m)
    res = res + que(x << 1 | 1, m + 1, r, ll, rr);
  return res;
}
void bul(int x, int l, int r) {
  if (l == r)
    return tr[x] = zero, void();
  int m = (l + r) >> 1;
  bul(x << 1, l, m);
  bul(x << 1 | 1, m + 1, r);
  pu(x);
}

int main() {
  zero.forw[0] = {0, 0};
  zero.forw[1] = zero.forw[2] = {1, 0};
  one.forw[0] = {0, 1};
  one.forw[1] = {0, 2};
  one.forw[2] = {1, 1};
  cin >> n >> m;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i ++)
    cin >> a[i], idx[a[i]].push_back(i);
  for (int i = 1; i <= 2 * n; i ++)
    y[i] = 1;

  auto cover = [&] (int p) {
    y[p] = -1;
    if (p != 1)
      mdf(1, 1, 2 * n - 1, p - 1, y[p] != y[p - 1]);
    if (p != 2 * n)
      mdf(1, 1, 2 * n - 1, p, y[p] != y[p + 1]);
  };
  bul(1, 1, 2 * n - 1);

  for (int i = 1; i <= m; i ++) {
    if (idx[i].empty()) {
      printf("-1 ");
      continue;
    }
    auto &iv = idx[i];
    int ans = n - (int)iv.size();
    for (int p = 0; p < (int)iv.size(); p ++) {
      int l = iv[p], r = iv[(p + 1) % iv.size()];
      if (r <= l)
        r += n;
      if (l + 1 <= r - 2) {
        Tag res = que(1, 1, 2 * n - 1, l + 1, r - 2);
        ans += res.get();
      }
    }
    printf("%d ", ans);
    for (auto e: iv) {
      cover(e);
      cover(e + n);
    }
  }

  return 0;
}