Codeforces Round 1021

https://codeforces.com/contest/2097

D Maximum Polygon

01字符串s, s=[left s][right s] 二分字符串长度

• f(s): left s xor= right s
• f(s): right s xor= left s
• f(left s)
• f(right s)

每次操作4选1

给定s, t 问能否使得 s经过若干次操作后变为t, 只需要yes/no

len <= 1e6

2s

我的思路

首先如果长度是2的幂次, 01 <-> 11 <-> 01, 只要非零就可以变为其它

• 长度4: 00+非零 -> 非零+非零 -> 01 + 01 ->(任意非零) -> 00 + 01 -> 00+(任意非零)

也就是 如果长度2的幂次，那么任意非零串之间相互转化

---

如果不是2的幂次, n = 2^t * m, 其中m 是奇数，t整数

那么就是看成2^t 的 二进制下m位的数操作

我想的是操作有对称性，有没有办法设计一个norm去算，然后想了好久没想出来

题解

我们可以得到任何 线性(xor)等价的 xor基组

证明: 对于长度2, [a,b] => [a,a+b] => [b,a+b] => [b,a] => [a+b,a] => [a+b,b] => [a,b] 全部都可以得到

对于长度4: [a,b,c,d] :

• 显然可以把a单独的放到b,
• 而放到c, 注意到 在不对c,d内部操作时，调整左边可以得到, [a+b,a] 和 [b,a], 这两个给右边就可以得到[a,b,c+a,d]
• 类似的放到d, 只需要左边得到 [a,a+b] 和[a,b] 即可 [a,b,c,d+a]

归纳法

• [a…..] 放到右边 […..]
  • 如果是和a同位置，则 [a+b a …….] 和 [b a …….]
  • 如果是和a不同位置，则 [a,b,c,…] 和 [a,b,c,…,+a,…]

由此我们得到了 线性等价，那么剩下就是高斯消元的实现就好

E Clearing the Snowdrift

给定数组 a[1..n]

一次操作，选择连续的长度不超过d 的一段, 使得这段的max值减1

问需要最少多少操作，让a变为全0

n 5e5

ai 1e9

2s

我的思路

如果没有限制d，那么每次选择全区间，ans = max ai

为啥，我觉得贪心就好了，要操作最大的值时，那么让区间选择的左端和最大值对齐，是一个不会更差的方案？

然后离散处理一下ai的值

好像 效率不够

当前 = max 有 arr 个位置, 那么需要计算最少要多少个d才能覆盖, 下一个值是v, 贡献 = 覆盖数 * (curv - v)

然后更新 arr的集合，再次计算多少个d才能，覆盖，问题就在于，这个更新arr以后的覆盖数计算需要O(n)

所以问题变成 set = 空; 每次 向里面加入若干个未出现过的 [1,n]之间的坐标，每次操作后，求其中最少需要多少个长度d才能覆盖

emmm这怎么维护啊?

题解

LCT

给一个数组，每次操作可能把0变1，问最少多少个长度d区间能覆盖所有1

0-index下

• 对于每个值为0，它的父节点是i+1
• 对于每个值为1，它的父节点是min(i+d,n)

那么ans=从0开始沿着父节点走，走到n经过的所有的 值的和

• 那么就是动态树

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
ll read() { ll r;scanf("%lld", &r);return r; }
template <typename T, typename S> class LCT {
  struct node { // 这里用0 表示空节点，所有存在的节点以1-index
    int pa; // 父节点(splay 内是splay内关系, 跨splay 是源点所在splay 指向 原树父节点)
    int ch[2]; // splay 的子节点
    bool flip; // lazy 子树翻转标记, 主要用在 makeRoot
    T v; // 节点单点值
    T prod;  // l.prod  * v * r.prod , 自定义 乘号运算, 计算的是限制在splay中的
    T rprod; // r.rprod * v * r.rprod, 翻转的 为了flip准备的，有些运算的 乘法不满足交换律，有些满足(那么和prod值相同)
    S sv; // 当前节点值
    S vir; // 在原树中此点的虚儿子的sub之和(原树有边,但splay中跨越splay)
    S sub; // vir + l.sub + r.sub + sv, 也就是当前u所在splay的 最左节点v（原树中的某个v）,v以及v子树的所有sv之和
    node() : pa{ 0 }, ch{ 0, 0 }, flip{ false }, v{},
      prod{}, rprod{}, sv{}, sub{}, vir{} {}
  };
#define cur o[u]
#define lc cur.ch[0]
#define rc cur.ch[1]
  vector<node> o;
  bool isRoot(int u) const { return o[cur.pa].ch[0] != u && o[cur.pa].ch[1] != u; } // 认父不认子
  bool direction(int u) const { return o[cur.pa].ch[1] == u && !isRoot(u); } // 是splay中父亲的哪个儿子
  void down(int u) {
    if (!cur.flip) return;
    for (int c : {lc, rc}) setFlip(c);
    cur.flip = false;
  }
  void up(int u) {
    cur.prod = o[lc].prod * cur.v * o[rc].prod;
    cur.rprod = o[rc].rprod * cur.v * o[lc].rprod;
    cur.sub = cur.vir + o[lc].sub + o[rc].sub + cur.sv;
  }
  void setFlip(int u) {
    if (!u) return;
    swap(lc, rc);
    swap(cur.prod, cur.rprod);
    cur.flip ^= 1;
  }
  void cp(int c, int p, int d) { // child parent
    if (c) o[c].pa = p;
    if (p) o[p].ch[d] = c;
  }
  /* SPLIT_HASH_HERE */
  void rotate(int u) {
    int f = cur.pa; // fa
    assert(f); // u not root
    int g = o[f].pa; // grandfa
    int l = direction(u);
    int c = cur.ch[l ^ 1]; // child
    // 需要注意的是 这里和splay中的区别, 这里的pa 当f是root时，依然会指向所在splay树中的最左的点的在原树的父节点, 所以这里不能用 cp(u, g, isRoot(f) ? -1 : direction(f));
    if (!isRoot(f)) o[g].ch[direction(f)] = u;
    cur.pa = g;
    cp(f, u, l ^ 1);
    cp(c, f, l);
    up(f);
  }
  void update(int u) { // 从上到下down 所以递归
    if (!isRoot(u)) update(cur.pa);
    down(u);
  };
  void splay(int u) {
    update(u);
    while (!isRoot(u)) {
      int f = cur.pa;
      if (!isRoot(f)) rotate(direction(u) == direction(f) ? f : u);
      rotate(u);
    }
    up(u);
  }
  void access(int x) { // x到当前原树的根的所有点，恰好放入一个splay中(实链中), 并且把x置为实链splay的根
    for (int u = x, last = 0; u; u = cur.pa) {
      splay(u);
      cur.vir = cur.vir + o[rc].sub - o[last].sub;
      rc = last;
      up(last = u);
    }
    splay(x);
  }
  int findRoot(int u) { // 原树的根
    int la = 0;
    for (access(u); u; u = lc) down(la = u);
    return la;
  }
  void split(int x, int y) { makeRoot(x); access(y); } // x到的路径y是恰好单独一个splay树, y为splay的根
  void makeRoot(int u) { access(u); setFlip(u); } // 修改根, 当前到原树的根的路径（大小关系翻转）
  /* SPLIT_HASH_HERE */
public:
  LCT(int n = 0) : o(n + 1) {}
  void setVal(int u, const T& v) { splay(++u); cur.v = v; up(u); }
  void setSval(int u, const S& v) { access(++u); cur.sv = v; up(u); }
  T query(int x, int y) { // 输入是0-index, 对于原树上x到y的链进行查询
    split(++x, ++y);
    return o[y].prod; // 内部是1-index
  }
  S subtree(int p, int u) { // 输入是0-index
    makeRoot(++p); // 在原树中p为根
    access(++u); // u...p是同splay
    return cur.vir + cur.sv;
  }
  bool connected(int u, int v) { return findRoot(++u) == findRoot(++v); }
  void link(int x, int y) { // 原来分离的原树通过x,y连接, x连到y, 但是lct中是没有连接的, 这个操作y父,x子，但是它们之间不是实边
    makeRoot(++x);
    access(++y);
    o[y].vir = o[y].vir + o[x].sub;
    up(o[x].pa = y); // 之间不是实边，所以只用更新y,不用更新y的祖先
  }
  void cut(int x, int y) { // 对原树切割, x-y如果不相邻则 无事发生
    split(++x, ++y);
    if (o[y].ch[0] == x) { // 如果相邻则满足
      o[y].ch[0] = o[x].pa = 0;
      up(y);
    }
  }
#undef cur
#undef lc
#undef rc
};


void luogu3690() {
  struct nodev {
    long long value;
    nodev(long long v = 0) : value(v) {}
    nodev operator*(const nodev& v0) {
      return nodev(value ^ v0.value);  // 用异或作为示例
    };
  };
  int n = read();
  int m = read();

  auto lct = LCT<nodev, int>(n);
  rep(i, 0, n) {
    int v = read();
    lct.setVal(i, nodev(v));
  }
  while (m-- > 0) {
    int op = read();
    int x = read();
    int y = read();
    if (op == 0) {
      printf("%lld\n", lct.query(--x, --y).value);
    } else if (op == 1) {
      if (!lct.connected(--x, --y)) lct.link(x, y);
    } else if (op == 2) {
      lct.cut(--x, --y);
    } else if (op == 3) {
      lct.setVal(--x, y);
    }
  }
}

void cf2097e() {
  // https://codeforces.com/contest/2097/problem/E
  struct nodev {
    ll value;
    nodev(ll v = 0) : value(v) {}
    nodev operator*(const nodev& v0) { return nodev(value + v0.value); };
  };
  int t = read();
  while (t-- > 0) {
    int n = read();
    int d = read();
    vector<pair<ll, int>> avi(n + 1); // 放置 {0,0} 最前面简化if逻辑
    rep(i, 1, n + 1) avi[i] = { read(),i - 1 };
    sort(begin(avi), end(avi));
    auto lct = LCT<nodev, int>(n + 1);
    rep(i, 0, n) lct.link(i, i + 1); // 未选中的 i -> i+1, 已经选中的i -> min(i+d,n);
    ll ans = 0;
    per(j, 1, n + 1) {
      auto [v, i] = avi[j];
      lct.setVal(i, nodev(1));
      lct.cut(i, i + 1);
      lct.link(i, min(i + d, n));
      ans += (avi[j].first - avi[j - 1].first) * lct.query(0, n).value;
    }
    printf("%lld\n", ans);
  }
}

int main() {
  // luogu3690();
  cf2097e();
  return 0;
}