依旧几天前的 Hootime 肘击现在的 Hootime。
Qoj15442 Cyclic Shift
考虑如何比较两个前缀序列。
注意到前缀序列是由若干个连续段构成的，而它们可以用一棵树表示，即每个点连向最近的严格大于自己的点。
然后哈希，倍增求最长相同前缀，然后比较第一个不同位置即可。
然后平凡地找最大值即可。
#include <bits/stdc++.h>
#define llong long long
#define N 500005
using namespace std;int n;
int a[N], fa[N][21], len[N];
int sta[N], top;unsigned llong val[N][21];
#define mrg(x,y) (x*114514+y*1919810)inline int lesseq(int x, int y){if(val[x][20] == val[y][20]) return 0;for(int i = 20; ~i; --i)if(val[x][i] == val[y][i])x = fa[x][i], y = fa[y][i];return a[x] < a[y] || (a[x] == a[y] && len[x] >= len[y]);
}int _main(){cin >> n;for(int i = 1; i <= n; ++i) cin >> a[i];for(int i = 1, x = 0; i <= n; ++i)if(a[i] > x) x = a[i], sta[++top] = i+n;reverse(sta+1, sta+top+1);for(int i = n; i >= 1; --i){while(top && a[i] >= a[(sta[top]-1)%n+1]) --top;if(!top) len[i] = 1e9+7;else fa[i][0] = (sta[top]-1)%n+1, len[i] = sta[top]-i;sta[++top] = i;}for(int i = 1; i <= n; ++i)val[i][0] = a[i]*1926+len[i];for(int t = 1; t <= 20; ++t)for(int i = 1; i <= n; ++i)fa[i][t] = fa[fa[i][t-1]][t-1], val[i][t] = mrg(val[i][t-1], val[fa[i][t-1]][t-1]);int res = 1;for(int i = 2; i <= n; ++i)if(lesseq(i, res)) res = i;for(int i = 1, cur = 0; i <= n; ++i)cout << (cur = max(cur, a[(res+i-2)%n+1])) << " ";cout << "\n";return 0;
}
void _init(){for(int i = 1; i <= n; ++i)for(int j = 0; j <= 20; ++j)fa[i][j] = val[i][j] = 0;top = 0;
}int T;
int main(){ios::sync_with_stdio(false);cin >> T;while(T--) _init(), _main();return 0;
}Qoj15440 DFS Order - Extra Stage
个人认为这题最难点是看出它是一个 DP 而不是某种神秘构造。
发现第一个 DFS 序中的一个区间 \([i, j]\) 能构成一个完整子树，当且仅当它的所有元素在其它所有 DFS 序中是连续的，且 \(a_i\) 都是相对最前。取出第一个 DFS 序中的一个区间 \([i, j]\)，定义其能构成的完整子树有 \(dp_{i,j}\) 种。
然后直接做了。
#include <bits/stdc++.h>
#define llong long long
#define N 505
using namespace std;constexpr llong p = 1e9+7;int n, m;
int a[N][N], pos[N][N];
int head[N], vis[N][N], cnt[N];
llong f[N][N], g[N][N];struct Int{int l, r;};
Int b[N*N]; int c;
#define len(x) (x.r-x.l+1)int main(){ios::sync_with_stdio(false);cin >> n >> m;if(n == 1){cout << 1;return 0;}for(int i = 1; i <= m; ++i)for(int j = 1; j <= n; ++j)cin >> a[i][j], pos[i][a[i][j]] = j;// Get all valid intervals. This is an unusual way to implement.for(int l = 1; l <= n; ++l){for(int i = 2; i <= m; ++i){head[i] = cnt[i] = 0;for(int j = 1; j <= n; ++j) vis[i][j] = 0;}for(int r = l; r <= n; ++r){bool valid = true;for(int i = 2; i <= m; ++i){int ptr = pos[i][a[1][r]];vis[i][ptr] = true;if(!vis[i][ptr-1]) head[i] ^= ptr;if( vis[i][ptr+1]) head[i] ^= ptr+1;if(!vis[i][ptr-1] && !vis[i][ptr+1]) ++cnt[i];if( vis[i][ptr-1] && vis[i][ptr+1]) --cnt[i];if(cnt[i] != 1 || head[i] != pos[i][a[1][l]]) valid = false;}if(valid && l != r) b[++c] = {l, r};}}// DP.sort(b+1, b+c+1, [](Int o1, Int o2){return o1.r-o1.l < o2.r-o2.l;});for(int i = 1; i <= n; ++i) f[i][i] = g[i][i] = 1;for(int len = 2, ptr = 1; len <= n; ++len){while(len(b[ptr]) == len){int l = b[ptr].l, r = b[ptr].r;f[l][r] = g[l+1][r];++ptr;}for(int l = 1; l <= n-len+1; ++l){int r = l+len-1;g[l][r] = f[l][r];for(int mid = l; mid < r; ++mid)(g[l][r] += f[l][mid]*g[mid+1][r]) %= p;}}cout << f[1][n];return 0;
}[Unknown Source] 共轭树图
给定一个有根树 \(T\)，根为 \(n\)，保证节点 \(i\) 的父亲 \(f_i > i\)。另外有一张具有 \(n\) 个点的图 \(G\)，初始 \(G\) 没有任何边。
你可以执行以下操作 \(n-1\) 次，每次你可以删除一条边 \((u, v)\)，并将 \(G\) 中 $u, 所在的连通块中编号最大的点 \(m_u, m_v\)，并在 \(G\) 中连边。
求能构造出的不同形态的 \(G\) 的数量。\(n \le 3 \times 10^3\)。
发现 \(G\) 的形态不同，当且仅当其有至少一条边不同。考虑点 \(i\) 连向祖先方向的边可以连向多少个元素。发现这是和其父亲的深度有关的，于是自然考虑 dp。
朴素 \(n^2\) dp 即可。
#include <bits/stdc++.h>
#define llong long long
#define N 3003
using namespace std;constexpr llong p = 998244353;int n;
vector<int> G[N];llong dp[N][N];
inline void dfs(int u){dp[u][1] = (u==n);for(int i = 2; i <= n; ++i) dp[u][i] = 1;for(int v : G[u]){dfs(v);for(int i = 2; i <= n; ++i)(dp[u][i-1] *= dp[v][i]) %= p;}for(int i = 2; i <= n; ++i)(dp[u][i] += dp[u][i-1]) %= p;return;
}int main(){freopen("reflection.in", "r", stdin);freopen("reflection.out", "w", stdout);ios::sync_with_stdio(false);cin >> n;for(int i = 1; i < n; ++i){int u, v; cin >> u >> v;if(u < v) swap(u, v);G[u].push_back(v);}dfs(n);cout << dp[n][1];return 0;
}[Unknown Source] 摆烂合唱
给定一个包含 \(\text{and}, \text{or}, \text{xor}\) 的带有 \(n\) 个布尔变量的表达式。每次指定一个变量 \(x_i\)，将其余变量等概率随机取值，求 \(x_i = 0\) 时表达式的值和 \(x_i = 1\) 时表达式的值不同的概率。
\(n \le 10^5\)
首先建出表达式树。考虑一个节点子树结果为 \(0/1\) 的概率，可以算出一个节点的变量被“短路”的概率。
然后树上前缀积即可。复杂度线性。
#include <bits/stdc++.h>
#define llong long long
#define N 200005
using namespace std;constexpr llong p = 998244353;
constexpr llong inv2 = (p+1)/2;int n;
int ls[N], rs[N], fa[N], op[N], tsiz, xcnt, root;
#define get(x) (x==son[fa[x]][0] ? 0 : 1)// 1: and, 2: or, 3: xorllong cnt[N][2], val[N];inline int input(){int x = ++tsiz; ls[x] = (getchar()=='x' ? ++xcnt : input());char ch = getchar();op[x] = (ch=='&' ? 1 : (ch=='|' ? 2 : 3));rs[x] = (getchar()=='x' ? ++xcnt : input());return getchar(), x;
}
inline void dfs1(int x){if(x <= n){cnt[x][0] = cnt[x][1] = inv2;return;}dfs1(ls[x]), dfs1(rs[x]);if(op[x] == 1){cnt[x][0] = cnt[ls[x]][0]*cnt[rs[x]][0]+cnt[ls[x]][0]*cnt[rs[x]][1]+cnt[ls[x]][1]*cnt[rs[x]][0];cnt[x][1] = cnt[ls[x]][1]*cnt[rs[x]][1];}else if(op[x] == 2){cnt[x][0] = cnt[ls[x]][0]*cnt[rs[x]][0];cnt[x][1] = cnt[ls[x]][1]*cnt[rs[x]][1]+cnt[ls[x]][0]*cnt[rs[x]][1]+cnt[ls[x]][1]*cnt[rs[x]][0];}else{cnt[x][0] = cnt[ls[x]][0]*cnt[rs[x]][0]+cnt[ls[x]][1]*cnt[rs[x]][1];cnt[x][1] = cnt[ls[x]][0]*cnt[rs[x]][1]+cnt[ls[x]][1]*cnt[rs[x]][0];}cnt[x][0] %= p, cnt[x][1] %= p;return;
}
inline void dfs2(int x){if(x <= n) return;if(op[x] == 1){val[ls[x]] = val[x]*cnt[rs[x]][1]%p;val[rs[x]] = val[x]*cnt[ls[x]][1]%p;}else if(op[x] == 2){val[ls[x]] = val[x]*cnt[rs[x]][0]%p;val[rs[x]] = val[x]*cnt[ls[x]][0]%p;}elseval[ls[x]] = val[rs[x]] = val[x];dfs2(ls[x]), dfs2(rs[x]);return;
}int main(){freopen("binary.in", "r", stdin);freopen("binary.out", "w", stdout);scanf("%d ", &n);if(n == 1){puts("1");return 0;}tsiz = n, getchar();val[root = input()] = 1;dfs1(root), dfs2(root);for(int i = 1; i <= n; ++i)printf("%lld\n", val[i]);return 0;
}[Unknown Source] 对称旅行者
给定一个长度为 \(n\) 的排列 \(a\)。
一轮冒泡排序定义为：顺次考虑 \(i \in [1, n)\)，如果 \(a_i > a_{i+1}\)，则 \(a_i \gets a_{i+1}, a_{i+1} \gets a_i\)。有 \(q\) 次询问，每次询问第 \(k\) 次冒泡排序后，元素 \(x\) 的位置。
\(n, q \le 5 \times 10^5\)
定义 \(m_x = \sum_{i = 1}^{x-1} [a_i > a_x]\)。
注意到，冒泡排序一轮，对于每个 \(i\)，\(m_i\) 就减少 \(1\)，并且 \(m\) 小于 \(0\) 的顺序排列。
然后用你喜欢的数据结构维护即可。
#include <bits/stdc++.h>
#define llong long long
#define N 500005
using namespace std;int n, q;
int a[N], b[N], pos[N];
struct Query{int k, x, id;};
Query qry[N];
int id[N], ans[N];template<int siz>
class FenwickTree{int fwk[1<<siz];#define lowbit(x) (x&-x)public:inline void set(int x){while(x < (1<<siz)) fwk[x] += 1, x += lowbit(x);}inline void unset(int x){while(x < (1<<siz)) fwk[x] -= 1, x += lowbit(x);}inline int getkth(int k){int x = 0; for(int i = siz-1; ~i; --i) if(k>fwk[x|(1<<i)]) k-=fwk[x|(1<<i)], x|=1<<i; return x+1;}inline int presum(int x){int res = 0; while(x) res += fwk[x], x ^= lowbit(x); return res;}
};FenwickTree<19> fwk, fwkv;
FenwickTree<20> fwkp;int main(){ios::sync_with_stdio(false);cin >> n;for(int i = 1; i <= n; ++i) cin >> a[i], pos[a[i]] = i;for(int i = 1; i <= n; ++i)fwk.set(a[i]), b[i] = i-fwk.presum(a[i]);for(int i = 1; i <= n; ++i) id[i] = i;sort(id+1, id+n+1, [&](int o1, int o2){return b[o1]<b[o2];});cin >> q;for(int i = 1; i <= q; ++i)cin >> qry[i].k >> qry[i].x, qry[i].id = i;sort(qry+1, qry+q+1, [](Query o1, Query o2){return o1.k<o2.k;});for(int i = 1, j = 1, k = 1; i <= qry[q].k; ++i){while(j <= n && b[id[j]] < i) fwkv.set(a[id[j]]), fwkp.set(id[j]), ++j;fwkp.unset(i), fwkp.set(i+n);while(k <= q && qry[k].k == i){int x = pos[qry[k].x];if(b[x] >= i) ans[qry[k].id] = x-i;else ans[qry[k].id] = fwkp.getkth(fwkv.presum(qry[k].x))-i;++k;}}for(int i = 1; i <= q; ++i) cout << ans[i] << "\n";return 0;
}
[Unknown Source] 神奇园艺师
给定一个 \(n\) 个数的集合 \(S\)。你可以进行若干次操作，每次操作你可以把一个元素乘或者除某个质数 \(p\)。一个集合的代价即为将所有数变成相同的，所需要的最小操作次数。求集合 \(S\) 的所有子集的代价和。
一看就是拆贡献题。注意到每个质数的贡献是独立的，以下我们固定质数 \(p\)。
考虑一个子集的贡献。假设 \(k^{x_i} | S_i\)，那么其贡献为 \(\sum_{now \in S} |x_i-x_e|\)，其中 \(x_e\) 为中位数的贡献。注意到 \(+x_e\) 和 \(-x_e\) 的数量是相同的因此我们可以不管 \(x_e\)，那么 \(i\) 在单个集合的贡献就是（假设 \(x\) 已经降序排序）：
\[v_i = \begin{cases}
x_i & i > e \\
0 & i = e \\
-x_i & i < e \\
\end{cases}
\]
\(i\) 和 \(e\) 的关系与大于 \(i\) 的元素数量和小于 \(i\) 的元素数量有关，分别设其为 \(a, b\)，那么上式可以改写为：
\[v_i = \begin{cases}
x_i & a < b \\
0 & a = b \\
-x_i & a > b \\
\end{cases}
\]
ps. 我最开始以为 \(|S|\) 为偶数时这个不成立，但是对于 \(|S|\) 为偶数的情况，下中位数可以选择视为 \(|x_e-x_e|\)，所以没有问题
然后对于元素 \(i\)，其贡献为：
\[\begin{aligned}
v_i
&= \sum_{a<b} {i-1 \choose a} {n-i \choose b} x_i - \sum_{a>b} {i-1 \choose a} {n-i \choose b} x_i\\
&= x_i\left( \sum_{a<b} {i-1 \choose a} {n-i \choose b} - \sum_{a>b} {i-1 \choose a} {n-i \choose b} \right)\\
\end{aligned}
\]
然后这题变成了组合推式子题（其实现在已经有 50pts 了）。我们先推左半。
\[\begin{aligned}
&\sum_{a<b} {i-1 \choose a} {n-i \choose b}\\
=\ & \sum_{a=0}^{i-1} \sum_{b=a+1}^{n-i} {i-1 \choose a} {n-i \choose b} \\
=\ & \sum_{a=0}^{i-1} \sum_{d=1}^{n-i-a} {i-1 \choose a} {n-i \choose a+d} \\
=\ & \sum_{d = 1}^{n-i} \sum_{a=0}^{\min \{ i-1, n-i-d \}} {i-1 \choose a} {n-i \choose a+d} \\
=\ & \sum_{d = 1}^{n-i} {n-1 \choose n-i-d} \\
=\ & \sum_{k = 0}^{n-i-1} {n-1 \choose k}
\end{aligned}
\]
同理，右半可以化为 \(\sum_{k = 0}^{i-2} {n-1 \choose k}\)。
那么，我们预处理 \({n-1 \choose k}\) 即可。
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define llong long long
#define N 1000006
using namespace std;
using namespace __gnu_pbds;constexpr llong p = 1e9+7;
llong fac[N], inv[N];
inline llong iv(llong a){llong b = p-2, res = 1;while(b){if(b & 1) res = res*a%p;a = a*a%p, b >>= 1;}return res;
}
inline llong C(int n, int m){return fac[n]*inv[m]%p*inv[n-m]%p;
}int prime[N], vis[N], pcnt;
inline void sieve(){for(int i = 2; i < N; ++i){if(!vis[i]) vis[i] = prime[++pcnt] = i;for(int j = 1; j <= pcnt && i*prime[j] < N; ++j){vis[i*prime[j]] = prime[j];if(i % prime[j] == 0) break;}}return;
}int n;
int a[N]; llong pres[N];
vector<int> ark[N];llong ans;int main(){ios::sync_with_stdio(false);cin >> n;// Initalizesieve();fac[0] = 1;for(int i = 1; i <= n; ++i) fac[i] = fac[i-1]*i%p;inv[n] = iv(fac[n]);for(int i = n; i >= 1; --i) inv[i-1] = inv[i]*i%p;// Parsefor(int i = 1; i <= n; ++i){cin >> a[i];int tmp = a[i];while(tmp != 1){int x = vis[tmp], cnt = 0;while(vis[tmp] == x) tmp /= x, ++cnt;ark[x].push_back(cnt);}}// Solvepres[0] = 1;for(int i = 1; i < n; ++i) (pres[i] = pres[i-1]+C(n-1,i)) %= p;#define getpres(x) (x>=0 ? pres[x] : 0)for(int kc = 1; kc <= pcnt; ++kc){int k = prime[kc];vector<int>& tmp = ark[k];sort(tmp.begin(), tmp.end(), greater<int>());int len = tmp.size();for(int i = 1; i <= len; ++i)ans = ((ans+(getpres(n-i-1)-getpres(i-2))*tmp[i-1])%p+p)%p;}cout << ans;return 0;
}Qoj14716 K-Coverage
考虑维护单个位置减一带来的贡献 \(\Delta_1\) 和加一带来的贡献 \(\Delta_2\)。接下来只考虑新区间在原区间右边的情况，在左边的话对称。即，考虑原区间 \([x, x+L-1]\)，新区间 \([y, y+L-1]\)。
如果两区间不交，那么贡献为 \(\sum_{i=x}^{x+L-1} \Delta_{1,i} + \sum_{i=y}^{y+L-1} \Delta_{2,i}\)。注意到只需要维护 \(\sum_{i=y}^{y+L-1} \Delta_{2,i}\) 的后缀 max。
如果两区间交，那么贡献为 \(\sum_{i=x}^{y} \Delta_{1,i} + \sum_{i=x+L-1}^{y+L-1} \Delta_{2,i} = \sum_{i=x}^{y} \Delta_{1,i} + \Delta_{2,i+L} = (\sum_{i=1}^{y} \Delta_{1,i} + \Delta_{2,i+L})-(\sum_{i=1}^{x-1} \Delta_{1,i} + \Delta_{2,i+L})\)。发现单调队列求 \((\sum_{i=1}^{y} \Delta_{1,i} + \Delta_{2,i+L})\) 最大值即可。
然后做完了。
#include <bits/stdc++.h>
#define llong long long
#define N 1000006
using namespace std;int n, m, l, k, sum, ans;
int a[N], b[N], d1[N], d2[N], v1[N], v2[N], pd1[N], pd2[N];
int pmax[N], smax[N];int que[N], he = 1, ta = 0;int _main(){ios::sync_with_stdio(false);cin >> n >> l >> k, m = (n+1)*4;for(int i = 1; i <= n; ++i)cin >> a[i], ++a[i], ++b[a[i]], --b[a[i]+l];a[0] = -l+1, a[n+1] = m+1;// Initalizesort(a+1, a+n+1);for(int i = 1; i <= m; ++i){b[i] += b[i-1], sum += (b[i]==k);pd1[i] = pd1[i-1]+(d1[i]=(b[i]==k+1)-(b[i]==k));pd2[i] = pd2[i-1]+(d2[i]=(b[i]==k-1)-(b[i]==k));}for(int i = 1; i <= m-l; ++i) v1[i] = v1[i-1]+(d1[i]+d2[i+l]);for(int i = m; i >= l+1; --i) v2[i] = v2[i+1]+(d1[i]+d2[i-l]);pmax[0] = smax[m+1] = -1e9-7;for(int i = 1; i <= m-l+1; ++i) pmax[i] = max(pmax[i-1], pd2[i+l-1]-pd2[i-1]);for(int i = m-l+1; i >= 1; --i) smax[i] = max(smax[i+1], pd2[i+l-1]-pd2[i-1]);// Solvefor(int i = 1; i <= n; ++i)ans = max(ans, pd1[a[i]+l-1]-pd1[a[i]-1]+max((a[i]>l?pmax[a[i]-l]:0), smax[a[i]+l]));he = 1, ta = 0;for(int i = 1; i <= n; ++i){for(int j = a[i-1]+l; j <= min(a[i]+l-1, m-l); ++j){while(he <= ta && v1[j] >= v1[que[ta]]) --ta;que[++ta] = j;}while(he <= ta && que[he] < a[i]) ++he;if(he <= ta) ans = max(ans, v1[que[he]]-v1[a[i]-1]);}he = 1, ta = 0;for(int i = n; i >= 1; --i){for(int j = a[i+1]-1; j >= max(a[i], l+1); --j){while(he <= ta && v2[j] >= v2[que[ta]]) --ta;que[++ta] = j;}while(he <= ta && que[he] > a[i]+l-1) ++he;if(he <= ta) ans = max(ans, v2[que[he]]-v2[a[i]+l]);}cout << sum+ans << "\n";return 0;
}
void _init(){for(int i = 0; i <= m+1; ++i)b[i] = v1[i] = v2[i] = d1[i] = d2[i] = pd1[i] = pd2[i] = pmax[i] = smax[i] = 0;sum = ans = 0;
}int T;
int main(){ios::sync_with_stdio(false);cin >> T;while(T--) _init(), _main();return 0;
}Qoj14810 Trajan Algorithm
太 TM 简单了，不想写了。
#include <bits/stdc++.h>
#define llong long long
#define N 1000006
using namespace std;int n, m;
vector<pair<int,int>> G[N];
int dfn[N], low[N], vis[N], dfcnt;
vector<int> s1, s2;
int cut[N];inline void tarjan(int u){dfn[u] = low[u] = ++dfcnt;int cucnt = 0;for(auto now : G[u]){int v = now.first, id = now.second;if(vis[id]) continue;vis[id] = true;if(!dfn[v]){tarjan(v);low[u] = min(low[u], low[v]);if(low[v] >= dfn[u]) ++cucnt;if(low[v] > dfn[u]) s2.push_back(u), s2.push_back(v);}else low[u] = min(low[u], dfn[v]);}if(cucnt-(u==1) >= 1) s1.push_back(u);return;
}int _main(){ios::sync_with_stdio(false);cin >> n >> m;for(int i = 1; i <= m; ++i){int u, v; cin >> u >> v;G[u].emplace_back(v, i);G[v].emplace_back(u, i);}tarjan(1);for(int now : s1) cut[now] = true;for(int now : s2) cut[now] = false;int flag = false;for(int i = 1; i <= n; ++i)if(cut[i]) flag = true, cout << i << " ";if(!flag) cout << "Empty";cout << "\n";return 0;
}
void _init(){for(int i = 1; i <= n; ++i) dfn[i] = low[i] = cut[i] = 0, G[i].clear();for(int i = 1; i <= m; ++i) vis[i] = 0;dfcnt = 0, s1.clear(), s2.clear();return;
}int T;
int main(){ios::sync_with_stdio(false);cin >> T;while(T--) _init(), _main();return 0;
}[Unknown Source] 阈值子序列
给定两个长度为 \(n\) 的序列 \(a, b\)。找出一个长度为 \(k\) 的序列 \(p_1, p_2, \cdots, p_k\)，使得 \(\forall i \in [1, k), p_i < p_i+1 \land b_ia_{p_i} < a_{p_{i+1}}\)。求 \(p\) 的最大值。\(1 \le n \le 10^5\)
依旧太简单了，不想写。
#include <bits/stdc++.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>
#define llong long long
#define N 1000006
#define W 1000000000000ll
using namespace std;namespace IO{char *buf1;#define gc() (*buf1++)struct F{F(){struct stat st;fstat(0, &st);buf1=(char *)mmap(NULL,st.st_size,PROT_READ,MAP_PRIVATE,0,0);}} f;template<typename T>__always_inline void read(T& x){x = 0; char ch = gc();while(ch < '0' || ch > '9') ch = gc();while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();}
}
using IO::read;int n;
llong a[N], b[N];
int dp[N];struct Int{llong l; mutable int val;Int(llong o1, int o3): l(o1), val(o3){}bool operator<(const Int& o)const{return l < o.l;}
};
set<Int> odt;
inline void assign(llong pos, int k){if(pos > W) return;auto it1 = prev(odt.upper_bound({pos, 0}));if(it1->val >= k) return;auto it2 = next(it1);while(it2 != odt.end() && it2->val <= k) ++it2;llong L = it1->l;odt.erase(next(it1), it2);if(L == pos) it1->val = k;else odt.emplace(pos, k);return;
}
inline int getval(llong pos){return prev(odt.upper_bound({pos, 0}))->val;
}int main(){read(n);for(int i = 1; i <= n; ++i) read(a[i]);for(int i = 1; i <= n; ++i) read(b[i]);odt.emplace(1, 1), odt.emplace(W+1, (int)1e9+7);int ans = 0;for(int i = 1; i <= n; ++i){dp[i] = getval(a[i]), ans = max(ans, dp[i]);assign(a[i]*b[dp[i]]+1, dp[i]+1);}cout << ans;return 0;
}