不难发现，本题我们需要一种 $O(qn)$ 的方法来获得满分。最暴力的逐项二分答案+模拟的做法就先不多说了，期望得分 30。

在不能暴力计算的情况下，我们可以动手模拟一下，看看在当前未求出答案的这些里面，哪一个是最好解决的。

此外，题目的“落在 $i$ 和 $i+1$ 之间，然后选择击杀顺序”这个也可以直接更改建模为：从 $i$ 和 $i+1$ 当中确定最初击杀谁，这之后的策略就是固定的了。如果设 $f_i$ 为最先击杀 $i$ 号梦魔，击杀所有梦魔所需要的初始攻击力，则 $p_i=\min(f_i,f_{i+1})$。

显然我们可以从 $a$ 的大小下手，在当前未解决答案的里面挑选最大的 $a$，不放设为 $a_u$，从他开始击杀梦魔的话，必须要 $a_u$ 的攻击力，此时有 $f_u=a_u$。接下来我们就可以以 $u$ 为轴点，将原始问题以 $u$ 进行划分，按照左右两侧来进行解决。

分治的过程中，也是找左右两个子区间的最大值，从这个位置开始击杀是最容易推导的。

我们以左子区间的最大值为例，假设这个时候的轴点是 $l_u$，如果能够成功击杀 $l_u$ 号梦魔，则可以成功击杀 $[1,u-1]$ 的所有梦魔，获得他们的 $b_i$。而如果要击杀所有梦魔，主要的瓶颈有两个：

• 击杀 $l_u$ 本身就需要 $a_{l_u}$ 的初始攻击力；
• 击杀了 $1,...,u-1$ 之后，还需要成功击杀 $u$ 号梦魔才行，也就是说初始攻击力加上 $\sum\limits_{i=1}^{u-1}b_i$ 不小于 $a_u$ 才行。

上述两者情况所需初始攻击力的最大值即为 $f_i$。

综上，一个基础的分治过程我们就有了，每次都从未解决的子区间寻找 $a$ 最大的梦魔，确定其答案之后，以其为轴点左右分治。需要注意上述两种情况的答案当中，第二种是需要在分治向下的过程当中继承下去的。

接下来就看分治的过程是怎么样的了。

方案 0：暴力遍历找区间最大值

很遗憾，这种方法非常轻易就能卡掉，因为每次找最大值的复杂度是 $O(n)$ 的（例：$a$ 的值单调递增或者递减），此时分治复杂度为 $T(n)=T(n-1)+O(n)=O(n^2)$ 的，在子任务 2 中可以被卡掉，期望得分和暴力一样是 30。

方案 1：稀疏表或线段树

稀疏表求 RMQ 是 $O(n\log n)$ 预处理，$O(1)$ 单次查询，而线段树是 $O(n)$ 预处理 $O(\log n)$ 查询，总时间复杂度为 $O(q\log n)$，期望得分 70。

其中 RMQ 如果用状压+非常规分块做优化（俗称“四毛子”），则可以做到 $O(n)$ 预处理 $O(1)$ 查询，但是常数比较大，不保证一定能过。

方案 2：单调栈+笛卡尔树

笛卡尔树的相关知识点可参考 OI-Wiki，模板可参考洛谷，对单调栈稍作修改即可构造对应的笛卡尔树，每个子树的根节点和本题当中的分治轴点是完全重合的。

因此我们只需要 $O(n)$ 预处理出来笛卡尔树，然后在此基础上完成上述的分治求解过程即可，每次的分治轴点就是子树根节点，往下分治找轴点时就是左右子节点，因此分治过程一样是 $O(n)$ 的。

总时间复杂度为 $O(qn)$，期望得分 100。

最后注意多测清空的细节即可，保证清空复杂度不超过 $O(qn+\sum k)$（也就是 $5\times 10^5$）即可。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
typedef long long i64;
inline i64 rd()
{
    i64 k = 0, f = 1;
    char s = getchar();
    while (s < '0' || s > '9') f = (s == '-') ? 0 : f, s = getchar();
    while (s >= '0' && s <= '9') k = (k << 1) + (k << 3) + (s ^ '0'), s = getchar();
    return f ? k : -k;
}
inline void wr(i64 x)
{
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) wr(x / 10);
    putchar((x % 10) ^ '0');
}
const int N = 2000010;

int n, q, k;
i64 a[N], b[N];
i64 tmp[N][3]; // 记录临时变化的，最后换回来

int lc[N], rc[N], rt; // 笛卡尔树
int stk[N], sz; // 单调栈

// 区间 b 加和用前缀和，这里的 ans 就是题解的 f
i64 sum_b[N], ans[N], res; 

void dfs(int l, int r, int u, i64 res)
{
    if (!u || (l > r)) return;
    // a[u] 是情况 1，res 是情况 2
    ans[u] = std::max(a[u], res); 
    if (l == r) return;
    dfs(l, u - 1, lc[u], std::max(res, a[u] - (sum_b[u - 1] - sum_b[l - 1])));
    dfs(u + 1, r, rc[u], std::max(res, a[u] - (sum_b[r] - sum_b[u])));
}
void solve()
{
    k = rd();
    for (int i = 1; i <= k; ++i) tmp[i][0] = rd(), tmp[i][1] = rd(), tmp[i][2] = rd();
    for (int i = 1; i <= k; ++i) std::swap(a[tmp[i][0]], tmp[i][1]), std::swap(b[tmp[i][0]], tmp[i][2]);
    // b 的前缀和
    for (int i = 1; i <= n; ++i) sum_b[i] = sum_b[i - 1] + b[i], ans[i] = 0;
    // 构造笛卡尔树
    int cur = 0;
    for (int i = 1; i <= n; ++i)
    {
        cur = sz;
        while (cur && a[stk[cur]] < a[i]) --cur;
        if (cur) rc[stk[cur]] = i;
        if (cur < sz) lc[i] = stk[cur + 1];
        stk[sz = ++cur] = i;
    }
    rt = stk[1], res = 0;
    
    dfs(1, n, rt, 0);
    for (int i = 1; i < n; ++i) res ^= std::min(ans[i], ans[i + 1]);
    wr(res), putchar('\n');
}
// 多测清空
void clr()
{
    for (int i = 1; i <= k; ++i) std::swap(a[tmp[i][0]], tmp[i][1]), std::swap(b[tmp[i][0]], tmp[i][2]);
    rt = sz = 0;
    memset(lc, 0, (n + 1) << 2), memset(rc, 0, (n + 1) << 2);
}
int main()
{
    n = rd();
    for (int i = 1; i <= n; ++i) a[i] = rd();
    for (int i = 1; i <= n; ++i) b[i] = rd();
    q = rd();
    while (q--) solve(), clr();
}