Wings 的博客Wings 的博客
归档 系列 分类 标签 关于 友链 开往
Wings 的博客Wings 的博客

目录

目录

2021 牛客多校第一场 训练记录 暨 补题

Wings avatarWings  收录于  类别 ACM
     约 2439 字   预计阅读 11 分钟    次阅读     条评论  

太弱小了, 没有力量.

蒋叶桢打疫苗去了, 我吃饭迟到了一会, 期间张炀杰疯狂开题. 到后我给张炀杰重新翻译了D签到题, 然后看到了另一个签到B, 分别 21min A, 28min 1A. 然后一起想了F, 数位dp假半天发现鸽子原理搞搞只需要处理很小的部分, 张炀杰上机, 48min A. 蒋叶桢来后看了H, 发现是个FFT板题, 但是期间出了一点小问题; 开了A博弈和I dp, dp没仔细想先去和张炀杰推博弈了. 蒋叶桢H 2h17min A, 之后全员博弈. 发现并不会做, 然后蒋叶桢暴力跑了小范围数据想找规律, 最后看到数据量较小, 决定打表. 5min后表跑完了, 3h21min A. 全员不会期望dp, 写了个方程发现倒序枚举好像是对的. 最后各种优化都没搞出来.

  1. 学习期望dp

好像就没啥了…

两堆石子, 个数为$n, m$, 每次从一堆拿$k(k>0)$个, 从另一堆拿$s\times k(s \ge 0)$ 个, 不能操作输. $T$组询问, 问先后手必胜.

$1 \le n, m \le 5 \times 10^3, 1 \le T \le 10^4$

打表会发现(确实是打了表才发现的), 一堆石子个数为 $i$, 最多只有一个 $j$, 使得两堆石子 $i, j$ 必败. 下面证明. 假设 $(i, j_1), (i, j_2)$ 必败, 不妨设 $i \le j_1 < j_2$, 状态 $(i, j_2)$ 可以转移到必败态 $(i, j_1)$, 即第二堆拿 $j_2 - j_1$ 个, 第一堆不拿($s=0$). 这样 $(i, j_2)$ 是必胜态, 和必败态矛盾.

然后就可以去筛了. $(i, j)$ 必败, 枚举 $k, s$, $(i+k, j+sk), (i+sk, j+k)$ 必败. 必败态 $O(n)$ 个, 枚举 $k$ $O(n)$, 枚举 $s$ $O(\log n)$, 总复杂度 $O(n^2 \log n)$. 只需要统计 $i \le j$ 的, 可进一步优化(否则牛客上过不去笑死, 本地跑 500ms 以内, 本地这样优化 200ms 以内)

cpp

int T, n, m, dp[MAXN][MAXN];

int main() {
  scanf("%d", &T);
  n = 5e3;
  dp[0][0] = 0;
  for (int i = 0; i <= n; i++)
    for (int j = i; j <= n; j++)
      if (!dp[i][j]) {
        for (int k = 1; i + k <= n; k++)
          for (int sk = 0; j + sk <= n; sk += k)
            dp[min(i+k, j+sk)][max(i+k, j+sk)] = 1;
        for (int k = 1; j + k <= n; k++)
          for (int sk = 0; i + sk <= n; sk += k)
            dp[min(i+sk, j+k)][max(i+sk, j+k)] = 1;
      }
  while (T--) {
    scanf("%d%d", &n, &m);
    puts(dp[min(n, m)][max(n, m)] ? "Alice" : "Bob");
  }
  return 0;
}

给一个大小为n的排列P, 两个人在上面选数, 要求如下:

  • 某个人选的数的下标要比之前这个人选的大
  • 每次选的数值要比之前两个人选的数都大

每次选都是等概率从可以选的数中选一个, 第一个人随便选(选择每个数的概率都是$\frac{1}{n}$). 最后不能选了结束. 问结束时期望两人一共选多少个数.

!注意下标是比自己之前选的大, 不和对方比较.

深入理解期望DP

这个题是两个人在走, 所以状态要两维, 设 $dp(i, j)$ 表示第一个人在$i$, 第二个人在$j$, 期望还需要走多少步结束. 还需要考虑是哪一个人走, 由于是排列, 并且满足每次选的数比所有人上次的大, 所以比对手大, 这样直接判断 $a_i, a_j$ 的大小关系就可以知道是谁在走了.

方程分两部分转移

  • $a_i > a_j$, 第二个人走: $dp(i, j) = 1 + \frac{1}{c_1} \sum dp(i, k_1)$, 其中, $k_1$ 满足 $k_1 > j, a_{k_1} > a_i$, $c_1$ 是满足该条件的 $k$ 的个数
  • $a_i < a_j$, 第一个人走: $dp(i, j) = 1 + \frac{1}{c_2} \sum dp(k_2, j)$, 其中, $k_2$ 满足 $k_2 > i, a_{k_2} > a_j$, $c_2$ 是满足该条件的 $k$ 的个数

朴素转移复杂度 $O(n^3)$, 需要优化. 显而易见, $k_1$ 要满足比 $j$ 大, 且 $k_1, j$ 都是第二维, $k_2$ 和 $i$ 同理. 那么可以逆序枚举, 用前缀和(后缀和)的思想来加速转移, 同时可知, $1/c_1 \sum dp(i, k_1)$ 和 $j$ 无关(关系已经通过转移顺序搞掉了).

设 $f(i) = \sum dp(i, k_1), c_1(i)$ 为第一个方程中的$c_1$. 对称地, 再设 $g(j) = \sum dp(k_2, j), c_2(j)$. 以第一个方程为例, 现在还需要考虑的是 $dp(i, k_1)$ 的另一个条件 $a_{k_1} > a_i$. 只有这样的状态, 才能够对 $f(i)$ 产生贡献. 然后会发现, 满足这个条件的状态, 不就是第二个方程吗? 所以做完第二个方程, 即 $a_i < a_j$ 的 $dp(i, j)$ 后, 把它加到 $f(i)$ 中, 同时 $c_1(i)+1$. 另一边同理.

这样就把复杂度降到了 $O(n^2)$.

答案需要枚举一下第一个人选的位置, 第二个人在0, 即 $dp(i, 0)$, 第一个人等概率选, 所以最后是 $\frac{1}{n} \sum_{i=1}^n dp(i, 0)$

cpp

int mult(LL a, LL b) {
  return a * b >= P ? a * b % P : a * b;
}
int pls(LL a, LL b) {
  return a + b >= P ? a + b - P : a + b;
}

int power(int a, int b = P-2) {
  int res = 1;
  while (b) {
    if (b&1)
      res = mult(res, a);
    a = mult(a, a);
    b >>= 1;
  }
  return res;
}

int T, n, inv[MAXN], c1[MAXN], c2[MAXN], a[MAXN], dp[MAXN][MAXN], f[MAXN], g[MAXN];

int main() {
  scanf("%d", &n);
  inv[0] = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    inv[i] = power(i);
  }

  for (int i = n; ~i; i--) {
    for (int j = n; ~j; j--) {
      if (a[i] > a[j]) {
        dp[i][j] = pls(1, mult(inv[c1[i]], f[i]));
        g[j] = pls(g[j], dp[i][j]);
        c2[j]++;
      }
      else if (a[i] < a[j]) {
        dp[i][j] = pls(1, mult(inv[c2[j]], g[j]));
        f[i] = pls(f[i], dp[i][j]);
        c1[i]++;
      }
    }
  }

  int ans = 0;
  for (int i = 1; i <= n; i++)
    ans = pls(ans, dp[i][0]);
  ans = mult(inv[n], ans);
  printf("%d\n", ans);

  return 0;
}

给出两个长度为 $n$ 的序列 $A, B$, 恰好交换 $A$ 中的两个数 $k$ 次, 使得 $\sum_{i=1}^n \mid A_i - B_i \mid$ 最大.

$2 \le n \le 5 \times 10^5, 0 \le k \le 10^18, -10^8 \le A_i, B_i \le 10^8$

首先有一个很重要的贡献转换, 考察 $\min A_i - B_i \mid$ 这个式子, 如果 $A_i > B_i$, 那么 $A_i$ 对答案的贡献是 $+A_i$, $B_i$ 对答案的贡献是 $-B_i$; 如果 $A_i < B_i$, 那么 $A_i$ 对答案的贡献是 $-A_i$, $B_i$ 对答案的贡献是 $+B_i$. 这样可以知道, 两个序列里的数, 对答案的贡献要么是正的自己, 要么是负的自己, 这样就把本身"绑在一起"的 $A_i, B_i$ 贡献"分开"了. 同时还需要满足的条件是正的符号个数等于负的符号个数, 都等于 $n$. 不考虑次数限制, 相当于给这 $2n$ 个数分配正负号各 $n$ 个, 使得他们的和最大. 所以排序, 最大的 $n$ 个正号, 剩下 $n$ 个负号即可.

把最优的符号分配方案放到原来的顺序上看, 每个位置 $i$ 上的两个数可能是如下情况:

-++-
+-+-

其中第一第二就是最优的了, 而第三第四, 即 ++ 和 --, 交换以后才是更优的. 由于正负号个数相等的性质, ++ 和 -- 的个数是相等的, 所以可以交换, 使得全部变成 +- 和 -+.

现在再来考虑恰好 $k$ 次交换的限制.

当 $n > 2$ 时, 根据鸽子原理, 一定有 $2$ 个相同的符号. 让他们交换, 不会改变答案. 所以恰好 $k$ 次在 $n > 2$ 的情况下是至多 $k$ 次. $n = 2$ 特判, 不再考虑.

接下来的问题是, 交换哪些更优? 稍微推一下:

假设 $i$ 位置最优贡献是两个 +, 更大的原本对答案的贡献依然是+, 更小的原本对答案的贡献是-, 和某个 - 交换后对答案的贡献是+. 也就是说, 对于 $i$ 这个位置, 交换能够使答案增加 $2 \min \{ A_i, B_i \}$

对于两个 - 也这样考虑, 交换能够使答案增加 $-2 \max \{ A_j, B_j \} = 2 \min \{-A_j, -B_j\}$

他们是独立的, 所以只需要确定两个数的符号, 然后看看需不需要交换, 如果需要, 看看是+还是-, 分开排序, 取最大即可.

复杂度 $O(n \log n)$

cpp

int n, k, a[MAXN], b[MAXN], sgn[2][MAXN]; // 0+, 1-
struct Num {
  int flag, val, id;
  Num(int flag, int val, int id):flag(flag), val(val), id(id) {}
  bool operator < (const Num &N) const {
    return val == N.val ? id == N.id ? flag < flag : id < N.id : val < N.val;
  }
};
vector<Num> all;
struct Par {
  int a, b;
  Par(int a, int b):a(a), b(b) {}
  int getMin() {
    return min(a, b);
  }
  bool operator < (const Par &P) const {
    return min(a, b) > min(P.a, P.b);
  }
};
vector<Par> pos, neg;

LL sum = 0;

int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    all.emplace_back(0, a[i], i);
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", b + i);
    all.emplace_back(1, b[i], i);
  }

  if (n == 2 && k&1)
    swap(a[1], a[2]);

  for (int i = 1; i <= n; i++)
    sum += abs(a[i] - b[i]);

  if (n > 2) {
    sort(all.begin(), all.end());
    for (int i = 0; i < n; i++)
      sgn[all[i].flag][all[i].id] = 1;
    for (int i = 1; i <= n; i++) if (sgn[0][i] == sgn[1][i]) {
      if (sgn[0][i] == 0)
        pos.emplace_back(a[i], b[i]);
      else
        neg.emplace_back(-a[i], -b[i]);
    }
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());
    for (int i = 0; i < min(k, (int)pos.size()); i++)
      sum += 2 * (pos[i].getMin() + neg[i].getMin());
  }

  printf("%lld\n", sum);
  return 0;
}

$T$ 组数据. 给出长度为 $n$ 的数组 $a$, 下标从 $0$ 开始, 且 $a_i$ 等概率从 $[0, n-1]$ 中选取. 对这个数组进行任意排序, 使得

$$\sum_{i=0}^{n-1} \sqrt{a_i - i}$$

尽量小. 当满足 $T$ 组数据程序所求值与最小值的平均误差不超过 $4\%$ 的时候认为AC.

$100 \le T \le 500, 10 \le n \le 1000$

网上一堆做法是什么多次冒泡, 完全不懂原理在哪, 也没个靠谱的解释. 大概就看到这个题可以这么乱搞, 就抄一抄, 好! 我补完了!

如果要求最小而不是尽量小, 即得到准确的最小值, 那么实际上是一个二分图最优匹配问题.

把下标当作左边的点, 值当作当作右边点, 两两之间连边, 边权为 $|a_i - i|$. 然后跑二分图最优匹配就行了.

紫书上讲背包的时候, 先讲了一个错误的贪心, 并且说明了贪心是可以得到近似解的. 这里也采用同样的思路. 直接贪心选取权值小的边, 由于数据随机, 所以得到的解不会和答案偏差太多.

然后就过了. 虽然不会算, 但是至少比什么多次冒泡有道理多了.

注意排序用桶排, 否则 $O(Tn^2\log n)$ 会T.

总复杂度$O(Tn^2)$

cpp

int T, n, a[MAXN], reranged[MAXN];;
bool vis[MAXN];

vector<PII> t[MAXN];

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; i++)
      reranged[i] = -1, t[i].clear();
    for (int i = 0; i < n; i++)
      scanf("%d", a + i);
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        t[abs(a[i]-j)].emplace_back(i, j);
    for (int j = 0; j < n; j++)
      for (auto[i, pos] : t[j])
        if (!(vis[i] || reranged[pos] >= 0))
          reranged[pos] = i, vis[i] = 1;
    for (int i = 0; i < n; i++)
      printf("%d%c", a[reranged[i]], " \n"[i == n-1]);
  }
  return 0;
}

$n \times m$ 的棋盘如上, 每个格子放了一些管道如下

可以边走边旋转管道, 要求从 $(0, 1)$ 向下走到 $(1, 1)$, 再走到 $(n, m)$, 最后向下走到 $(n+1, m)$. 问是否有解, 有的话输出路径(包括旋转).

$T$ 组数据

$1 \le T \le 10^4, 2 \le n \le m \le 1000, \sum nm \le 10^6$

比赛时好像没多少人过, 我们也没开.

我最讨厌搜索题了, 代码老长, 写又写不来, 还要出一堆bug, 难受.

没啥好讲的, 拆四个方向进入的点, 然后BFS就没了.

老问题, BFS一加入就要设置vis=1, 又没注意, T飞了.

奇怪的常量表, jyz说他大受桢撼 QAQ

cpp

const int MAXN = 1e3 + 10;
const int DX[] = {0, 0, 1, -1};
const int DY[] = {1, -1, 0, 0};
const int RIGHT = 0;
const int LEFT = 1;
const int DOWN = 2;
const int UP = 3;
const int BEND = 0;
const int STRAIGHT = 1;
const int TYPE[] = {0, 0, 0, 0, 1, 1};

int T, n, m, layout[MAXN][MAXN];
VI TO[5][5];  //to[i][j] 从方向i通过类型j的管道能够出去的方向

struct Node {
  int x, y, d;
};
queue<Node> Q;

struct Node2 {
  int x, y, in, out;
};
vector<Node2> ans;

Node path[MAXN][MAXN][4];
bool vis[MAXN][MAXN][4];

bool bfs() {
  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= m; j++)
      for (int k = 0; k < 4; k++)
        vis[i][j][k] = 0, path[i][j][k] = Node{0, 0, 0};
  while (!Q.empty())
    Q.pop();
  Q.push(Node{0, 1, DOWN});
  while (!Q.empty()) {
    auto[x, y, d] = Q.front();
    Q.pop();
    vis[x][y][d] = 1;
    if (x == n+1 && y == m && d == DOWN)
      return true;
    for (int dir : TO[d][TYPE[layout[x][y]]]) {
      int nx = x + DX[dir], ny = y + DY[dir];
      if ((nx && ny && nx <= n && ny <= m && !vis[nx][ny][dir]) || (nx == n+1 && ny == m)) {
        Q.push(Node{nx, ny, dir}), path[nx][ny][dir] = Node{x, y, d}, vis[nx][ny][dir] = 1;
      }
    }
  }
  return false;
}

vector<string> sans;
char str[MAXN];

int getType(int in, int out) {
  if (in == out) {
    if (in == LEFT || in == RIGHT)
      return 4;
    else
      return 5;
  }
  if ((in == RIGHT && out == UP) || (in == DOWN && out == LEFT))
    return 0;
  if ((in == DOWN && out == RIGHT) || (in == LEFT && out == UP))
    return 1;
  if ((in == UP && out == RIGHT) || (in == LEFT && out == DOWN))
    return 2;
  if ((in == RIGHT && out == DOWN) || (in == UP && out == LEFT))
    return 3;
  return -7;
}

int getRotate(int in, int out, int type) {
  int t = getType(in, out);
  if (t == -7)
    return -7;
  if (t >= 4)
    return t != type;
  else
    return (4 + t - type) % 4;
}

int main() {
  layout[0][1] = 5;
  TO[LEFT][STRAIGHT].push_back(LEFT);
  TO[RIGHT][STRAIGHT].push_back(RIGHT);
  TO[UP][STRAIGHT].push_back(UP);
  TO[DOWN][STRAIGHT].push_back(DOWN);
  TO[LEFT][BEND].push_back(UP);
  TO[LEFT][BEND].push_back(DOWN);
  TO[RIGHT][BEND].push_back(UP);
  TO[RIGHT][BEND].push_back(DOWN);
  TO[UP][BEND].push_back(RIGHT);
  TO[UP][BEND].push_back(LEFT);
  TO[DOWN][BEND].push_back(LEFT);
  TO[DOWN][BEND].push_back(RIGHT);
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= m; j++)
        scanf("%d", &layout[i][j]);
    if (bfs()) {
      puts("YES");
      ans.clear();
      sans.clear();
      int x = n+1, y = m, d = DOWN;
      do {
        auto[xx, yy, dd] = path[x][y][d];
        ans.push_back(Node2{xx, yy, dd, d});
        x = xx, y = yy, d = dd;
      } while (!(x == 0 && y == 1 && d == DOWN));
      ans.pop_back();
      reverse(ans.begin(), ans.end());
      for (auto[x, y, in, out] : ans) {
        int r = getRotate(in, out, layout[x][y]);
        if (r) {
          sprintf(str, "1 %d %d %d\n", r * 90, x, y);
          string s(str);
          sans.push_back(s);
        }
        sprintf(str, "0 %d %d\n", x, y);
        string s(str);
        sans.push_back(s);

        layout[x][y] = getType(in, out);
      }
      printf("%d\n", (int)sans.size());
      for (string s : sans)
        printf("%s", s.c_str());
    }
    else
      puts("NO");
  }
  return 0;
}

$n$ 个车站, 第 $i$ 个车站到下一个 $(i+1)$ 车站的用时为 $cost_i$. 车站在时间段 $[u_i, v_i]$ 开放, 开放时段才能够停靠. 如果到达车站的时刻在开放时段前, 可以等待至开放并成功停靠; 如果到达车站的时刻在开放时段后, 则停靠失败. $q$次询问,

  1. 区间 $[l, r]$, 问从车站 $l$ 到车站 $r$, 是否都能够成功停靠
  2. 修改一个车站的开放时段
  3. 修改从一个车站出发到下一个车站的用时.

$T$ 组数据.

$1 \le T \le 10^4, 2 \le n \le 10^6, 1 \le q \le 10^6, 1 \le u_i, v_i, cost_i \le 10^9$

区间问题, 考虑线段树. 区间查询, 单点修改.

考虑两个区间怎么合并. 注意到"有向", 合并不满足交换律.

叶子节点, 也就是一个车站, 有开放时间段 $[u_i, v_i]$, 按照贪心的思想, 越早发车, 越有可能不超过下一个车站的关闭时间 $v_{i+1}$. 同时越有可能不超过再下一个车站的关闭时间, 以此类推. 那么对于一个连续的车站区间来说, 在第一个站会有一个最晚发车时间, 使得晚于这个时间发车, 不能完全走完这一段区间. 我们把这个时间记录在线段树的节点中, 记为 $limit$. 再对一个区间记录一个最短时刻 $earlist$, 表示完成这个区间的最小时刻. 根据贪心, 如果用在最小时刻 $earlist$ 完成一个区间并到下一个站(时刻 $earlist + cost$), 却不能再下一个站的最晚发车时间 $limit$ 前到达, 那么就无法到达下一个站. 考虑下一个区间, 也是一样, 如果不能在下一个区间的 $limit$ 前到达下一个区间的第一个站, 那么就无法完成这两个区间. 无法完成的话合并就打个失败的标记, 下面考虑能够完成, 区间怎么合并.

为方便在叙述合并区间的时候, 左边的区间称为左区间, 右边的区间称为右区间, 合并成的区间称为大区间.

大区间的 $limit$ 可能来自左区间的 $limit$, 同时需要考虑右区间的限制, 记 $cost$ 为这个区间最后一个站到下一个站(区间外某个站)的用时, $precost$ 为第一个站到最后一个站的 $cost$ 前缀和(注意这个 $precost$ 不是经过这个区间的用时, 因为车可能在某个站点等待开放, 导致实际时间比 $precost$ 长). 设 $latist_{lr} = limit_r - cost_l$, 即满足右区间条件推出来的, 左区间到最后一个站的最晚到达时间. 而满足左区间条件推出来的最晚到达时间为 $latist_{ll} = limit_l + precost_l + t$ ($t \ge 0$ 是等待时间), 大区间需要同时满足左右区间的条件, 大区间中, 最晚到达左区间最后一个点的时间 $latist = limit + precost_l + t’$ 需要对 $latist_{ll}$ 和 $latist_{lr}$ 取 min, 即 $limit + precost_l + t = \min \{ limit_l + precost_l + t, limit_r - cost_l \}$. 有 $limit + t’ = \min \{limit_l + t, limit_r - precost_l - cost_l\}$.

(麻了, 不会推, 天晓得我怎么写了个 $limit = \min \{ limit_l, limit_r - precost_l - cost_l \}$ 然后就过了. 人已经傻了.)

$earlist, cost, precost$ 直接推就行.

笑死根本不会做但是过了, 复杂度 $O((n+q) \log n)$

cpp

int T, n, q;
LL L[MAXN], R[MAXN], cost[MAXN];
struct Node {
  int l, r, mid;
  LL earlist, cost, precost, limit;
} t[MAXN << 2];

void updateNode(int u, LL L_, LL R_, LL cost_) {
  t[u].earlist = L_, t[u].cost = cost_, t[u].precost = 0, t[u].limit = R_;
}

Node merge(int l, int r, Node LNode, Node RNode) {
  Node res;
  res.l = l, res.r = r, res.mid = (l+r)>>1;
  if (LNode.earlist == -1 || RNode.earlist == -1 || LNode.earlist + LNode.cost > RNode.limit)
    res.earlist = res.limit = -1;
  else {
    res.limit = min(LNode.limit, RNode.limit - LNode.cost - LNode.precost);
    res.earlist = max(LNode.earlist + LNode.cost + RNode.precost, RNode.earlist);
  }
  res.cost = RNode.cost;
  res.precost = LNode.precost + LNode.cost + RNode.precost;
  return res;
}

void pushUp(int u) {
  t[u] = merge(t[u].l, t[u].r, t[LCH(u)], t[RCH(u)]);
}

void build(int l, int r, int u) {
  t[u] = Node{l, r, (l+r)>>1};
  if (l == r)
    updateNode(u, L[l], R[l], cost[l]);
  else {
    build(l, t[u].mid, LCH(u));
    build(t[u].mid+1, t[u].r, RCH(u));
    pushUp(u);
  }
}

void init(int _n) {
  build(1, _n, 1);
}

void update(int pos, LL L_, LL R_, LL cost_, int u = 1) {
  if (t[u].l == t[u].r)
    updateNode(u, L_, R_, cost_);
  else {
    if (pos <= t[u].mid)
      update(pos, L_, R_, cost_, LCH(u));
    else
      update(pos, L_, R_, cost_, RCH(u));
    pushUp(u);
  }
}

Node query(int l, int r, int u = 1) {
  if (t[u].l == l && t[u].r == r)
    return t[u];
  if (l > t[u].mid)
    return query(l, r, RCH(u));
  if (r <= t[u].mid)
    return query(l, r, LCH(u));
  else {
    Node lch = query(l, t[u].mid, LCH(u));
    Node rch = query(t[u].mid+1, r, RCH(u));
    return merge(l, r, lch, rch);
  }
}

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
      scanf("%lld", L + i);
    for (int i = 1; i <= n; i++)
      scanf("%lld", R + i);
    for (int i = 1; i < n; i++)
      scanf("%lld", cost + i);
    cost[n] = 0;
    init(n);
    scanf("%d", &q);
    while (q--) {
      int op, pos, l, r;
      LL LL, RR, w;
      scanf("%d", &op);
      if (op == 0) {
        scanf("%d%d", &l, &r);
        Node res = query(l, r);
        puts(res.earlist != -1 ? "Yes" : "No");
      }
      else if (op == 1) {
        scanf("%d%lld", &pos, &w);
        cost[pos] = w;
        update(pos, L[pos], R[pos], cost[pos]);
      }
      else {
        scanf("%d%lld%lld", &pos, &LL, &RR);
        L[pos] = LL, R[pos] = RR;
        update(pos, L[pos], R[pos], cost[pos]);
      }
    }
  }
  return 0;
}
更新于 2021-07-24
 训练, 牛客多校
 | 主页