14045: 【原4045】日天要读书

题目描述

author: MW 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4045

Description

日天想要看一本有n页的书。为了能够提高对于这本书的理解，时光机建议日天以一定的顺序来读这本书，该顺序表示为一个\([1,2,\cdots , n]\)的置换\(P = [p_1,p_2,\cdots , p_n]\)，其中 \(p_i\) 表示第i次阅读的页码。

然而，有些时候，日天的室友月月鸟会对这个序列中位于\([l,r]\)子序列做一个排序。每次排序时，日天都知道他将要阅读的页码\(p_x\)在原来序列中的位置\(x\)。他想知道每次排序后，\(p_x\)的位置是否发生了变化。

由于日天已经习惯了遭遇这样的事，所以每次月月鸟对序列排序后，日天都会把序列恢复原来的顺序，所以可以认为每次排序是独立的。

Input Format

第一行，有两个用空格分隔的正整数n, m\(1\leq n, m \leq 1e4\)，分别代表序列长度以及月月鸟对序列排序的次数

第二行，有m个用空格分隔整数\(p_1,p_2,\cdots , p_n (1\leq p_i \leq n)\) (注：置换中任何数都只出现一次)

之后的m行，每行包含三个用空格分隔的整数\(l_i, r_i, x_i(1\leq l_i \leq r_i \leq n, 1\leq x_i \leq n)\)，分别为排序的左边界，右边界以及日天要读的页码在序列中的位置。

Output Format

对于每一次的排序，输出一行"Yes"或"No"(不含引号),来表示日天要读页码的是否在原位置

Sample Input 1

Sample Output 1

Yes
No
Yes
Yes
No

Sample Input 2

6 5
1 4 3 2 5 6
2 4 3
1 6 2
4 5 4
1 3 3
2 6 3

Sample Output 2

Yes
No
Yes
No
Yes

样例解释

在样例1中，

[1, 2, 3, 4, 5]为排序后的序列, 原来第3个元素的位置没有变化，所以答案为"Yes"
[3, 4, 5, 2, 1]为排序后的序列, 原来第1个元素的位置发生变化，所以答案为"No"
[5, 2, 3, 4, 1]为排序后的序列, 原来第3个元素的位置没有变化，所以答案为"Yes".
[5, 4, 3, 2, 1]为排序后的序列, 原来第4个元素的位置没有变化，所以答案为"Yes".
[5, 1, 2, 3, 4]为排序后的序列, 原来第3个元素的位置发生变化，所以答案为"No".

Limits

对于50%的数据，\(1\leq n,m \leq 100\)

对于100%的数据，\(1\leq n,m \leq 1e4\)

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/23.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

using ll=long long;

/*
int lessCount[10005][10005];
int p[10005];

int main() {
    int n, m;
    cin >> n >> m;
    int tmp;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &tmp);
        p[i] = tmp;
        for (int j = 1; j <= n; ++j) {
            lessCount[j][i] = lessCount[j][i - 1] + (j > tmp);
        }
    }

    int l, r, x;
    while (m--) {
        scanf("%d%d%d", &l, &r, &x);
        tmp = p[x];
        if (lessCount[tmp][r] - lessCount[tmp][l] == x - l) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
}

*/

int main() {
    int table[10005];
    int n, m;
    cin >> n >> m;
    int tmp;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &table[i]);
    }

    int l, r, x, count;
    while (m--) {
        scanf("%d%d%d", &l, &r, &x);
        if (x < l || x > r) {
            printf("Yes\n");
            continue;
        }
        count = 0;
        tmp = table[x];
        for (int i = l; i <= r; ++i) {
            if (table[i] < tmp) ++count;
        }
        if (count == x - l) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
}

FineArtz's solution

/* 日天要读书 */
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> p(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        cin >> p[i];
    vector<int> q(p.begin(), p.end());
    int l, r, x;
    while (m--){
        q = p;
        cin >> l >> r >> x;
        sort(q.begin() + l, q.begin() + r + 1);
        auto ite = find(q.begin(), q.end(), p[x]);
        if (distance(q.begin(), ite) == x) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

int origin[10009] = { 0 };
int num_data[10009] = { 0 };

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &origin[i]);
        //num_data[i] = origin[i];
    }

    for (int i = 0; i < m; ++i) {
        int l, r, x;
        scanf("%d %d %d", &l, &r, &x);
        if (x<l || x>r) {
            printf("Yes\n");
        }
        else {
            int cnt = 0;
            for (int j = l; j <= r; ++j) {
                if (j == x)
                    continue;
                if (origin[j] < origin[x])
                    ++cnt;
            }
            if (cnt == x - l)
                printf("Yes\n");
            else
                printf("No\n");
        }
    }

    return 0;
}

skyzh's solution

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

int A[10000];

int main() {
    int N, T;
    scanf("%d%d", &N, &T);
    for (int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }

    int l, r, x;

    priority_queue <int, vector<int>, greater<int> > q;

    for (int i = 0; i < T; i++) {
        scanf("%d%d%d", &l, &r, &x);
        if (x < l || x > r) printf("Yes\n");
        else {
            for (int j = l; j <= r; j++) q.push(A[j - 1]);
            int pg = A[x - 1];
            int pos = x - l;
            for (int j = 0; j < pos; j++) q.pop();
            if (q.top() == pg) printf("Yes\n");
            else printf("No\n");
            while (!q.empty()) q.pop();
        }
    }
    return 0;
}

yyong119's solution

#include <cstdio>
#define MAX_N 10010
using namespace std;
int n, m, l, r, x, cnt;
int a[MAX_N];
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
    // return res * flag;
    return res;
}
int main() {
    n = read(); m = read();
    for (register int i = 1; i <= n; ++i) a[i] = read();
    for (register int i = 0; i < m; ++i) {
        l = read(), r = read(), x = read();
        if (x < l || x > r) {
                printf("Yes\n");
                continue;
        }
        cnt = 0;
        for (register int j = l; j <= r; ++j)
            if (a[j] < a[x]) ++cnt;
        if (cnt == x - l) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}