Penchick and Satay Sticks Solution

Quartz_Blocks · 2024-11-23 22:27:01 · 题解

介绍一种时间慢但是特殊的做法。

(大炮轰蚊子？)

众所周知，有一种数据结构叫 ST 表，它可以 O(1) 解决 RMQ 问题的单次查询。

众所又周知，对于一个位于 i 的元素 a_i，需要移动到位置 j (i < j)，若 \max{(a_i,a_i+1,\dots,a_j)} - a_i > 1 或者 a_i - \min{(a_i,a_i+1,\dots,a_j)} > 1，那么 a_i 在通过交换操作往 j 位置移动时一定不能到达。因为在这个区间当中存在无法与 a_i 交换的值，所以 a_i 一定无法到达 j 位置。

那求 \max{(a_i,a_i+1,\dots,a_j)} - a_i > 1 和 a_i - \min{(a_i,a_i+1,\dots,a_j)} > 1 的过程不就是 RMQ 问题吗？

我们就可以预处理两个 ST 表，一个用于存储最大值，一个用于存储最小值。

既然有了这两个 ST 表，问题自然就迎刃而解了！

Code:

#include <bits/stdc++.h>
using namespace std;
#include<bits/stdc++.h>
using namespace std;
int n;
int a[200010];//存储序列
int log_2[200010];//预处理 log_2 的值
int mx[200010][21];// mx 数组（也就是 ST 表）
int mn[200010][21];// mx 数组（也就是 ST 表）
inline int read(){//快速读入
    int x = 0,f = 1;// x 代表数字，f 代表符号
    char ch = getchar();//读入字符
    while(ch < '0' || ch > '9'){//没读入到数字
        if(ch == '-') f = -1;//读入到了负
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){//读入到了数字
        x = x*10 + ch-48;//加入 x
        ch = getchar();
    }
    return x * f;
}
void gen(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        a[i] = read();
        mx[i][0] = a[i];//初始化 mx[i][0]，单个数字的区间最大值肯定是那个数字。
        mn[i][0] = a[i];//初始化 mx[i][0]，单个数字的区间最大值肯定是那个数字。
    } 

    for(int j = 1;j <= log_2[n];j++){// 先以 j 为维度
        for(int i = 1;i + (1 << j) - 1 <= n;i++){//再生成
            mx[i][j] = max(mx[i][j-1],mx[i+(1 << (j-1))][j-1]);//状态转移
            mn[i][j] = min(mn[i][j-1],mn[i+(1 << (j-1))][j-1]);//状态转移
        }
    }
    return;
}
int que(int l,int r,bool op){//op == 1 max      op == 0 min
    int t = log_2[r-l+1];
    return (op ? max(mx[l][t],mx[r - (1 << t) + 1][t]) : min(mn[l][t],mn[r - (1 << t) + 1][t]));
}

void solve(){
    gen();
    for(int i = 1;i <= n;i++){
        if(a[i] != i){
            bool flag = 1;
            if(que(min(i,a[i]),max(i,a[i]),1) - a[i] >= 2){
                flag = 0;
            }
            if(a[i] - que(min(i,a[i]),max(i,a[i]),0) >= 2){
                flag = 0;
            }
            if(flag == 0){
                cout << "NO\n";
                return;
            }
        }
    }
    cout << "YES\n";
    return;
}
// n + n log n + T()
int main(){
    log_2[1] = 0;//log 1 = 0
    for(int i = 2;i <= 200000;i++){
        log_2[i] = log_2[i / 2] + 1;//计算 log 的值。
    }
    int T;
    cin >> T;
    while(T--){
        solve();
    }

    return 0;
}