You are given an array \(a_1\),\(a_2\),…,\(a_n\) and an array \(b_1\),\(b_2\),…,\(b_n\).
For one operation you can sort in non-decreasing order any subarray \(a[l…r]\) of the array \(a\).
For example, if \(a=[4,2,2,1,3,1]\) and you choose subbarray \(a[2…5]\), then the array turns into \([4,1,2,2,3,1]\).
You are asked to determine whether it is possible to obtain the array b by applying this operation any number of times (possibly zero) to the array \(a\).
The first line contains one integer \(t (1≤t≤3?10^5)\) — the number of queries.
The first line of each query contains one integer \(n (1≤n≤3?105)\).
The second line of each query contains \(n\) integers \(a_1,a_2,…,a_n (1≤a_i≤n)\).
The third line of each query contains n integers \(b_1,b_2,…,b_n (1≤b_i≤n)\).
It is guaranteed that \(\sum{n}≤3?10^5\) over all queries in a test.
For each query print YES (in any letter case) if it is possible to obtain an array b and NO (in any letter case) otherwise.
4
7
1 7 1 4 4 5 6
1 1 4 4 5 7 6
5
1 1 3 3 5
1 1 3 3 5
2
1 1
1 2
3
1 2 3
3 2 1
YES
YES
NO
NO
In first test case the can sort subarray \(a_1…a_5\), then a will turn into \([1,1,4,4,7,5,6]\), and then sort subarray \(a_5…a_6\).
这题也过分,一定要发朋友圈博客。
OI带到这里的“坏”习惯——及时break。ACM里遍地都是多组数据,判断出一组答案,及时break之后,这一组还没读完读数据就被下一组读了,自然WA了。
这题调了一上午的原因就在于此——经验不足,以至于完全看不出我的代码及时break的问题。
另外,这是我的第一篇用markdown写的博客,markdown真好用。
支持的操作是对子区间升序排序,这意味着,我们可以把一个区间内的最大值移动到该区间最右端,也可以把一个区间内的最小值移动到该区间最左端。
由于b是从左到右输入,对于每一个b,a也要将合适的数字左移,所以我们使用第二条,移动区间最小值到最左端。其实想一想不一定总是要到最左端,一个区间内的最小值可以左移到任意位置,还不会影响其他数字的顺序(每次排序最小值和最小值左边的第一个数,总共两个数)。
首先读入a数组,经过一堆后面会说的预处理(为了快速找到下文说的pos[b]),然后依次读入b。
对于每一个读入的b(假设是第i个),寻找这个数字b在a中最早出现的位置(pos[b])。
然后完善一些小地方,区间最小值连上更新,就用线段树,挺方便。快速找pos[b],思路类似莫队里经常出现的pos数组和nxt数组。另外,memset不要每组数组都全部清零,第18个测试点很变态(见代码59行)。
SDOI2009 HH的项链
#include <stdio.h>
#include <string.h>
#include <algorithm>
int T;
int n;
int a[300010], nxt[300010], pos[300010];
struct Segtree
{
int l, r;
int min;
} s[1200010];
inline int lson(int x) { return x << 1; }
inline int rson(int x) { return x << 1 | 1; }
inline void pushup(int x) { s[x].min = std::min(s[lson(x)].min, s[rson(x)].min); }
void build(int x, int l, int r)
{
s[x] = {l, r, 0};
if (l == r)
{
s[x].min = a[l];
return;
}
int mid = l + r >> 1;
build(lson(x), l, mid);
build(rson(x), mid + 1, r);
pushup(x);
}
void update(int x, int position)
{
if (position > s[x].r || position < s[x].l)
return;
if (s[x].l == s[x].r && s[x].l == position)
{
s[x].min = 0x7fffffff;
return;
}
update(lson(x), position);
update(rson(x), position);
pushup(x);
}
int que(int x, int l, int r)
{
if (r < s[x].l || l > s[x].r)
return 0x7fffffff;
if (l <= s[x].l && s[x].r <= r)
return s[x].min;
return std::min(que(lson(x), l, r), que(rson(x), l, r));
}
int main()
{
//freopen("test.in","r",stdin);
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", a + i);
memset(nxt, 0x7f, sizeof(int)*(n+2));//第18个测试点十分丧病,T是几十万,每组n是1
memset(pos, 0x7f, sizeof(int)*(n+2));
for (int i = n; i >= 1; i--)
{
nxt[i] = pos[a[i]];
pos[a[i]] = i;
}
build(1, 1, n);
bool ok = 1;
for (int i = 1, b; i <= n; i++)
{
scanf("%d", &b);
if(!ok) continue;//不要break,数据要读完
if (pos[b] == 0x7f7f7f7f)
ok = 0;
if (que(1, 1, pos[b]) == b)
{
update(1, pos[b]);
pos[b] = nxt[b];
}
else
ok = 0;
}
puts(ok ? "YES" : "NO");
}
return 0;
}
CodeForces 1187D Subarray Sorting
原文:https://www.cnblogs.com/wawcac-blog/p/11229396.html