ZROI Day1-Day10 笔记

比利♂海灵顿 · 2021-08-30 18:57:29 · 个人记录

ZROI

Day1: 倍增

令人疑惑的一天, 我还不如去卷题.

RMQ (Range Maximum/Minimum Query)

区间查询最大/小值.

• ST (Sparse Table)

  过水已隐藏

• 线段树

  过水已隐藏

快速幂

过水已隐藏

LCA (Lowest Common Ancestor)

查询

• 倍增

  过水已隐藏

• ST

  把树拍成欧拉序 (Euler Tour), 然后用 ST 表维护并查询最小深度的节点.

  每个点第一次出现是第一次 DFS 遍历到它的时候, 每个点后面的出现次数是它儿子的子树 DFS 结束的时候. 每次查询 LCA, 求欧拉序种两个点第一次出现的位置这个区间中深度最小的节点.

  正确性是因为这两个点中间的位置分别是前一个点的子树中的节点和它们 LCA 的部分子树还有这两点之间的路径, 其中, 这条路径包含 LCA, 并且 LCA 是最浅的节点, 并且其它节点都在 LCA 子树内, 深度都比它大, 所以这个深度最小的点就是 LCA.

  根据这个结论, 我们不必将两个点第一次出现作为左右端点, 只要随便找出某个这两个点出现的位置即可.

  复杂度分析: 每个点遍历到和遍历完都会给欧拉序贡献一个长度, 所以欧拉序长度是 O(n), DFS 遍历建立欧拉序的复杂度同样是 O(n), 并且 ST 表的复杂度是 O(n\log n) 预处理, O(1) 查询, 所以算法复杂度是 O(n\log n + q).

应用

• 树上两点距离

  过水已隐藏

• 树上两点间路径信息统计

  过水已隐藏

树上路径修改

用 LCA + 树上差分维护, DFS 统计权值.

细节过水已隐藏.

AT2693

给一棵边带权的树, 规定根为 K, 每次询问 x, y 经过 K 的最短距离. 这时规定一个点的深度为到 K 的路径的边权和. 每次查询输出 x, y 的深度和即可.

实现超级简单:

unsigned a[10005], m, n, Cnt(0), A, B, C, D, t, Ans(0), Tmp(0);
bool b[10005];
struct Edge; 
struct Node {
  Edge *Fst;
  Node *Fa; 
  unsigned long long Dep;
}N[100005], *S;
struct Edge {
  Node *To;
  Edge *Nxt;
  unsigned Val;
}E[200005], *CntE(E);
void Link(Node *x, Node *y) {
  (++CntE)->Nxt = x->Fst;
  x->Fst = CntE;
  CntE->To = y;
  CntE->Val = C;
}
void DFS(Node *x) {
  Edge *Sid(x->Fst);
  while (Sid) {
    if(Sid->To != x->Fa) {
      Sid->To->Fa = x;
      Sid->To->Dep = x->Dep + Sid->Val; 
      DFS(Sid->To);
    }
    Sid = Sid->Nxt;
  }
}
int main() {
  n = RD();
  for (register unsigned i(1); i < n; ++i) {
    A = RD(), B = RD(), C = RD();
    Link(N + A, N + B);
    Link(N + B, N + A);
  }
  for (register unsigned i(1); i <= n; ++i) N[i].Dep = 0x3f3f3f3f3f3f3f3f;
  m = RD(), S = N + RD(), S->Dep = 0;
  DFS(S); 
  for (register unsigned i(1); i <= m; ++i) {
    A = RD(), B = RD();
    printf("%llu\n", N[A].Dep + N[B].Dep); 
  }
  return Wild_Donkey;
}

例2

给定一棵边带权的树, 询问 x 到 y 路径上边权的最小值.

求 LCA 的同时统计信息 (貌似只能倍增), 过水已隐藏.

例3: CF609E

给一个边带权无向图, 求强制选择某条边的时候, 最小生成树边权总和.

先求最小生成树, 如果选定边本来就在树中, 则直接输出最小生成树权值. 否则选一点为根, 求选定边的两端点在最小生成树上的路径中权值的最大值, 删除这个权值, 将选定边的权值统计入答案即可.

码量没有那么短, 但是都是板子, 细节少, 半小时连写带调.

unsigned Fa[200005], Stack[200005], StTp(0), m, n, Cnt(0), A, B, C, D, t;
unsigned long long Sum(0), Ans[200005], Tmp(0);
bool b[10005];
struct FakeEdge {
  unsigned Val, Fr, To, Num;
  char Tag;
  inline const char operator< (const FakeEdge &x) const{
    return this->Val < x.Val;
  }
}FE[200005];
struct Edge;
struct Node {
  Edge *Fst;
  Node *Fa[20];
  unsigned Max[20], Dep;
}N[200005];
struct Edge {
  Node *To;
  Edge *Nxt;
  unsigned Val;
  char InTr;
}E[400005], *CntE(E);
void Link(Node *x, Node *y) {
  (++CntE)->Nxt = x->Fst;
  x->Fst = CntE;
  CntE->To = y;
  CntE->Val = C;
}
unsigned Find(unsigned x) {
  register unsigned Tmpx(x);
  while (Fa[Tmpx] ^ Tmpx) Stack[++StTp] = Tmpx, Tmpx = Fa[Tmpx];
  while (StTp) Fa[Stack[StTp--]] = Tmpx;
  return Tmpx;
}
void DFS(Node *x) {
  Edge *Sid(x->Fst);
  while (Sid) {
    if(Sid->To != x->Fa[0]) {
      Sid->To->Fa[0] = x;
      Sid->To->Max[0] = Sid->Val;
      Sid->To->Dep = x->Dep + 1;
      for (register unsigned i(0); Sid->To->Fa[i]; ++i) {
        Sid->To->Fa[i + 1] = Sid->To->Fa[i]->Fa[i];
        Sid->To->Max[i + 1] = max(Sid->To->Max[i], Sid->To->Fa[i]->Max[i]);
      }
      DFS(Sid->To);
    }
    Sid = Sid->Nxt;
  }
}
unsigned LCA(Node *x, Node *y) {
  register unsigned TmpM(0);
  if(x->Dep < y->Dep) swap(x, y);
  for (register unsigned i(18); i < 0x3f3f3f3f; --i) if(x->Fa[i]) if(x->Fa[i]->Dep >= y->Dep) {
    TmpM = max(TmpM, x->Max[i]);
    x = x->Fa[i];
  }
  if(x == y) return TmpM;
  for (register unsigned i(18); i < 0x3f3f3f3f; --i) if(x->Fa[i] != y->Fa[i]) {
    TmpM = max(TmpM, x->Max[i]);
    TmpM = max(TmpM, y->Max[i]);
    x = x->Fa[i];
    y = y->Fa[i];
  }
  TmpM = max(TmpM, x->Max[0]);
  TmpM = max(TmpM, y->Max[0]);
  return TmpM;
}
int main() {
  n = RD(), m = RD(); 
  for (register unsigned i(1); i <= m; ++i)
    FE[i].Fr = RD(), FE[i].To = RD(), FE[i].Val = RD(), FE[i].Num = i;
  sort(FE + 1, FE + m + 1);
  for (register unsigned i(1); i <= n; ++i) Fa[i] = i;
  for (register unsigned i(1); i <= m; ++i) if(Find(FE[i].Fr) ^ Find(FE[i].To)) {
    FE[i].Tag = 1;
    Fa[Fa[FE[i].Fr]] = Fa[FE[i].To];
    Sum += FE[i].Val;
  }
  for (register unsigned i(1); i <= m; ++i) if(FE[i].Tag) {
    C = FE[i].Val;
    Link(N + FE[i].Fr, N + FE[i].To);
    Link(N + FE[i].To, N + FE[i].Fr);
  }
  DFS(N + 1);
  for (register unsigned i(1); i <= m; ++i)
    if(FE[i].Tag) Ans[FE[i].Num] = Sum;
    else Ans[FE[i].Num] = Sum + FE[i].Val - LCA(N + FE[i].Fr, N + FE[i].To);
  for (register unsigned i(1); i <= m; ++i) printf("%llu\n", Ans[i]);
  return Wild_Donkey;
}

例4: HDU3183

每个测试点给一个 1000 位以内的整数, 要求删除 m 位, 使得结果最小.

每次从左往右扫, 如果当前位比下一位大, 删除这一位, 删完 m 位为止. 如果当前位更小, 则当前位往后移一位, 继续判断.

错误: 我竟然再次用 char 存整数...

unsigned m, n(1), Cnt(0), A, B, C, D, t, Ans(0), Tmp(0);
char a[10005], b[10005], Flg(0);
unsigned Pre[10005], Pro[10005];
inline void Clr() {
  memset(b, 0, n + 2);
  memset(a, 0, n + 2);
  memset(Pre, 0, (n + 2) << 2);
  memset(Pro, 0, (n + 2) << 2);
  n = 1;
  Flg = 0;
}
int main() {
  while (scanf("%s", a + 1) != -1) { 
    m = RD();
    while (a[n]) ++n;
    for (register unsigned i(0); i <= n; ++i) {
      Pre[i] = i - 1;
      Pro[i] = i + 1;
    }
    for (register unsigned i(1), j(0); i <= m; ++i) {
      while (a[j] <= a[Pro[j]]) j = Pro[j];
      b[j] = 1;
      Pro[Pre[j]] = Pro[j];
      Pre[Pro[j]] = Pre[j];
      j = Pre[j];
    }
    for (register unsigned i(1); i < n; i = Pro[i]){
      if(!b[i]) {
        if (a[i] == '0') {
          if(!Flg) continue;
          else printf("%c", a[i]);
        } else {
          printf("%c", a[i]);
          Flg = 1;
        }
      }
    }
    if(!Flg) putchar('0');
    putchar('\n'); 
    Clr();
  }
  return Wild_Donkey;
}

例5: POJ3419

LOJ 传送门

询问区间最长无重复元素的子段长度.

首先可以用双指针, 线性地处理出每个位置为左端点, 不重复的极长连续段长度 f_{i, 0}.

然后对 f 建立最大值 ST 表.

接下来, 使用二分答案, 二分最长段的长度 x. Judge() 函数很简单, 只要查询 [L, R - x + 1] 区间内的长度最大值是否大于 x 即可.

unsigned a[200005], f[200005][20], Log[200005], Bin[20], m, n, A, B, L, R, Mid, t, Ans(0), Tmp(0);
char Cnt[2000005];
inline void Clr() {}
inline unsigned Qry(unsigned x, unsigned y) {
  register unsigned Tmp(Log[y - x + 1]);
  return max(f[x][Tmp], f[y - Bin[Tmp] + 1][Tmp]);
}
inline char Judge(unsigned x) {
  return (Qry(A, B - x + 1) >= x);
}
int main() {
  n = RD(), m = RD(); 
  for (register unsigned i(1); i <= n; ++i)
    a[i] = RDsg() + 1000000;
  for (register unsigned i(1), j(1); i <= n; ++i) {
    while (!Cnt[a[j]]) ++Cnt[a[j++]];
    f[i][0] = j - i; 
    --Cnt[a[i]];
  }
  for (register unsigned i(1), j(0); i <= n; i <<= 1, ++j) 
    Log[i] = j, Bin[j] = i;
  for (register unsigned i(3); i <= n; ++i)
    Log[i] = max(Log[i], Log[i - 1]);
  for (register unsigned i(1), j(0); i <= n; i <<= 1, ++j)
    for (register unsigned k(1); k + (i << 1) <= n + 1; ++k)
      f[k][j + 1] = max(f[k][j], f[k + i][j]);
  for (register unsigned i(1); i <= m; ++i) {
    A = RD() + 1, B = RD() + 1;
    L = 1, R = B - A + 1;
    while (L ^ R) {
      Mid = ((L + R + 1) >> 1);
      if(Judge(Mid)) L = Mid;
      else R = Mid - 1;
    }
    printf("%u\n", L);
  }
  return Wild_Donkey;
}

Day2: 线段树&树状数组

区间查询-不修改-线段树

过水已隐藏 (还不如前缀和)

区间查询-单点修改-线段树

过水已隐藏 (还不如树状数组)

区间查询-区间修改-线段树

过水已隐藏

树状数组 (BIT)

其实就是线段树将右子树统统删除.

功能: 区间查询, 单点修改; 单点查询, 区间修改

过水已隐藏

例1

给定一个长度为 n 的排列 p, 求将其冒泡排序所需要交换的次数.

这题就是求数字右边比它小的数字数量和, 需要从右往左扫描并维护右边的不同数字出现个数, 进行单点修改, 并且区间查询.

使用权值树状数组, 值域如果较大, 可以使用动态开点线段树或离散化 + 树状数组.

例2: P4868

定义 "前前缀和" 为前缀和的前缀和, 维护一个序列, 要求:

• 单点修改

• 单点查询前前缀和

单点修改相当于对前缀和的区间修改, 单点查前前缀和相当于对前缀和区间查询, 所以我们可以直接对前缀和建立线段树, 然后进行区间修改和查询.

unsigned n, m, A;
long long a[100005], Sum[100005], B, C, Ans(0);
char Op[10];
struct Node {
  Node *LS, *RS;
  long long Val, Tag;
}N[200005], *CntN(N);
void PsDw(Node *x, unsigned Len) {
  if(x->Tag) {
    x->LS->Tag += x->Tag;
    x->LS->Val += x->Tag * ((Len + 1) >> 1);
    x->RS->Tag += x->Tag;
    x->RS->Val += x->Tag * (Len >> 1);
    x->Tag = 0;
  }
}
void Build(Node *x, unsigned L, unsigned R) {
  if(L == R) {
    x->Val = Sum[L];
    return;
  }
  register unsigned Mid((L + R) >> 1);
  Build(x->LS = ++CntN, L, Mid);
  Build(x->RS = ++CntN, Mid + 1, R);
  x->Val = x->LS->Val + x->RS->Val;
  return;
}
void Chg(Node *x, unsigned L, unsigned R) {
  if(A <= L) {
    x->Tag += C;
    x->Val += (R - L + 1) * C;
    return;
  }
  PsDw(x, R - L + 1);
  register unsigned Mid((L + R) >> 1);
  Chg(x->RS, Mid + 1, R);
  if(Mid >= A) Chg(x->LS, L, Mid);
  x->Val = x->LS->Val + x->RS->Val;
}
void Qry(Node *x, unsigned L, unsigned R) {
  if(A >= R) {
    Ans += x->Val;
    return;
  }
  PsDw(x, R - L + 1);
  register unsigned Mid((L + R) >> 1);
  Qry(x->LS, L, Mid);
  if(Mid < A) {
    Qry(x->RS, Mid + 1, R);
  }
}
int main() {
  n = RD(), m = RD(); 
  for (register unsigned i(1); i <= n; ++i) Sum[i] = Sum[i - 1] + (a[i] = RD());
  Build(N, 1, n);
  for (register unsigned i(1); i <= m; ++i) {
    scanf("%s", &Op);
    if(Op[0] ^ 'Q') {
      A = RD(), B = RD();
      C = B - a[A], a[A] = B;
      Chg(N, 1, n);
    } else {
      A = RD(), Ans = 0;
      Qry(N, 1, n);
      printf("%lld\n", Ans);
    }
  }
  return Wild_Donkey;
}

例3: POJ2155

给一个 0/1 矩阵, 实现:

• 矩形取反

• 单点查询

显然, 这个题需要差分+前缀和, 但是如何维护二维前缀和呢?

维护一个差分数组 f_{i, j} 表示点 (i, j) 后面所有的数取反次数, 所以这个数字是 0 或 1.

一个点 (x, y) 当前的值就是初始值取反 \displaystyle{(\sum_{i = 1}^{x}\sum_{j = 1}^{y} f_{i, j}) \% 2} 次.

发现只要求异或和即可.

使用二维树状数组, 其每一维的定义和一维树状数组一样, 相当于树状数组套树状数组. Tr_{i, j} 表示 (i - lowbit(i), i] 行的 (j - lowbit(j), j].

例4: CF1527E

给一个序列, 要求将其分成 m 段, 使得每段权值和最小.

一个段的权值定义为: 一个段的所有出现过的元素第一次出现和最后一次出现的权值和, 如 1 1 2 1 的权值是 3. 长度 n \leq 3.5 * 10^4, 段数 m \leq 100

设计状态 f_{i, j} 表示前 i 位, 分成 j 段的最小权值. 设 g_{i, j} 表示区间 [i, j] 这一段的权值.

这样就能写出方程:

非常容易想到 O(nm\log n) 的方法, 线段树维护最大/小值, 每次询问枚举区间断点.

在维护最小/大值的时候, 发现可以顺便维护答案 Val, 对于叶子节点, Val 显然等于 0, 因为没有合法 x, y, 对于一般节点, Val = \max(Val_{LS}, Val_{RS}, Max_{RS} - Min_{LS}.

这棵线段树可以做到 O(n) 预处理, O(logn) 修改.

询问可以优化到 O(logn). 像普通查询一样, 查询三个值, 分别是 [l, r] 区间内的 Min, Max 和 Val, 合并方式和前面预处理相同.

例5-Plus: POJ3728

给一棵点带权树, 每次查询 (l, r) 路径上的点对 (x, y) 的 max(a_y - a_x) (路径上 x 在 y 之前).

首先根据上一个题的思路推广, 因为我们只要判断两个点在路径上的相对方向, 不用判断距离, 所以可以使用树链剖分, 细节非常复杂, 需要判断这一段重链在路径中的方向是向上还是向下, 还需要合并重链信息, 复杂度 O(mlog^2n).

发现此题不需要修改, 所以可以使用倍增求 LCA 的过程, 维护路径信息, 合并方式和线段树一样, 细节数骤降. 不过仍然需要分辨垂直链的方向, 维护双份的 Val.

例6: HDU6315

给两个序列, 长度都是 n, a 一开始都是 0, b 是 [1, n] 的排列, 要求支持:

• a$ 区间加 $1

• 区间查询 \lfloor \frac{a_i}{b_i} \rfloor

询问明显需要维护一个序列 c, 使得 c_i = \lfloor \frac{a_i}{b_i} \rfloor.

最后是区间求和, 我们在元素统一的节点上直接统计, 否则下传标记, 直到统一元素为止.

复杂度的证明需要用到势能分析.

首先, 一个数 x 连续取 x = \phi(x) 直到 x = 1 的次数的量级是 \log x. 证明如下:

• 对于偶数 x

  这时, 一定有 \frac x2 的数字和 x 有公因数 2, 所以 \phi(x) 至多是 \frac x2

• 对于奇数 x

  我们回到定义式 \displaystyle{\phi(x) = x\prod_i^{p_i | x}\frac {p_i - 1}{p_i}}, 进行变形, \displaystyle{\phi(x) = \bigg(x\prod_i^{p_i | x} \frac 1{p_i}\bigg)\bigg(\prod_i^{p_i | x}(p_i - 1)\bigg)}. 我们知道, \displaystyle{x\prod_i^{p_i | x} \frac 1{p_i}} 一定是奇数, 而 \displaystyle{\prod_i^{p_i | x}(p_i - 1)} 一定是偶数, 所以 \phi(x) 一定是偶数.

综上, 一个数 x 连续取 \phi 的次数最多是 \log x 级别的.

势能的定义是这个节点一次查询最多消耗的时间复杂度, 而一个节点最多进行 \log Max 次取 \phi, 就能变成最低势能. 而每次暴力取 \phi (指查询的标记下传) 的复杂度是 O(n), 所以初始势能应该是 O(n \log Max). 而每次进行区间赋值, 会有 \log n 级别的节点变成统一元素, 它的势能最多增加 O(\log n\log Max). 这种操作最多会出现 m 次, 所以算法复杂度是 O((n + m \log n) \log Max).

例8: CF1149C

定义括号序子段权值为它去掉匹配的括号后剩下的形如 )))...)(...((( 的序列长度.

将直径转化为括号序的权值最大的子段的权值, 因为括号序表示的是先序遍历这棵树的移动方向, ( 表示向当前点的新的儿子移动, ) 表示回到这个点的父亲. 一个括号序表示在树上的一条可重复经过每边的路径, 去掉匹配的括号相当于转化为从这个子段表示的路径起点移动到终点的路径, 它的长度也就是起点到终点简单路径长度. 权值最大的子段的权值也就是树上最长简单路径, 也就是树的直径.

线段树维护这个权值, 一个节点维护八个值: CntD, Val, ValC, ValD, BdC, BdD, BdL, BdR.

然后是维护这些值:

总复杂度是 O(m \log n), 代码也很简单, 因为查询区间都是 [1, n], 所以无需写查询函数. 并且只需要单点修改即可, 所以无需使用 Tag.

unsigned m, n, Cnt(0), A, B, t, Ans(0), Tmp(0);
char a[200005], Tmpc, Chgc;
struct Node {
  Node *LS, *RS;
  int CntD, Val, ValC, ValD, BdC, BdD, BdL, BdR;
}N[400005], *CntN(N);
inline void Print(Node *x) {
  printf("Point %u [%u, %u]\n", x - N, x->LS - N, x->RS - N);
  printf("Cnt) %u Val %u Val( %u Val) %u\n", x->CntD, x->Val, x->ValC, x->ValD);
  printf("( %u ) %u <- %u -> %u\n", x->BdC, x->BdD, x->BdL, x->BdR);
}
inline void Udt (Node *x, int Len) {
  x->CntD = x->LS->CntD + x->RS->CntD;
  x->ValC = x->RS->ValC + max(x->LS->ValC - x->RS->ValD, 0);
  x->ValD = x->LS->ValD + max(x->RS->ValD - x->LS->ValC, 0);
  x->BdC = max(x->LS->BdC, x->RS->BdC + ((Len + 1) >> 1) - ((x->LS->CntD) << 1));
  x->BdD = max(x->RS->BdD, x->LS->BdD + ((x->RS->CntD) << 1) - (Len >> 1));
  x->BdL = max(x->LS->BdL, max(x->LS->ValD + x->LS->ValC + x->RS->BdC, x->RS->BdL + x->LS->ValD - x->LS->ValC));
  x->BdR = max(x->RS->BdR, max(x->RS->ValD + x->RS->ValC + x->LS->BdD, x->LS->BdR + x->RS->ValC - x->RS->ValD));
  x->Val = max(x->LS->Val, x->RS->Val);
  register int TmpV = max(x->LS->BdR + x->RS->BdC, x->RS->BdL + x->LS->BdD);
  x->Val = max(x->Val, TmpV);
  return; 
}
void Build (Node *x, unsigned L, unsigned R) {
  if(L == R) {
    x->BdL = x->BdR = x->Val = 1;
    x->BdD = x->ValD = x->CntD = a[L];
    x->BdC = x->ValC = a[L] ^ 0x1;
    return;
  }
  register unsigned Mid((L + R) >> 1);
  Build(x->LS = ++CntN, L, Mid);
  Build(x->RS = ++CntN, Mid + 1, R);
  Udt(x, R - L + 1);
}
void Chg(Node *x, unsigned L, unsigned R) {
  if(L == R) {
    x->BdD = x->ValD = x->CntD = a[L];
    x->BdC = x->ValC = a[L] ^ 0x1;
    return;
  }
  register unsigned Mid((L + R) >> 1);
  if(A <= Mid) Chg(x->LS, L, Mid);
  else Chg(x->RS, Mid + 1, R);
  Udt(x, R - L + 1); 
}
int main() {
  n = ((RD() - 1) << 1), m = RD();
  scanf("%s", a + 1);
  for (register unsigned i(1); i <= n; ++i) a[i] -= '(';
  Build(N, 1, n);
  printf("%d\n", N->Val);
  for (register unsigned i(1); i <= m; ++i) {
    A = RD(), B = RD();
    if(a[A] ^ a[B]) {
      swap(a[A], a[B]);
      Chg(N, 1, n);
      A = B;
      Chg(N, 1, n);
    }
    printf("%d\n", N->Val);
  }
  return Wild_Donkey;
}

Day3: 模拟赛

T1: 模拟

一个字符矩阵, 从 (1, 1) 走到 (n, m), 只能往右和往下两个方向走, 也就是和 (n, m) 的曼哈顿距离只能缩短.

求路径上的字符连成的字典序最小的字符串.

这道题类似于数字三角形, 将矩形的数组转化成三角形, 将矩阵分成 n + m - 1 层, 每层只有最小值可以经过, 递推即可, 复杂度 O(nm).

考场代码 24':

unsigned m, n, Cnt(0), A, B, C, D, t;
char a[2005][2005], b[2005][2005], Ans[4005], Min;
inline void Clr() {}
int main() {
  n = RD(), m = RD(); 
  for (register unsigned i(1); i <= n; ++i) {
    scanf("%s", a[i] + 1);
  }
  b[1][1] = 1;
  Ans[0] = a[1][1];
  for (register unsigned i(2), Tmp; i <= n; ++i) {
    Tmp = min(i, m), Min = 0x7f;
    for (register unsigned j(1); j <= Tmp; ++j) {
      if(b[i - j + 1][j - 1] | b[i - j][j]) {
        Min = min(a[i - j + 1][j], Min);
      }
    }
    Ans[i - 1] = Min;
    for (register unsigned j(1); j <= Tmp; ++j) {
      if(a[i - j + 1][j] == Min) {
        b[i - j + 1][j] = 1;
      }
    }
  }
  for (register unsigned i(2), Tmp; i <= m; ++i) {
    Tmp = (n + i > m) ? (n - m + i) : 1, Min = 0x7f;
    for (register unsigned j(n); j >= Tmp; --j) {
//      c[j][i - j + n] = i;
      if(b[j - 1][i - j + n] | b[j][i - j + n - 1]) {
        Min = min(Min, a[j][i - j + n]);
      }
    }
    Ans[n + i - 2] = Min;
    for (register unsigned j(n); j >= Tmp; --j) {
      if(a[j][i - j + n] == Min) {
        b[j][i - j + n] = 1;
      }
    }
  }
  printf("%s\n", Ans);
  return Wild_Donkey;
}

挂掉了, 原因是每层只是取了最小值, 但是没有考虑是否可以走, 加一个特判就过了.

死因:

if(a[i - j + 1][j] == Min && (b[i - j + 1][j - 1] | b[i - j][j])) {

正解 100':

unsigned m, n, Cnt(0), A, B, C, D, t;
char a[2005][2005], b[2005][2005], Ans[4005], Min;
inline void Clr() {}
int main() {
  n = RD(), m = RD(); 
  for (register unsigned i(1); i <= n; ++i) {
    scanf("%s", a[i] + 1);
  }
  b[1][1] = 1;
  Ans[0] = a[1][1];
  for (register unsigned i(2), Tmp; i <= n; ++i) {
    Tmp = min(i, m), Min = 0x7f;
    for (register unsigned j(1); j <= Tmp; ++j) {
      if(b[i - j + 1][j - 1] | b[i - j][j]) {
        Min = min(a[i - j + 1][j], Min);
      }
    }
    Ans[i - 1] = Min;
    for (register unsigned j(1); j <= Tmp; ++j) {
      if(a[i - j + 1][j] == Min && (b[i - j + 1][j - 1] | b[i - j][j])) {
        b[i - j + 1][j] = 1;
      }
    }
  }
  for (register unsigned i(2), Tmp; i <= m; ++i) {
    Tmp = (n + i > m) ? (n - m + i) : 1, Min = 0x7f;
    for (register unsigned j(n); j >= Tmp; --j) {
      if(b[j - 1][i - j + n] | b[j][i - j + n - 1]) {
        Min = min(Min, a[j][i - j + n]);
      }
    }
    Ans[n + i - 2] = Min;
    for (register unsigned j(n); j >= Tmp; --j) {
      if(a[j][i - j + n] == Min && (b[j - 1][i - j + n] | b[j][i - j + n - 1])) {
        b[j][i - j + n] = 1;
      }
    }
  }
  printf("%s\n", Ans);
  return Wild_Donkey;
}

T2: 贪心 状压DP

先离散化, 变成一个 n * n 以内的矩阵.

很容易想到枚举 y_1, y_2 作为纵坐标上下界, 在横坐标上线性求最大子段和, 所以复杂度为 O(n^3).

尝试用线段树求最大子段和, 在枚举边界时, 在线段树上加入每一行的元素复杂度从 O(1) 变成 O(\log n). 但是我们可以同时维护区间和的最大子段和, 这样就不用 O(n) 求最大子段和了, 可以在一行插入之后直接得到最大子段和.

线段树求 LIS

权值线段树, 维护对应权值为结尾的最长 LIS 长度. 每次插入一个数 a_i 之前查询区间 [1, a_i) 的最大值 Max, 尝试使用 Max + 1 更新位置 a_i.

权值线段树一般伴随着离散化, 如果强制在线, 还可以结合动态开点.

复杂度 O(n\log n).

P1486

维护一个集合, 支持:

• 加入一个数字

• 全局加减

• 查询排名第 k 的元素

• 将低于下界的元素删除

典型的权值线段树, 记录一个 Level 作为海平面, 每次全局加就降低海平面, 相当于整体增加了, 全局减就升高海平面, 并且将淹没的点删掉.

查询的时候在线段树上二分查找即可.

插入时记录一个总入队数 (注意判断一开始就不合法的情况, 直接跳过, 不计入总人数), 最后用总人数减去还在线段树里的人数即可.

unsigned a[10005], m, n, Cnt(0), A, B, C, D, t, Ans(0), Tmp(0), Level(100000);
char Op[5];
struct Node {
  Node *LS, *RS;
  unsigned Val;
}N[600005], *CntN(N);
void Del (Node *x, unsigned L, unsigned R){
  x->Val = 0;
  if(L == R) return;
  register unsigned Mid((L + R) >> 1);
  if(x->LS) {
    if(x->LS->Val) Del(x->LS, L, Mid);
    x->Val += x->LS->Val; 
  }
  if(x->RS) {
    if(Mid < Level - 1) if(x->RS->Val) Del(x->RS, Mid + 1, R); 
    x->Val += x->RS->Val;
  }
}
void Chg(Node *x, unsigned L, unsigned R) {
  ++(x->Val);
  if(L == R) return;
  register unsigned Mid((L + R) >> 1);
  if(A <= Mid) {
    if(!(x->LS)) x->LS = ++CntN;
    Chg(x->LS, L, Mid);
  } else {
    if(!(x->RS)) x->RS = ++CntN; 
    Chg(x->RS, Mid + 1, R);
  }
}
void Qry(Node *x, unsigned L, unsigned R) {
  if(L == R) {B = L;return;}
  register unsigned Mid((L + R) >> 1);
  if(x->RS) {
    if(x->RS->Val >= A) return Qry(x->RS, Mid + 1, R);
    A -= x->RS->Val;
  }
  Qry(x->LS, L, Mid);
}
int main() {
  n = RD(), Level += (m = RD());
  for (register unsigned i(1); i <= n; ++i) {
    scanf("%s", &Op[1]), A = RD();
    switch (Op[1]) {
      case ('I') :{
        if(A >= m) {
          A += Level - m;
          ++Ans;
          Chg(N, 1, 300000);
        }
        break;
      }
      case ('A') :{
        Level -= A;
        break;
      }
      case ('S') :{
        Level += A;
        Del(N, 1, 300000);
        break;
      }
      case ('F') :{
        if(A > N->Val) {
          printf("-1\n");
          break;
        }
        Qry(N, 1, 300000);
        printf("%u\n", B - Level + m);
        break;
      }
    }
  }
  printf("%u\n", Ans - N->Val);
  return Wild_Donkey;
}

HDU 2019-MU-Day3-G

一个序列, 求对于每一个 i, 第 i 位保留, 在前缀 [1, i) 中取尽量少的位置变成 0, 使得前缀 [1, i] 的和不大于一个常数 k.

权值线段树上二分, 二分选择线段树上最右边的部分, 求总和 SumBig, 使得前缀和 Sum - SumBig \leq k. 统计这个部分的元素数量.

二分复杂度 O(\log n), 线段树维护的复杂度也是 O(\log n), 总复杂度 O(n\log n).

动态开点线段树

过水已隐藏

Nowcoder-2019-MU-Day7-E

维护一个集合, 支持:

• 插入 [l, r] 的所有整数

• 查询中位数

动态开点权值线段树上二分.

矩形求并

过水已隐藏

线段树合并

过水已隐藏

CF600E

这时, 知道 S[a, p) = T[1, p - a + 1), T[1, ZT_{i - a + 1}) = T[i - a + 1, i - a + 1 + ZT_{i - a + 1}), 所以 T[1, ZT_{i - a + 1}) = T[i - a + 1, i - a + 1 + ZT_{i - a + 1}) = S[i, i + ZT_{i - a + 1}) 所以 ZS_i \geq ZT_{i - a + 1}.

接下来, 证明 ZS_i \leq ZT_{i - a + 1}. 我们知道 S_{i + ZT_{i - a + 1}} = T_{i - a + 1 + ZT_{i - a + 1}} \neq T_{ZT_{i - a + 1}}, 所以 ZS_i \leq ZT_{i - a + 1}.

综上 ZT_{i - a + 1} \leq ZS_i \leq ZT_{i - a + 1}, 也就是 ZT_{i - a + 1} = ZS_i

• i + ZT_{i - a + 1} = p

  其实证明 ZS_i \geq ZT_{i - a + 1} 的过程和上一种情况一样, 但是这时不一定保证 ZS_i \leq ZT_{i - a + 1}.

  这是因为我们不知道 S_{i + ZT_{i - a + 1}} = T_{i - a + 1 + ZT_{i - a + 1}} 是否成立, 所以既然 T[1, ZT_{i - a + 1}) = T[i - a + 1, i - a + 1 + ZT_{i - a + 1}), 不如直接将 a 右移至 i 的位置, 继续匹配, 找出新的 p, 重复之前的步骤即可.

• i + ZT_{i - a + 1} > p

  类似地, 我们知道 T[1, p - a + 1) = S[a, p), 而且 T[1, ZT_{i - a + 1}) = T[i - a + 1, i - a + 1 + ZT_{i - a + 1}), 所以 T[1, p - a + 1) = S[i, p), 所以 ZS_i \geq p - i.

  这时有 S_p \neq T_{p - a + 1} = T_{ZT_{i - 1 + 1}}, 因此 ZS_i \leq p - i, 所以 ZS_i = p - i.

求 ZT 的时候, 边界条件是 ZT_1 = LenT, 因为 T 和 T 自己的 LCP 一定是它本身.

接下来, 将 T 作为母串, a = 2, 用模板串 T 对它本身进行匹配. 假设我们知道 ZT_{i} 前面所有 ZT 值, 也就是我们求 ZT_{i} 所需的所有 ZT 值, 这样就可以用相同的方法求出 ZT 了.

代码实现:

using namespace std;
unsigned ZS[20000005], ZT[20000005], m, n, Cnt(0);
unsigned long long Ans1(0), Ans2(0);
char S[20000005], T[20000005];
void ExKMP(char *Mot, char *Mod, unsigned *Zot, unsigned *Zod, unsigned Lenot) {
  register unsigned i(1), a(1), p(1);
  while (i <= Lenot) {
    while (Mot[p] == Mod[p - a + 1]) ++p;
    if (p == a) {
      Zot[i] = 0, ++i, ++a, ++p;
      continue;
    }
    if(i >= p) {
      a = i;
      continue;
    }
    if (i + Zod[i - a + 1] == p) {
      if(p - i == m) Zot[i] = m, ++i, p = i;
      a = i;
      continue;
    }
    if(i + Zod[i - a + 1] < p) {
      Zot[i] = Zod[i - a + 1];
    } else {
      Zot[i] = p - i;
    }
    ++i;
  }
  return;
}
int main() {
  scanf("%s%s", S + 1, T + 1);
  n = strlen(S + 1), m = strlen(T + 1); 
  ZT[1] = m;
  ExKMP(T + 1, T, ZT + 1, ZT, m - 1);
  for (register unsigned long long i(1); i <= m; ++i) {
    Ans1 ^= i * (ZT[i] + 1);
  }
  ExKMP(S, T, ZS, ZT, n);
  for (register unsigned long long i(1); i <= n; ++i) {
    Ans2 ^= i * (ZS[i] + 1);
  }
  printf("%llu\n%llu\n", Ans1, Ans2); 
  return Wild_Donkey;
}

ManacherehcanaM

过水已隐藏

PAM

过水已隐藏

SAM

过水已隐藏

GSAM

过水已隐藏

SGAM

过水已隐藏

<!-- ### ICPC2018-Nanjing-Regional-Contest-M

给两个字符串 S, T, 有多少有序 (i, j, k) 满足 S_i,..., S_j, T_1,..., T_k 是回文串.

用 T 的前缀倒序匹配 S, 然后对 S 求 Manacher P 数组.

设 T' 是倒序的 T.

枚举 T' 的每个后缀和 S 的每个后缀的 LCP, 然后求以 LCP 末尾为起始的 S 的回文子串, 统计入答案 O(n^3). -->

<!-- ### Nowcoder14894

从字符串 A 中取可空子串 [l1, r1], 从 B 中取 [l2, r2] 要求 r1 = l2. -->

POI2007

给一个多边形, 求有多少对称轴.

每个点求两个临边夹角, 按顺序破环为链跑 Manacher, 只要存在对于某个中心的回文串长度为 n, 则找到一个对称轴.

Day7: 模拟赛 Ⅱ

模拟赛!

A

给 n 个点, 用长为 k 的窗口覆盖, 求最少窗口数.

红题中的红题, 简称红中红.

unsigned a[100005], m, n, Cnt(0), A, B, C, D, t, Ans(0), Tmp(0);
char b[10005];
int main() {
  n = RD(), m = RD();
  for (register unsigned i(1); i <= n; ++i) {
    a[i] = RD();
  }
  sort(a + 1, a + n + 1);
  for (register unsigned i(1), j(0); i <= n; ++i) {
    if(j < a[i]) {
      ++Ans, j = a[i] + m;
    }
  }
  printf("%u\n", Ans);
  return Wild_Donkey;
}

B

给一个山谷, 谷底之前高度递减, 谷底之后高度递增. 现在下雨, 水会优先往下流, 求最后的水位高度.

将山谷片成 n 片. 然后按高度为第一关键字, 以位置为第二关键字排序. 扫一遍排序后的数组处理出 Width_i 表示高度 i 的山谷宽度.

我们可以从低到高枚举高度, 每次减去宽度, 直到水量不足填满一层, 然后约分即可.

不要忘记判断整数部分为 0 的情况!!! (不要问我为什么知道, 100' \rightarrow 99')

unsigned Width[1005], Min, m, n, Cnt(0), C, D, t, Ans(-1), Tmp(0), W;
char Exist[1005];
struct Hill {
  unsigned Hight, Pos;
  inline const char operator<(const Hill &x) const{
    return (this->Hight ^ x.Hight) ? (this->Hight < x.Hight) : (this->Pos < x.Pos);
  }
}H[1005], A, B;
int main() {
  n = RD(), m = RD();
  for (register unsigned i(1); i <= n; ++i) {
    Exist[H[i].Hight = RD()] = 1, H[i].Pos = i;
  }
  H[++n].Hight = 0x3f3f3f3f, H[n].Pos = 0;
  H[++n].Hight = 0x3f3f3f3f, H[n].Pos = n - 1;
  sort(H + 1, H + n + 1);
  Min = H[1].Hight; 
  for (register unsigned i(Min), L(0x3f3f3f3f), R(0); i <= 1000; ++i) {
    if(Exist[i]) {
      A.Hight = i;
      B.Hight = i + 1;
      L = min(L, upper_bound(H + 1, H + n + 1, A)->Pos);
      R = max(R, (lower_bound(H + 1, H + n + 1, B) - 1)->Pos);
      Width[i] = R - L + 1;
    } else {
      Width[i] = Width[i - 1];
    }
  }
  for (register unsigned i(Min); i <= 1000; ++i) {
    if(m < Width[i]) {
      W = Width[i];
      break;
    }
    m -= Width[i];
    Ans = i, W = Width[i];
  }
  ++Ans;
  if(m >= (n - 2)) {
    W = n - 2;
    Ans += m / W;
    m %= W;
  }
  Tmp = __gcd(W, m);
  if(!Ans) {
    printf("%u/%u\n", m / Tmp, W / Tmp);
    return 0;
  }
  if(!m) {
    printf("%u\n", Ans);
    return 0;
  }
  printf("%u+%u/%u\n", Ans, m / Tmp, W / Tmp);
  return Wild_Donkey;
}

C

给两个序列 A, B, 每次选择一个数列整体修改, 然后查询两个数列所有数的中位数.

其实考场上用的是复杂度错误的算法 O(n + m + q\log n \log m), 但是因为 \color{red}传统艺能, 仍然过掉了此题.

因为是全局修改, 所以可以打一个 Tag, 然后在询问的过程中判断两个数组中的元素大小的时候叠加上 Tag 的修正即可.

二分答案 a_i, 然后二分查找 a_i 在 b 中的排名, 判断它们的和, 每次询问是 O(\log n \log m).

long long a[100005], b[100005], A, B, C, D, Ans(0);
unsigned m, n, q, Tmp(0), Dest(0);
unsigned Judge (unsigned x) {
  return x + upper_bound(b + 1, b + m + 1, a[x] + C - D) - 1 - b < Dest;
}
unsigned Judge2 (unsigned x) {
  return x + upper_bound(a + 1, a + n + 1, b[x] + D - C) - 1 - a < Dest;
}
int main() {
  n = RD(), m = RD(), q = RD();
  Dest = ((m + n + 1) >> 1);
  for (register unsigned i(1); i <= n; ++i) {
    a[i] = RD() - a[1];
  }
  a[0] = -1000000000000000, A = a[1] + 1000000000000000, a[1] = 0, a[n + 1] = 0x3f3f3f3f3f3f3f3f;
  for (register unsigned i(1); i <= m; ++i) {
    b[i] = RD() - b[1];
  }
  b[0] = -1000000000000000, B = b[1] + 1000000000000000, b[1] = 0, b[m + 1] = 0x3f3f3f3f3f3f3f3f;
  for (register unsigned i(1); i <= q; ++i) {
    if(RD() & 1) {
      C = A + RDsg();
      D = B;
    } else {
      D = B + RDsg();
      C = A; 
    }
    register unsigned L(0), R(n), Mid;
    while (L ^ R) {
      Mid = ((L + R + 1) >> 1);
      if(Judge(Mid)) {
        L = Mid;
      } else {
        R = Mid - 1;
      }
    }
    Tmp = L;
    L = upper_bound(b + 1, b + m + 1, a[Tmp] + C - D) - 1 - b, R = upper_bound(b + 1, b + m + 1, a[Tmp + 1] + C - D) - 1 - b;
    while (L ^ R) {
      Mid = ((L + R + 1) >> 1);
      if(Judge2(Mid)) {
        L = Mid;
      } else {
        R = Mid - 1;
      }
    }
    while (Tmp + L >= Dest) {
      if(a[Tmp - 1] + C > b[L - 1] + D) {
        --Tmp;
      } else {
        --L;
      }
    }
    while (Tmp + L + 1 < Dest) {
      if(a[Tmp + 1] + C < b[L + 1] + D) {
        ++Tmp;
      } else {
        ++L;
      }
    }
    Ans = min(a[Tmp + 1] + C, b[L + 1] + D);
    if (!((n + m) & 1)) {
      if(a[Tmp + 1] + C < b[L + 1] + D) {
        Ans += min(a[Tmp + 2] + C, b[L + 1] + D); 
      } else {
        Ans += min(a[Tmp + 1] + C, b[L + 2] + D);
      }
      if(Ans & 1) {
        printf("%lld.5\n", (Ans >> 1) - 1000000000000000);
      } else {
        printf("%lld\n", (Ans >> 1) - 1000000000000000);
      }
      continue;
    }
    printf("%lld\n", Ans - 1000000000000000);
  }
  return Wild_Donkey;
}

事实上, O(n + m + q \log n) 的算法很容易实现. 只要在二分一个 a_i 的时候, 直接判断 b_{\frac{n + m}2 - i} 的大小是否紧贴 a_i 即可.

long long a[100005], b[100005], A, B, C, D, Ans(0);
unsigned m, n, q, Tmp(0), Dest(0);
unsigned Judge (unsigned x) {
  if(a[x] + C < b[Dest - x + 1] + D) return 1;
  return 0;
}
int main() {
  n = RD(), m = RD(), q = RD();
  Dest = ((m + n + 1) >> 1);
  for (register unsigned i(1); i <= n; ++i) {
    a[i] = RD() - a[1];
  }
  a[0] = -1000000000000000, A = a[1] + 1000000000000000, a[1] = 0, a[n + 1] = 0x3f3f3f3f3f3f3f3f;
  for (register unsigned i(1); i <= m; ++i) {
    b[i] = RD() - b[1];
  }
  b[0] = -1000000000000000, B = b[1] + 1000000000000000, b[1] = 0, b[m + 1] = 0x3f3f3f3f3f3f3f3f;
  for (register unsigned i(1); i <= q; ++i) {
    if(RD() & 1) {
      C = A + RDsg();
      D = B;
    } else {
      D = B + RDsg();
      C = A; 
    }
    register unsigned L((Dest >= m) ? (Dest - m) : 0), R(min(n, Dest)), Mid;
    while (L ^ R) {
      Mid = ((L + R + 1) >> 1);
      if(Judge(Mid)) {
        L = Mid;
      } else {
        R = Mid - 1;
      }
    }
    Ans = max(a[L] + C, b[Dest - L] + D);
    if (!((n + m) & 1)) {
      Ans += min(a[L + 1] + C, b[Dest - L + 1] + D); 
      if(Ans & 1) {
        printf("%lld.5\n", (Ans >> 1) - 1000000000000000);
      } else {
        printf("%lld\n", (Ans >> 1) - 1000000000000000);
      }
      continue;
    }
    printf("%lld\n", Ans - 1000000000000000);
  }
  return Wild_Donkey;
}

D

给两个 10^{100} 以内的十进制数 L, R, 给出 n 个位数总和在 100 以内的十进制数, 求 [L, R] 中满足包含所有 n 个数作为子串的整数的数量.

"ACAM + 状压DP + 数位DP" 大杂烩

建立 n 个数的 ACAM, 然后在 ACAM 上跑 DP, 每个节点 i 存一个数组 f_{j, pos, 0/1}, 表示走到第 Pos 位的时候, 包含了状压状态为 j 表示的子串的, 是否顶着上界的情况数.

重定义转移边后跑 DP 即可, 注意边界条件是所有情况中, 前导零后面的第一个非零转移, 需要特别讨论.

const unsigned MOD(998244353);
const char _0(0), _1(1), _10(10);
char Len, TLen, m, n;
unsigned Ans(0), Tmp(0);
char L[105], R[105], a[105];
struct Node {
  Node *To[10], *Fa, *Fail, *Son, *Bro;
  unsigned f[105][32][2], Sum[105][32][2];
  char End;
}N[105], *Last(N), *CntN(N);
struct Quee {
  Node *Nd;
  char Chr;
}Q[105], *Hd(Q), *Tl(Q);
void Add(char c) {
  if(!(Last->To[c])) Last->To[c] = ++CntN, CntN->Fa = Last;
  Last = Last->To[c];
}
void Build() {
  (++Tl)->Nd = N;
  register Node *x, *Back;
  register char c; 
  while (Hd != Tl) {
    x = (++Hd)->Nd, c = Hd->Chr;
    if(x->Fa) {
      Back = x->Fa->Fail;
      while (Back) {
        if(Back->To[c]) {
          x->Fail = Back->To[c];
          x->Bro = Back->To[c]->Son;
          Back->To[c]->Son = x;
          break;
        }
        Back = Back->Fail; 
      }
      if(!(x->Fail)) x->Fail = N, x->Bro = N->Son, N->Son = x;
    }
    for (register char i(_0); i < _10; ++i) if(x->To[i]) (++Tl)->Nd = x->To[i], Tl->Chr = i;
  } 
}
void DFS(Node *x) {
  register Node *So(x->Son);
  while (So) So->End |= x->End, DFS(So), So = So->Bro;
}
void ReLink(Node *x) {
  register Node *Back; 
  for (register char i(_0); i < _10; ++i) {
    if(!(x->To[i])) {
      Back = x->Fail;
      while (Back) {
        if(Back->To[i]) {x->To[i] = Back->To[i];break;}
        Back = Back->Fail;
      }
      if(!(x->To[i])) x->To[i] = N;;
    } else {
      ReLink(x->To[i]);
    }
  }
}  
void DP (char *x, char Lead) {
  for (register char j(_1); j <= (x[Lead]); ++j)
    ++(N->To[j]->f[Lead + 1][N->To[j]->End][(j == x[Lead]) ? _1 : _0]),
    N->To[j]->Sum[Lead + 1][N->To[j]->End][(j == x[Lead]) ? _1 : _0] += j;
  for (register char i(Lead + _1); i < Len; ++i) {
    for (register char j(_1); j < _10; ++j)
      ++(N->To[j]->f[i + 1][N->To[j]->End][0]),
      N->To[j]->Sum[i + 1][N->To[j]->End][0] += j;
    for (register char j(_0); j < m; ++j) {
      for (register Node *k(N); k <= CntN; ++k) {
        register unsigned *Des;
        for (register char l(_0); l < x[i]; ++l) {
          Des = k->To[l]->f[i + 1][j | k->To[l]->End];
          *Des += k->f[i][j][0]; if(*Des >= MOD) *Des -= MOD;
          *Des += k->f[i][j][1]; if(*Des >= MOD) *Des -= MOD;
          Des = k->To[l]->Sum[i + 1][j | k->To[l]->End];
          *Des = (((unsigned long long)k->Sum[i][j][0] + k->Sum[i][j][1]) * 10 + ((unsigned long long)k->f[i][j][0] + k->f[i][j][1]) * l + *Des) % MOD;
        }
        Des = k->To[x[i]]->f[i + 1][j | k->To[x[i]]->End];
        *(Des + 1) += k->f[i][j][1]; if(*(Des + 1) >= MOD) *(Des + 1) -= MOD;
        *Des += k->f[i][j][0]; if(*Des >= MOD) *Des -= MOD;
        Des = k->To[x[i]]->Sum[i + 1][j | k->To[x[i]]->End];
        *Des = ((unsigned long long)k->Sum[i][j][0] * 10 + (unsigned long long)k->f[i][j][0] * x[i] + *Des) % MOD;
        *(Des + 1) = ((unsigned long long)k->Sum[i][j][1] * 10 + (unsigned long long)k->f[i][j][1] * x[i] + *(Des + 1)) % MOD;
        for (register char l(x[i] + 1); l < _10; ++l) {
          Des = k->To[l]->f[i + 1][j | k->To[l]->End];
          *Des += k->f[i][j][0]; if(*Des >= MOD) *Des -= MOD;
          Des = k->To[l]->Sum[i + 1][j | k->To[l]->End];
          *Des = ((unsigned long long)k->Sum[i][j][0] * 10 + (unsigned long long)k->f[i][j][0] * l + *Des) % MOD;
        }
      }
    }
  }
  for (register Node *k(N); k <= CntN; ++k){
    register unsigned *Des(k->Sum[Len][m - 1]);
    Tmp += *Des; if(Tmp >= MOD) Tmp -= MOD;
    Tmp += *(Des + 1); if(Tmp >= MOD) Tmp -= MOD;}
  for (register char i(_1); i <= Len; ++i)
    for (register char j(_0); j < m; ++j)
      for (register Node *k(N); k <= CntN; ++k)
        k->f[i][j][0] = k->f[i][j][1] = k->Sum[i][j][0] = k->Sum[i][j][1] = 0;
}
int main() {
  n = RD(), m = (1 << n), scanf("%s%s", L, R), TLen = strlen(L), Len = strlen(R);
  for (register unsigned i(TLen - 1); i < 0x3f3f3f3f; --i) L[Len - TLen + i] = L[i] - '0';
  for (register char i(_0); i < Len - TLen; ++i) L[i] = 0;
  for (register char i(_0); i < Len; ++i) R[i] = R[i] - '0';
  TLen = Len - 1; while (!L[TLen]) L[TLen] = 9, --TLen; --L[TLen], TLen = 0, L[Len] = 1; 
  while(!L[TLen]) ++TLen;
  for (register char i(_0), j; i < n; ++i) {
    memset(a, 0, sizeof(a)), scanf("%s", a), j = strlen(a), Last = N;
    for (register char k(0); k < j; ++k) Add(a[k] - '0');
    Last->End = 1 << i;
  }
  Build(), DFS(N), ReLink(N), DP(R, 0), Ans = Tmp, Tmp = 0, DP(L, TLen), Ans += MOD - Tmp;
  if(Ans >= MOD) Ans -= MOD; printf("%u\n", Ans);
  return Wild_Donkey;
}

Day8: 分治 & CDQ & 线段树分治

例题

一张无向图, 每次询问 a, b 不经过 c 的最短路, n \leq 200, q \leq 10^5.

数据范围提示了 Floyd, 但是这个 Floyd 是排除了某个点的 Floyd, 我们只要发现将点插入 Floyd 容易维护, 所以考虑加点 + 撤销, 采用分治, 先将左边的插入, 然后对右边分治, 右边结束之后, 撤销左边点的加入, 继续递归左边. 递归到边界就可以直接回答没有 c_i 存在的最短路.

ZJOI2016

给一个正边权的网格图和若干询问, 每次询问两点间最短路.

将矩形分割成两个矩形, 对于分割线上的所有点, 求到矩形内所有点的单源最短路, 然后递归两个子矩形, 重复之前的操作.

然后分析两点间的路径可能的情况.

两点间的路径可能是蓝线, 跨过了右边子矩形的分割线, 也可能是黄线, 经过了左边子矩形的分割线, 对于所有可能经过的分割线, 枚举分割线上每个点到两个点的距离和, 取最小值作为答案.

离线询问, 然后求每一个分割线上的点到矩形内的最短路, 更新可能有影响的对应询问的答案, 最后将矩形分成两个, 用双端队列将询问分到两个子矩形中, 递归求解.

分析复杂度, 设最大的矩形面积为 S, 首先每一个矩形的分割线选择较短的一条, 这样可以将长度限制在 \sqrt S 内. 每次求最短路的复杂度假设是 Dijkstra 的 S\log S, 那么一个矩形最短路的复杂度是 O(S \sqrt S \log S).

而每次分割会使得下一层的矩形面积至多是这一层的一半, 所以下一层的最短路复杂度是 O(\frac {S \sqrt S \log S}{\sqrt 2}). 层数一共是 O(\log S). 所以最短路的总复杂度是 O(S\sqrt S \log^2 S).

更新答案的复杂度也很好算, 每层需要回答询问最多 O(q) 个, 所以总复杂度是 O(q \log S).

如果这样算, 复杂度 O(S\sqrt S \log^2 S + q \log S).

第 Nxt_i 位是 i 后面的第一个确定的数字, 我们用一个数组 g_i 表示确定的位置 i 到 Nxt_i 的, 能填入 (i, Nxt_i) 的在 (a_i, a_{Nxt_i}) 区间内的数字个数.

设 f_{i, j} 为 [1, i] 的序列, i 在一个子序列, j 是另一个子序列的末尾的最小距离和, 这时 f_{i, j} 可以转移到 f_{i + 1, j} 和 f_{i + 1, i} 上.

如果看 f_{i, j} 的转移, 它可以由 f_{i - 1, j} 转移而来或 f_{}

设 g_{i} = f_{i, i - 1}, 则

发现可以用 Dis_{i, i + 1} 的前缀和进行优化, -->

CF1365G

有 1000 个数字 a_1, a_2,…, 你想知道对于每个 1 \leq i \leq 1000, 除了 a_i 以外其它所有数字 | 起来的结果.

你可以做至多 13 次下面的询问: 给定若干个位置, 交互库会返回这些位置对应数字 | 的结果.

首先考虑 20 次, 询问, 可以通过询问每个下标的第 i 二进制位为 1 或 0 的或和, 记为 f_{i, 0/1}, 共 20 个数, 查询时对于 x 的每个二进制位 i, 如果这一位是 1, 则统计 f_{i, 0}, 否则统计 f_{i, 1}.

之所以不能只对 x 为 0 的二进制位 i 统计 f_{i, 1}, 而不去统计二进制位为 0 的所有 f, 只用 10 次查询完成此题, 是因为可能存在 x', 对于 x 为 0 的所有位置, x' 都为 0, 但是 x' \neq x. 这样就会漏掉 x' 的元素没有统计.

所以尝试重新定义编号, 使得不存在 x' \neq x, 使得 x' | x = x. 这时必须保证编号的二进制表示中, 1 的数量相同. 假设新的编号二进制长度为 a, 每个编号含有 b 个 1. 那么我们就可以在 a 次查询内得到整个数列 P, 因为我们只要对于每个 i \in [1, a] 知道 f_{i, 1} 就可以了.

首先对于一对 a, b, 有 \binom {a}{b} 种编号, 需要满足 a \leq 13. 显然, b 相同的时候, a 越大, 编号集合越大, 所以 a 是 13. 而 b 是 a 的一半的时候, 集合最大, 所以取 b = 6 或 b = 7, 其集合大小都是 1716, 可以表示 1000 个下标.

unsigned List[2005], InList[20005], Ask[2005], n, Cnt(0);
unsigned long long f[15], Ans(0);
void DFS(unsigned Dep, unsigned Csd, unsigned Now) {
  if (Dep == 13) {
    if (Csd == 7) List[++Cnt] = Now;
    return;
  }
  if (13 - Dep < 7 - Csd) return;
  DFS(Dep + 1, Csd + 1, (Now << 1) + 1);
  DFS(Dep + 1, Csd, Now << 1);
}
int main() {
  n = RD(), DFS(0, 0, 0);
  for (register unsigned i(1); i <= n; ++i)
    InList[List[i]] = i;
  for (register unsigned i(0); i < 13; ++i) {
    Cnt = 0;
    for (register unsigned j(1); j <= n; ++j)
      if (List[j] & (1 << i)) Ask[++Cnt] = j;
    if (Cnt) {
      printf("? %u", Cnt);
      for (register unsigned j(1); j <= Cnt; ++j)
        printf(" %u", Ask[j]);
      putchar('\n');
      fflush(stdout);
      f[i] = RDll();
    }
    else f[i] = 0;
  }
  putchar('!');
  for (register unsigned i(1); i <= n; ++i) {
    Ans = 0;
    for (register unsigned j(0); j < 13; ++j)
      if (!(List[i] & (1 << j))) Ans |= f[j];
    printf(" %llu", Ans);
  }
  putchar('\n'), fflush(stdout);
  return Wild_Donkey;
}

例题

一个 n * n 的矩形 (n \leq 1000), 你可以进行如下操作至多 20 次:

选择若干行和若干列, 涂黑这些行列的交点.

使得最后只有主对角线没被涂黑.

两次操作可以将平行于对角线的一半的线上的交点转化为黑点, 这样就可以用 O(2\log n) 次操作完成转化.

例题

有 n 种物品, 第 i 种物品第一次选择的收益是 a_i, 之后每次选择的收益都是 b_i, 代价始终为 c_i. 你需要求出在总代价不超过 m 下收益的最大值.

有 Q 次修改, 第 j 次修改会在第 i 次修改 (i < j) 的基础上修改一个物品的两类收益. 你需要对于每次修改后输出答案.

修改构成一个树形结构, 对于每个修改相当于在树的 DFS 序的区间上修改, 而这个区间可以用线段树维护.

背包 DP 可以考虑新建一个数组 g_{i, j} 表示第 i 个物品强制选一次, 花费 j 的代价, 然后用它跑完全背包.

例题

有 n 个物品, 每个物品有大小和权值, 每次查询一个区间中的物品拿出来做大小为 W 的背包得到的结果. n, m \leq 10^4, W \leq 100, 区间不存在包含关系.

离线查询, 排序, 发现每个物品有贡献的询问一定是一个连续区间, 用线段树维护这个区间, 于是将每个物品插入对应节点上, 在线段树上 DFS, 过程中统计路径贡献, 每次到叶子就回答对应位置的询问.

Day9: 平衡树

Splay

过水已隐藏

Treap

过水已隐藏

非旋 Treap (FHQ)

跑得比 Splay 还慢, 可以持久化.

内核是普通 Treap 的分裂和合并 (Split & Merge).

插入时首先将树分裂成两部分, 这两部分和插入的单点合并成一棵树.

删除时将树分成删除的单点, 该点左边的树, 该点右边的树, 然后合并它左右的树即可.

实现 (是谁说 FHQ 短的):

const unsigned Base(1000000009);
unsigned Seed(1000000007), m, n, Cnt(0), A, B, C, D, t, Ans(0), Tmp(0);
struct Node {
  Node *LS, *RS;
  unsigned Val, RVal, Size;
}N[2000005], *CntN(N);
inline unsigned Rand() {
  return Seed *= Base;
}
void Upd(Node *x) {
  x->Size = 1;
  if (x->LS) x->Size += x->LS->Size;
  if (x->RS) x->Size += x->RS->Size;
}
pair<Node*, Node*> Split (Node *x) {
  register pair<Node*, Node*> TmpP;
  if(x->Val > C) {
    if(x->LS) {
      TmpP = Split(x->LS);
      x->LS = TmpP.second;
      Upd(x);
      return make_pair(TmpP.first, x);
    } else {
      TmpP.first = NULL, TmpP.second = x;
      return TmpP;
    }
  } else {
    if(x->RS) {
      TmpP = Split(x->RS);
      x->RS = TmpP.first;
      Upd(x);
      return make_pair(x, TmpP.second);
    } else {
      TmpP.first = x, TmpP.second = NULL;
      return TmpP;
    }
  }
}
Node *Merge(Node *x, Node *y) {
  if(!x) return y;
  if(!y) return x;
  if(x->RVal < y->RVal) {
    x->RS = Merge(x->RS, y);
    Upd(x);
    return x;
  } else {
    y->LS = Merge(x, y->LS);
    Upd(y);
    return y;
  }
}
void Insert() {
  C = B;
  register pair<Node*, Node*> TmpP(Split(N));
  register Node *LTr(TmpP.first), *RTr(TmpP.second), *Now(++CntN);
  Now->RVal = Rand(), Now->Val = B, Now->Size = 1; 
  Now = Merge(LTr, Now);
  Merge(Now, RTr);
}
void Delete() {
  C = B - 1;
  register pair<Node*, Node*> TmpP1(Split(N));
  C = B;
  register pair<Node*, Node*> TmpP2(Split(TmpP1.second));
  register Node *Now(TmpP2.first);
  if(Now) {
    Now = Merge(Now->LS, Now->RS);
    Now = Merge(TmpP1.first, Now);
  } else {
    Now = TmpP1.first;
  }
  Merge(Now, TmpP2.second);
}
void Rank() {
  register Node *now(N);
  while (now) {
    if(now->Val < B) {
      if(now->LS) D += now->LS->Size;
      ++D;
      now = now->RS;
    } else { 
      now = now->LS;
    }
  }
}
void Find() {
  register Node *now(N);
  while (now) {
    if(now->LS) {
      if(now->LS->Size < B) {
        B -= now->LS->Size;
      } else {
        now = now->LS;
        continue; 
      } 
    }
    if(B ^ 1) {
      --B, now = now->RS;
    } else {
      D = now->Val - 20000000;
      return;
    }
  }
}
int main() {
  m = RD();
  N[0].RVal = 0, N[0].Val = 0, N[0].Size = 0; 
  for (register unsigned i(1); i <= m; ++i) {
    A = RD();
    B = RDsg() + 20000000;
    switch (A) {
      case (1) :{
        Insert();
        break;
      }
      case (2) :{
        Delete(); 
        break;
      }
      case (3) :{
        D = 0, Rank();
        break;
      }
      case (4) :{
        B -= 19999999; 
        Find();
        break;
      }
      case (5) :{
        D = 0, Rank();
        B = D, Find();
        break;
      }
      case (6) :{
        ++B, D = 1, Rank();
        B = D, Find();
        break;
      }
    }
    if(A >= 3) {
      printf("%d\n", D);
    } 
  }
  return Wild_Donkey;
}

文艺平衡树

过水已隐藏

HNOI2012

给 n 个带权点, 支持两种操作:

• 两点之间连边

• 查询某点所在连通块中权值第 i 大的点

每个点维护一个平衡树, 连边可以用启发式合并在 O(n \log^2 n) 内解决问题.

当然也可以使用权值线段树合并, 在均摊 O(n \log^2 n) 时间内解决问题.

下面这份代码使用了平衡树启发式合并的做法.

unsigned a[100005], Fa[100005], Stack[100005], TopS(0), m, n, Cnt(0), A, B, D, t, Ans(0), Tmp(0);
char Op[5];
inline unsigned Find(unsigned x) {
  register unsigned Tmpx(x);
  while (Tmpx ^ Fa[Tmpx]) Stack[++TopS] = Tmpx, Tmpx = Fa[Tmpx];
  while (TopS) Fa[Stack[TopS--]] = Tmpx;
  return Tmpx;
}
struct Node {
  unsigned ValL, ValR, Size;
  Node* LS, * RS;
}N[300005], * Root[100005], * CntN, * C;
Node* Add(Node* x) {
  if (x->ValL == x->ValR) {
    (++CntN)->Size = 2;
    if (C->ValL < x->ValL) CntN->LS = C, CntN->RS = x;
    else CntN->RS = C, CntN->LS = x;
    CntN->ValL = CntN->LS->ValL;
    CntN->ValR = CntN->RS->ValR;
    return CntN;
  }
  ++(x->Size);
  if (C->ValL <= x->LS->ValR) x->LS = Add(x->LS);
  else x->RS = Add(x->RS);
  if (!(x->LS)) return x->RS;
  if (!(x->RS)) return x->LS;
  if (x->Size > 3) {
    if ((x->LS->Size * 3) < x->RS->Size) {
      register Node* TmpN(x->RS);
      x->RS = TmpN->RS;
      TmpN->RS = TmpN->LS;
      TmpN->LS = x->LS;
      x->LS = TmpN;
      TmpN->Size = TmpN->LS->Size + TmpN->RS->Size;
      TmpN->ValL = TmpN->LS->ValL;
      TmpN->ValR = TmpN->RS->ValR;
    }
    if ((x->RS->Size * 3) < x->LS->Size) {
      register Node* TmpN(x->LS);
      x->LS = TmpN->LS;
      TmpN->LS = TmpN->RS;
      TmpN->RS = x->RS;
      x->RS = TmpN;
      TmpN->Size = TmpN->LS->Size + TmpN->RS->Size;
      TmpN->ValL = TmpN->LS->ValL;
      TmpN->ValR = TmpN->RS->ValR;
    }
  }
  x->ValL = x->LS->ValL;
  x->ValR = x->RS->ValR;
  return x;
}
void DFS(Node* x) {
  if (x->ValL == x->ValR) { Stack[++TopS] = x - N;return; }
  if (x->LS) DFS(x->LS);
  if (x->RS) DFS(x->RS);
}
Node* Merge(Node* x, Node* y) {
  DFS(x);
  register Node* Cur(y);
  while (TopS) C = N + Stack[TopS--], Cur = Add(Cur);
  return Cur;
}
void Qry(Node* x) {
  if (B > x->Size) { Ans = -1; return; }
  if (x->ValL == x->ValR) { Ans = x - N; return; }
  if (x->LS) {
    if (x->LS->Size < B) B -= x->LS->Size, Qry(x->RS);
    else Qry(x->LS);
  }
  else Qry(x->RS);
}
signed main() {
  n = RD(), m = RD(), CntN = N + n;
  for (register unsigned i(1); i <= n; ++i) N[i].ValL = N[i].ValR = RD(), N[i].Size = 1, Root[i] = N + i, Fa[i] = i;
  for (register unsigned i(1); i <= m; ++i) {
    A = Find(RD()), B = Find(RD());
    if (A == B) continue;
    if (Root[A]->Size < Root[B]->Size) Fa[A] = B, Root[B] = Merge(Root[A], Root[B]);
    else Fa[B] = A, Root[A] = Merge(Root[B], Root[A]);
  }
  m = RD();
  for (register unsigned i(1); i <= m; ++i) {
    scanf("%s", &Op), A = RD(), B = RD();
    if (Op[0] ^ 'B') Qry(Root[Find(A)]), printf("%d\n", Ans);
    else { A = Find(A), B = Find(B); if (Root[A]->Size < Root[B]->Size) Fa[A] = B, Root[B] = Merge(Root[A], Root[B]); else Fa[B] = A, Root[A] = Merge(Root[B], Root[A]); }
  }
  return Wild_Donkey;
}

CF573E

给定一个长度为 n 的序列 A, 求子序列 B (可以为空), 使得 \displaystyle \sum_{i=1}^m iB_i 的值最大.

先考虑 O(n^2) DP, 设计 f_{i, j} 表示考虑前 i 位, 选择了 j 个数的, 最大 \displaystyle \sum_{k=1}^j kB_k.

状态转移方程很好写:

所以转移是 O(1), 总复杂度 O(n^2), 滚掉一维, 空间 O(n).

试图证明决策单调性, 即存在一个 j, 使得 f_{i - 1, j - 2} + (j - 1)A_i \geq f_{i - 1, j - 1}, 而对于所有 k \geq j, 都有 f_{i - 1, k - 1} + kA_i < f_{i - 1, k}.

使用打表法, 发现确实这样.

感性理解一下, 如果一个数字 i 在总共选择 j 个的时候被选择了, 那么选择更多的数的时候, 选择一个数的条件应该放宽, 所以就更能选 i 了.

实践是检验真理的唯一标准, 因为这样写过了, 所以存在决策单调性.

这样对于一个阶段, 它的 DP 值相对上一个阶段的变化就是:

• 在决策点 j 左边, DP 值不变

• 在 j 前面插入一个新值 f_{i - 1, j - 1} + jA_i

• 从 j 到 i - 1 的 DP 值向右平移一位, 然后加上等差数列 (j + 1)A_i, (j + 2)A_i, ..., iA_i.

用平衡树维护 DP 值即可, 因为二分决策点, 对 Mid 的一次判断需要单点查询, 是 O(\log n) 的, 所以总复杂度 O(n \log^2 n).

unsigned m, n, Cnt(0), SzLft(0), A, B, C, D, t, Tmp(0);
long long ATmp, TmpC, TmpN, Ans;
struct Node {
  Node* LS, * RS;
  long long Bot, K;
  unsigned Size;
}N[1000005], * CntN(N), * Root(N);
void PsDw(Node* x) {
  register long long LSTmp(0);
  if (x->LS) x->LS->K += x->K, x->LS->Bot += x->Bot, LSTmp = x->LS->Size;
  if (x->RS) x->RS->K += x->K, x->RS->Bot += x->Bot + x->K * LSTmp;
  x->K = x->Bot = 0;
}
void DFS(Node* x) {
  if (x->Size == 1) { Ans = max(Ans, x->Bot); return; }
  PsDw(x);
  if (x->LS) DFS(x->LS);
  if (x->RS) DFS(x->RS);
  return;
}
Node* Add(Node* x) {
  ++(x->Size);
  if (x->Size == 2) {
    x->LS = ++CntN, x->RS = ++CntN;
    x->RS->Bot = x->Bot, x->LS->Bot = TmpC;
    x->LS->Size = x->RS->Size = 1;
    x->K = x->Bot = 0;
    return x;
  }
  PsDw(x);
  if (x->LS) {
    if (A <= x->LS->Size) x->LS = Add(x->LS);
    else A -= x->LS->Size, x->RS = Add(x->RS);
  }
  else x->RS = Add(x->RS);
  if (!(x->LS)) return x->RS;
  if (!(x->RS)) return x->LS;
  if (x->Size > 3) {
    if ((x->LS->Size * 3) < x->RS->Size) {
      register Node* TmpNd(x->RS);
      PsDw(TmpNd);
      x->RS = TmpNd->RS;
      TmpNd->RS = TmpNd->LS;
      TmpNd->LS = x->LS;
      x->LS = TmpNd;
      TmpNd->Size = TmpNd->LS->Size + TmpNd->RS->Size;
    }
    if ((x->RS->Size * 3) < x->LS->Size) {
      register Node* TmpNd(x->LS);
      PsDw(TmpNd);
      x->LS = TmpNd->LS;
      TmpNd->LS = TmpNd->RS;
      TmpNd->RS = x->RS;
      x->RS = TmpNd;
      TmpNd->Size = TmpNd->LS->Size + TmpNd->RS->Size;
    }
  }
  return x;
}
void Chg(Node* x, unsigned Cnt) {
  if (x->Size <= Cnt) {
    x->Bot += ATmp * SzLft;
    x->K += ATmp;
    SzLft += x->Size;
    return;
  }
  PsDw(x);
  if (x->RS) {
    if (x->RS->Size < Cnt) {
      Chg(x->LS, Cnt - x->RS->Size);
      Chg(x->RS, x->RS->Size);
    }
    else Chg(x->RS, Cnt);
  }
  else Chg(x->LS, Cnt);
}
long long Qry(Node* x) {
  if (x->Size == 1) return x->Bot;
  PsDw(x);
  if (x->LS) {
    if (x->LS->Size >= A) return Qry(x->LS);
    else { A -= x->LS->Size; return Qry(x->RS); }
  }
  else return Qry(x->RS);
}
signed main() {
  n = RD();
  N->Bot = 0xafafafafafafafaf, N->Size = 1;
  TmpC = 0, A = 1, Root = Add(Root);
  TmpC = RDsg(), A = 2, Root = Add(Root);
  for (register unsigned i(2); i <= n; ++i) {
    ATmp = RDsg();
    register unsigned L(1), R(i), Mid;
    while (L ^ R) {
      Mid = ((L + R) >> 1);
      A = Mid, TmpC = Qry(Root) + Mid * ATmp, A = Mid + 1, TmpN = Qry(Root);
      if (TmpC > TmpN) {//Choose
        R = Mid;
      }
      else {  //Not
        L = Mid + 1;
      }
    }
    A = L, TmpC = Qry(Root) + L * ATmp, A = L + 1, Root = Add(Root);
    SzLft = L + 1, Chg(Root, i + 1 - L);
  }
  DFS(N);
  printf("%lld\n", Ans);
  return Wild_Donkey;
}

Day10: 可持久化

可持久化线段树

过水已隐藏

CF323C

给定两个长度均为 n 的排列.

unsigned a[100005], m, n, Cnt(0), t, Ans(0), Tmp(0);
unsigned long long A, B, C, D;
struct Juice {
  unsigned Val, Cost, Limit;
  inline const char operator< (const Juice& x)const {
    return this->Val < x.Val;
  }
}J[100005];
struct Node {
  Node* LS, * RS;
  unsigned long long Cost, V;
}N[4000005], * Root[100005], * CntN(N);
void Udt(Node* x) {
  x->V = x->Cost = 0;
  if (x->LS) x->V += x->LS->V, x->Cost += x->LS->Cost;
  if (x->RS) x->V += x->RS->V, x->Cost += x->RS->Cost;
}
void Add(Node* x, Node* y, unsigned L, unsigned R) {
  if (L == R) {
    y->Cost = B * C;
    y->V = C;
    if (x) y->V += x->V, y->Cost += x->Cost;
    return;
  }
  register unsigned Mid((L + R) >> 1);
  if (A <= Mid) {
    if (x) {
      y->RS = x->RS;
      Add(x->LS, y->LS = ++CntN, L, Mid);
    }
    else Add(NULL, y->LS = ++CntN, L, Mid);
  }
  else {
    if (x) {
      y->LS = x->LS;
      Add(x->RS, y->RS = ++CntN, Mid + 1, R);
    }
    else Add(NULL, y->RS = ++CntN, Mid + 1, R);
  }
  return Udt(y);
}
void Qry(Node* x, unsigned L, unsigned R) {
  if (L == R) {
    C += A * x->Cost / x->V;
    return;
  }
  register unsigned Mid((L + R) >> 1);
  if (x->LS) {
    if (x->LS->V >= A) return Qry(x->LS, L, Mid);
    else {
      A -= x->LS->V;
      C += x->LS->Cost;
    }
  }
  Qry(x->RS, Mid + 1, R);
}
signed main() {
  n = RD(), m = RD(), Root[0] = N;
  for (register unsigned i(1); i <= n; ++i)
    J[i].Val = RD(), a[i] = J[i].Cost = RD(), J[i].Limit = RD();
  sort(J + 1, J + n + 1), sort(a + 1, a + n + 1), Cnt = unique(a + 1, a + n + 1) - a - 1;
  for (register unsigned i(n); i; --i)
    A = lower_bound(a + 1, a + Cnt + 1, J[i].Cost) - a, B = J[i].Cost, C = J[i].Limit, Add(Root[i + 1], Root[i] = ++CntN, 1, Cnt);
  for (register unsigned i(1); i <= m; ++i) {
    B = RD(), D = RD();
    register unsigned BL(0), BR(n), BMid;
    while (BL ^ BR) {
      BMid = (BL + BR + 1) >> 1, A = D, C = 0;
      if (Root[BMid]->V < A) {
        BR = BMid - 1;
        continue;
      }
      Qry(Root[BMid], 1, Cnt);
      if (C > B) BR = BMid - 1;
      else BL = BMid;
    }
    if (!BL) printf("-1\n");
    else printf("%u\n", J[BL].Val);
  }
  return Wild_Donkey;
}

P2839

给一个序列, 每次求序列的子区间, 满足左端点在 [a, b] 之间, 右端点在 [c, d] 之间的最大中位数. 和一般定义不同的是, 本题中偶数个元素的中位数定义为第 \frac n2 个数.