太弱小了, 没有力量.
蒋叶桢打疫苗去了, 我吃饭迟到了一会, 期间张炀杰疯狂开题. 到后我给张炀杰重新翻译了D签到题, 然后看到了另一个签到B, 分别 21min A, 28min 1A. 然后一起想了F, 数位dp假半天发现鸽子原理搞搞只需要处理很小的部分, 张炀杰上机, 48min A. 蒋叶桢来后看了H, 发现是个FFT板题, 但是期间出了一点小问题; 开了A博弈和I dp, dp没仔细想先去和张炀杰推博弈了. 蒋叶桢H 2h17min A, 之后全员博弈. 发现并不会做, 然后蒋叶桢暴力跑了小范围数据想找规律, 最后看到数据量较小, 决定打表. 5min后表跑完了, 3h21min A. 全员不会期望dp, 写了个方程发现倒序枚举好像是对的. 最后各种优化都没搞出来.
- 学习期望dp
好像就没啥了…
A.Alice and Bob
两堆石子, 个数为$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 以内)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
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)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
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)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
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$次询问,
- 区间 $[l, r]$, 问从车站 $l$ 到车站 $r$, 是否都能够成功停靠
- 修改一个车站的开放时段
- 修改从一个车站出发到下一个车站的用时.
$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)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
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;
}
|