华北水利水电大学 第二届ACM-ICPC校赛

ProblemA: 第x个数

Time Limit: 1 Memory Limit: 128 MB Submit 8 Solved 5 Description silchen得到了长度为N的一个全排列(n个数字互不相同，并且都在[1n])，现在dark di出了一个问题，他会对于这个数列进行M次操作，并且在M次操作之后他会询问silchen第x个数字是什么。

操作有2种类型： 1.将下标[lr]中的数字变为一个递增数列。

2.将下标[lr]中的数字变为一个递减数列。

现在silchen向你来求助了。

Input 第一行输入一个整数T，代表数据组数，T小于等于5 每组数据第一行输入2个整数，分别表示nm其中n是数列长度，m是操作数，nm均不大于1000.

第二行输入n个整数，表示一个排列.

接下去m行3个整数，olr，o为0表示第一种操作，o为1表示第二种操作，保证l，r范围为1到n，且l <= r。

最后输入一个整数x表示要求第x个数字 x范围为1到n。 Output 输出一个数字，表示第x个数字的大小。

Sample Input 1 6 3 1 6 2 5 3 4 0 1 4 1 3 6 0 2 4 3 Sample Output 5 HINT

第一次操作后数列变成 1 2 5 6 3 4

第二次操作后数列变成 1 2 6 5 4 3

第三次操作后数列变成 1 2 5 6 4 3

所以第3个数字是5

呃，感觉模拟就好吧，想不出什么好的优化方法。。。

#include
using namespace std;

const int maxn=1001;

int n,T,m,o,r,l,x;

int a[maxn];

bool cmp(const int a,const int b)
{
    return a>b;
}

void solve()
{
    if(!o)
    {
        sort(a+l,a+r+1);
    }
    else
    {
        sort(a+l,a+r+1,cmp);
    }
}

int main()
{

    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=0;i!=m;i++)
        {
            scanf("%d %d %d",&o,&l,&r);
            solve();
        }
        scanf("%d",&x);
        printf("%d
",a[x]);
    }
    return 0;
}