USER
QED is given a permutation∗
p
of length n
. He also has a string s
of length n
containing only characters L
and R
. QED only likes permutations that are sorted in non-decreasing order. To sort p
, he can select any of the following operations and perform them any number of times:
Choose an index i
such that si=L
. Then, swap pi
and pi−1
. It is guaranteed that s1≠L
.
Choose an index i
such that si=R
. Then, swap pi
and pi+1
. It is guaranteed that sn≠R
.
He is also given q
queries. In each query, he selects an index i
and changes si
from L
to R
(or from R
to L
). Note that the changes are persistent.
After each query, he asks you if it is possible to sort p
in non-decreasing order by performing the aforementioned operations any number of times. Note that before answering each query, the permutation p
is reset to its original form.
∗
A permutation of length n
is an array consisting of n
distinct integers from 1
to n
in arbitrary order. For example, [2,3,1,5,4]
is a permutation, but [1,2,2]
is not a permutation (2
appears twice in the array), and [1,3,4]
is also not a permutation (n=3
but there is 4
in the array).
Input
The first line contains t
(1≤t≤104
) — the number of test cases.
The first line of each test case contains two integers n
and q
(3≤n≤2⋅105
, 1≤q≤2⋅105
) – the length of the permutation and the number of queries.
The following line contains n
integers p1,p2,…,pn
(1≤pi≤n
, p
is a permutation).
The following line contains n
characters s1s2…sn
. It is guaranteed that si
is either L
or R
, s1=R
, and sn=L
.
The following q
lines contain an integer i
(2≤i≤n−1
), denoting that si
is changed from L
to R
(or from R
to L
).
It is guaranteed that the sum of n
and q
over all test cases does not exceed 2⋅105
.
Output
For each query, output "YES" (without quotes) if it is possible, and "NO" (without quotes) otherwise.
You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).
Example
InputCopy
3
5 3
1 4 2 5 3
RLRLL
2
4
3
8 5
1 5 2 4 8 3 6 7
RRLLRRRL
4
3
5
3
4
6 2
1 2 3 4 5 6
RLRLRL
4
5
OutputCopy
YES
YES
NO
NO
YES
NO
NO
NO
YES
YES
Note
In the first testcase, s=RRRLL
after the first query. QED may sort p
using the following operations:
Initially, p=[1,4,2,5,3]
.
Select i=2
and swap p2
with p3
. Now, p=[1,2,4,5,3]
.
Select i=5
and swap p5
with p4
. Now, p=[1,2,4,3,5]
.
Select i=4
and swap p4
with p3
. Now, p=[1,2,3,4,5]
, which is in non-decreasing order.
It can be shown that it is impossible to sort the array after all three updates of the first testcase.
type code in c++
ASSISTANT
To solve the problem of determining whether the permutation can be sorted after each query, we need to track the connectivity of indices according to the string `s` that dictates the allowed swaps.
### Step-by-Step Reasoning:
1. **Understanding the Problem:**
- We have a permutation `p` of length `n`.
- The string `s` contains 'L' and 'R' indicating the allowed swap operations.
- We need to determine if, after each query (which toggles a character in `s`), the permutation `p` can be sorted into non-decreasing order by performing the allowed swap operations.
- The key observation is that the connectivity between indices in `p` dictates whether we can rearrange the permutation to be sorted.
2. **Creating Connections Based on `s`:**
- If `s[i] = 'L'`, we can swap `p[i]` with `p[i-1]`.
- If `s[i] = 'R'`, we can swap `p[i]` with `p[i+1]`.
- By toggling the characters in `s`, we can dynamically modify the connectivity between elements in the permutation.
3. **Maintaining Validity:**
- For the permutation to be sorted, every element `p[i]` must be able to reach its correct position `i`.
- This translates to ensuring that in the connected components defined by `s`, each unique element in the connected component matches the indices.
4. **Implementation Strategy:**
- Use a set to keep track of boundaries between connected components.
- Every time `s` is toggled, update the boundaries and check if the connected components can still form valid segments needed for sorting.
- Use prefix sums to efficiently calculate sums and validate if the segments are correct.
5. **Handling Queries:**
- After each toggle, check the validity of the connected components.
- If all connected components are valid, output "YES"; otherwise, "NO".
### Final Implementation:
The following C++ code implements the above strategy efficiently, ensuring that each query is handled in optimal time.
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct TestCase {
int n, q;
vector<int> p;
string s;
vector<ll> prefix_p;
vector<ll> prefix_p2;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
TestCase tc;
cin >> tc.n >> tc.q;
tc.p.resize(tc.n +1);
for(int i=1;i<=tc.n;i++) cin >> tc.p[i];
cin >> tc.s;
// Compute prefix sums
tc.prefix_p.assign(tc.n +2, 0LL);
tc.prefix_p2.assign(tc.n +2, 0LL);
for(int i=1;i<=tc.n;i++){
tc.prefix_p[i] = tc.prefix_p[i-1] + tc.p[i];
tc.prefix_p2[i] = tc.prefix_p2[i-1] + (ll)tc.p[i]*tc.p[i];
}
// Initialize boundaries
set<int> boundaries;
for(int i=1;i<tc.n;i++){
if(!(tc.s[i-1] == 'R' || tc.s[i] == 'L')){
boundaries.insert(i);
}
}
// Initialize interval_starts
set<int> starts;
starts.insert(1);
for(auto it: boundaries){
if(it+1 <= tc.n){
starts.insert(it+1);
}
}
// Function to check validity
auto is_valid = [&](int l, int r) -> bool {
ll sum_i = (ll)r*(r+1)/2 - (ll)(l-1)*l/2;
ll sum_i2 = (ll)r*(r+1)*(2LL*r+1)/6 - (ll)(l-1)*l*(2LL*(l-1)+1)/6;
ll sum_pj = tc.prefix_p[r] - tc.prefix_p[l-1];
ll sum_pj2 = tc.prefix_p2[r] - tc.prefix_p2[l-1];
return (sum_i == sum_pj) && (sum_i2 == sum_pj2);
};
// Initialize invalid_count
int invalid_count = 0;
// Iterate over intervals
auto it = starts.begin();
while(it != starts.end()){
int l = *it;
auto it_next = next(it);
int r;
if(it_next != starts.end()){
r = *it_next -1;
}
else{
r = tc.n;
}
if(!is_valid(l, r)) invalid_count++;
it = it_next;
}
// Process queries
while(tc.q--){
int c;
cin >> c;
// Toggle s[c-1], since string is 0-indexed in C++
char old_char = tc.s[c-1];
char new_char = (tc.s[c-1] == 'L') ? 'R' : 'L';
tc.s[c-1] = new_char;
// Handle edge(i-1, i) where i = c
auto process_boundary = [&](int pos, bool add) {
// pos is the boundary position
if(add){
// Add boundary at pos: split into [a,pos] and [pos+1, b]
// Find the interval containing pos
auto it = starts.upper_bound(pos);
--it;
int l = *it;
// Find r
auto it_next = next(it);
int r;
if(it_next != starts.end()){
r = *it_next -1;
}
else{
r = tc.n;
}
// If already split, do nothing
if(pos < l || pos >= r){
return;
}
// Check validity before split
if(!((ll)r*(r+1)/2 - (ll)(l-1)*l/2 == (tc.prefix_p[r] - tc.prefix_p[l-1])) ||
!((ll)r*(r+1)*(2LL*r+1)/6 - (ll)(l-1)*l*(2LL*(l-1)+1)/6 != (tc.prefix_p2[r] - tc.prefix_p2[l-1]))){
// Do nothing
}
}
};
// Handle edge(c-1, c)
// Determine was_present_before and now_present for edge(c-1, c)
bool was_present = false, now_present = false;
// Before toggle, s[c-1] was old_char
// After toggle, s[c-1] is new_char
// Edge(c-1, c) is present if s[c-2] == 'R' or s[c-1] == 'L'
// Note: c ranges from 2 to n-1, indices in s are 0-based
// Handle edge(c-1, c)
bool edge1_before = false, edge1_after = false;
if(c-1 >=1){
// s[c-2] and s[c-1] are involved
edge1_before = (c-2 >=0 ? (tc.s[c-2] == 'R') : false) || (old_char == 'L');
edge1_after = (c-2 >=0 ? (tc.s[c-2] == 'R') : false) || (new_char == 'L');
if(edge1_before != edge1_after){
if(edge1_before && !edge1_after){
// Add boundary at c-1
// Split interval
// Find interval containing c-1
auto it_split = starts.upper_bound(c-1);
--it_split;
int l = *it_split;
int r;
auto it_next = next(it_split);
if(it_next != starts.end()){
r = *it_next -1;
}
else{
r = tc.n;
}
// Remove [l, r] from invalid_count if invalid
if(!(((ll)r*(r+1)/2 - (ll)(l-1)*l/2) == (tc.prefix_p[r] - tc.prefix_p[l-1])) ||
!(((ll)r*(r+1)*(2LL*r+1)/6 - (ll)(l-1)*l*(2LL*(l-1)+1)/6) == (tc.prefix_p2[r] - tc.prefix_p2[l-1])) ){
invalid_count--;
}
// Insert boundary at c-1
starts.insert(c);
// Now check [l, c-1] and [c, r]
bool valid1 = true, valid2 = true;
if(l <= c-1){
valid1 = (((ll)(c-1)*(c)/2 - (ll)(l-1)*l/2) == (tc.prefix_p[c-1] - tc.prefix_p[l-1])) &&
(((ll)(c-1)*(c)*(2LL*(c-1)+1)/6 - (ll)(l-1)*l*(2LL*(l-1)+1)/6) == (tc.prefix_p2[c-1] - tc.prefix_p2[l-1]));
}
if(!valid1 && l <= c-1){
invalid_count++;
}
if(c <= r){
valid2 = (((ll)r*(r+1)/2 - (ll)(c-1)*c/2) == (tc.prefix_p[r] - tc.prefix_p[c-1])) &&
(((ll)r*(r+1)*(2LL*r+1)/6 - (ll)(c-1)*c*(2LL*(c-1)+1)/6) == (tc.prefix_p2[r] - tc.prefix_p2[c-1]));
}
if(!valid2 && c <= r){
invalid_count++;
}
}
else if(!edge1_before && edge1_after){
// Remove boundary at c-1
// Merge two intervals
// Find [l, c-1] and [c, r]
auto it1 = starts.find(c);
if(it1 == starts.end()) return 0;
int l1 = *it1;
auto it_prev = it1;
--it_prev;
int l2 = *it_prev;
int r2;
auto it_next = next(it1);
if(it_next != starts.end()){
r2 = *it_next -1;
}
else{
r2 = tc.n;
}
// Remove [l1, r2] if invalid
bool was_invalid1 = false, was_invalid2 = false;
if(!(((ll)(c-1)*(c)/2 - (ll)(l2-1)*l2/2) == (tc.prefix_p[c-1] - tc.prefix_p[l2-1])) ||
!(((ll)(c-1)*(c)*(2LL*(c-1)+1)/6 - (ll)(l2-1)*l2*(2LL*(l2-1)+1)/6) == (tc.prefix_p2[c-1] - tc.prefix_p2[l2-1])) ){
was_invalid1 = true;
invalid_count--;
}
if(!(((ll)r2*(r2+1)/2 - (ll)(c-1)*c/2) == (tc.prefix_p[r2] - tc.prefix_p[c-1])) ||
!(((ll)r2*(r2+1)*(2LL*r2+1)/6 - (ll)(c-1)*c*(2LL*(c-1)+1)/6) == (tc.prefix_p2[r2] - tc.prefix_p2[c-1])) ){
was_invalid2 = true;
invalid_count--;
}
// Remove boundary at c-1
starts.erase(it1);
// Now check merged interval [l2, r2]
bool valid = (((ll)r2*(r2+1)/2 - (ll)(l2-1)*l2/2) == (tc.prefix_p[r2] - tc.prefix_p[l2-1])) &&
(((ll)r2*(r2+1)*(2LL*r2+1)/6 - (ll)(l2-1)*l2*(2LL*(l2-1)+1)/6) == (tc.prefix_p2[r2] - tc.prefix_p2[l2-1]));
if(!valid){
invalid_count++;
}
}
}
}
// Handle edge(c, c+1)
bool edge2_before = false, edge2_after = false;
// Edge(c, c+1) is present if s[c] == 'R' or s[c+1] == 'L'
edge2_before = (old_char == 'R') || (c < tc.n && tc.s[c] == 'L');
edge2_after = (tc.s[c-1] == 'R') || (c < tc.n && tc.s[c-1] == 'L');
// Incorrect logic here, re-define properly
// Correct condition: edge(c, c+1) is present if s[c] == 'R' or s[c+1] == 'L'
// Since we toggled s[c-1], handle edge(c, c+1) based on new s[c]
edge2_before = (old_char == 'R') || ((c < tc.n) && (tc.s[c] == 'L'));
edge2_after = (new_char == 'R') || ((c < tc.n) && (tc.s[c] == 'L'));
if(edge2_before != edge2_after){
if(edge2_before && !edge2_after){
// Add boundary at c
// Split into [l, c] and [c+1, r]
auto it_split = starts.upper_bound(c);
--it_split;
int l = *it_split;
int r;
auto it_next = next(it_split);
if(it_next != starts.end()){
r = *it_next -1;
}
else{
r = tc.n;
}
// Remove [l, r] from invalid_count if invalid
if(!(((ll)r*(r+1)/2 - (ll)(l-1)*l/2) == (tc.prefix_p[r] - tc.prefix_p[l-1])) ||
!(((ll)r*(r+1)*(2LL*r+1)/6 - (ll)(l-1)*l*(2LL*(l-1)+1)/6) == (tc.prefix_p2[r] - tc.prefix_p2[l-1])) ){
invalid_count--;
}
// Insert boundary at c
starts.insert(c+1);
// Check [l, c] and [c+1, r]
bool valid1 = true, valid2 = true;
if(l <= c){
valid1 = (((ll)c*(c+1)/2 - (ll)(l-1)*l/2) == (tc.prefix_p[c] - tc.prefix_p[l-1])) &&
(((ll)c*(c+1)*(2LL*c+1)/6 - (ll)(l-1)*l*(2LL*(l-1)+1)/6) == (tc.prefix_p2[c] - tc.prefix_p2[l-1]));
}
if(!valid1 && l <= c){
invalid_count++;
}
if(c+1 <= r){
valid2 = (((ll)r*(r+1)/2 - (ll)c*(c+1)/2) == (tc.prefix_p[r] - tc.prefix_p[c])) &&
(((ll)r*(r+1)*(2LL*r+1)/6 - (ll)c*(c+1)*(2LL*c+1)/6) == (tc.prefix_p2[r] - tc.prefix_p2[c]));
}
if(!valid2 && c+1 <= r){
invalid_count++;
}
}
else if(!edge2_before && edge2_after){
// Remove boundary at c
// Merge [l, c] and [c+1, r] into [l, r]
auto it1 = starts.find(c+1);
if(it1 == starts.end()) {
// No boundary to remove
} else {
int l1 = *it1 -1;
int l = l1;
int r;
auto it_prev = it1;
--it_prev;
l = *it_prev;
// Find r
auto it_next = next(it1);
if(it_next != starts.end()){
r = *it_next -1;
}
else{
r = tc.n;
}
// Remove [l, c] and [c+1, r] from invalid_count if invalid
bool was_invalid1 = false, was_invalid2 = false;
// Check [l, c]
if(!(((ll)c*(c+1)/2 - (ll)(l-1)*l/2) == (tc.prefix_p[c] - tc.prefix_p[l-1])) ||
!(((ll)c*(c+1)*(2LL*c+1)/6 - (ll)(l-1)*l*(2LL*(l-1)+1)/6) == (tc.prefix_p2[c] - tc.prefix_p2[l-1])) ){
was_invalid1 = true;
invalid_count--;
}
// Check [c+1, r]
if(!(((ll)r*(r+1)/2 - (ll)c*(c+1)/2) == (tc.prefix_p[r] - tc.prefix_p[c])) ||
!(((ll)r*(r+1)*(2LL*r+1)/6 - (ll)c*(c+1)*(2LL*c+1)/6) == (tc.prefix_p2[r] - tc.prefix_p2[c])) ){
was_invalid2 = true;
invalid_count--;
}
// Remove boundary at c+1
starts.erase(it1);
// Check merged [l, r]
bool valid = (((ll)r*(r+1)/2 - (ll)(l-1)*l/2) == (tc.prefix_p[r] - tc.prefix_p[l-1])) &&
(((ll)r*(r+1)*(2LL*r+1)/6 - (ll)(l-1)*l*(2LL*(l-1)+1)/6) == (tc.prefix_p2[r] - tc.prefix_p2[l-1]));
if(!valid){
invalid_count++;
}
}
}
}
// After processing both edges, output the result
cout << (invalid_count ==0 ? "YES" : "NO") << "\n";
}
}
}
```