A
考虑之前选中没有一个的，那么结果就是(min(n-s,n-t))
那么能选中的第一次就是这个结果(+1)，但需要拥有两个
((s>t))考虑一开始选不中(t)，则但选中(t)时(s)也一定被选中了(()最坏的情况为(s)与(t)并集最小())
(ans=n-min(s,t)+1)
B
-
简单想的复杂度高的算法：先(sum_{i,j})表示文本串前(i)个字符(j)字符的个数
匹配串也用(a)统计每个字符的个数，二分一下判是否满足(O(26n+sum t_i+mlogn)) -
复杂度下界
开个桶(a_{i,j})表示文本串(i)字符第(j)个的位置
匹配串统计每个字符的个数，再在(a)里比较一下最大值(O(n+26m))
C
题意：需要构造一个数组，有(m)个约束((t,l,r))
(t=1,a_{l,r})非严格递增；(t=0,a_{l,r})，至少有一对连续的位置(a_{i}>a_{i+1})
思考怎么则不合理：唯一的情况为至少有一组(t=0)包含在(t=1)中
将(t=1)当做限制，(t=0)当做判断
一开始将数组严格递减构造，显然这样满足所有的(t=0)；将(t=1)记录下来，按左区间的位置升序排序；
每次对于((t=1,l,r))将([l,r])的值赋为(a_{l})
D
想到平衡树的做法不记得用(STL)结果打崩了
考虑前(i-1)已经匹配了，(a_i≠b_i)，那么怎么移过来呢？假设远处有一个位置(x)，满足(a_x=b_i)
能移动过来的条件为(min[i,x]=b_i)
平衡树则需要支持：区间最小值查询，单点查询，单点删除与添加，直接打崩
考虑用(set+)线段树实现：我们发现单点往前移有一个特点，移过的点都不会用到了
把((a_i,i))放到(set)里，线段树维护区间最小值查询，我们需要使得线段树仅维护单点修改就能实现之前的状态
每次用(set)找出第一个符合大于等于的：
-
就相当于如果(set)里还有第一个关键字为(b_i)，找到第二个关键字(()原数组位置(x))最小的
找到后将(x)在线段树值为(inf)，并在(set)里删去(()因为(i)这个点之后没有用了())，也就是相对位置不变 -
如果没有就失败
(rank2's code)
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int maxN = 3 * (int)1e5 + 100;
int b[maxN];
int t[4 * maxN];
int a[maxN];
void build(int v, int tl, int tr) {
if (tl == tr) {
t[v] = a[tl];
return;
}
int tm = (tl + tr) / 2;
build(v + v, tl, tm);
build(v + v + 1, tm + 1, tr);
t[v] = min(t[v + v], t[v + v + 1]);
}
void upd(int v, int tl, int tr, int pos, int val) {
if (tl == tr) {
t[v] = val;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm) upd(v + v, tl, tm, pos, val);
else upd(v + v + 1, tm + 1, tr, pos, val);
t[v] = min(t[v + v], t[v + v + 1]);
}
const int INF = (int)1e9 + 100;
int get(int v, int tl, int tr, int l, int r) {
if (l > r) return INF;
if (tl == l && tr == r) {
return t[v];
}
int tm = (tl + tr) / 2;
return min(get(v + v, tl, tm, l, min(r, tm)), get(v + v + 1, tm + 1, tr, max(l, tm + 1), r));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("input.txt", "r", stdin);
int q;
cin >> q;
while (q--) {
int n;
cin >> n;
set < pair < int, int > > s;
for (int i = 1; i <= n; i++) {
cin >> a[i];
s.insert(make_pair(a[i], i));
}
bool ok = true;
build(1, 1, n);
for (int i = 1; i <= n; i++) {
cin >> b[i];
if (!ok) continue;
auto it = s.lower_bound(make_pair(b[i], -1));
if (it == s.end() || ((it -> first) != b[i])) {
ok = false;
continue;
}
int ind = (it -> second);
s.erase(it);
if (b[i] != get(1, 1, n, 1, ind)) {
ok = false;
}
upd(1, 1, n, ind, INF);
}
if (ok) cout << "YES" << '
';
else cout << "NO" << '
';
}
return 0;
}
E
很裸的换根
考虑(1)作为点，(ans=sum size_i)，只需要考虑从(u)移到(v)u和(v)的子树大小变化就好了