排序问题-CodeForces 811B-Vladik and Complicated Book

柔情只为你懂 2022-05-16 11:45 327阅读 0赞

*  # 排序问题-CodeForces 811B-Vladik and Complicated Book #

--------------------

*  ## 题目链接：[B. Vladik and Complicated Book][] ##
 *  ## 思路： ##

题意就是给一个长度为n的序列，及排序次数m，每次对序列 l~r 进行升序，问原下标为x的元素在序列中的位置有无改变

设原下标为x的元素为val

数据：(1 ≤ *n*, *m* ≤ 10^4）数据量很大，所以如果每次都把子序列 l~r 取出来排序然后找val的位置，超时是不可避免的

所以来讨论下val在序列中的位置是怎么确定的

**首先val的位置改变，只是会在进行排序的子序列 l~r 中**，所以在序列中位置没有改变等价于在子序列中的位置没有改变

***已知子序列将进行升序排序，所以val在子序列中的位置，取决于在子序列中有多少个元素比val小***

所以用val与子序列中每个元素进行比较，确定val的位置

**子序列中小于等于val的元素个数为Index，那么val排序后在序列中 的位置为 l+Index-1**

*  ## 代码： ##

#include <iostream>
    #include <algorithm>
    using namespace std;
    #define MAX_Size 10100
    int Page[MAX_Size];
    int main()
    {
        int n,m;
        int l,r,x;
        while(cin>>n>>m)
        {
            for(int i=1; i<=n; i++)
                cin>>Page[i];
            while(m--)
            {
                cin>>l>>r>>x;
                int Index=0;
                for(int i=l; i<=r; i++)
                    if(Page[x]>=Page[i])
                        Index++;
                //cout<<Index<<endl;
                if(Index+l-1==x)
                    cout<<"Yes"<<endl;
                else
                    cout<<"No"<<endl;
    
            }
        }
        return 0;
    }

[B. Vladik and Complicated Book]: http://codeforces.com/problemset/problem/811/B