齐齐排序题解

分析题意：

1. 一对有n个数的数列，m次操作，每次操作的代号ti为1或2，并且有操作范围xi。
2. 操作代号为1，将数列中下标从1到xi范围的数按升序排序。
3. 操作代号为2，将数列中下标从1到xi范围的数按降序排序。
4. 输出操作后的序列。

做法：

1. 需要排序，则用快速排序sort。
2. 每次遍历时按照当前要求进行操作。

优化：
不难发现从1到xi中，将会有重复操作，我们只需要把1到xi中范围最广的xi找出来，在进行排序，会起到去重的效果。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[200010],t[200010],x[200010];
int n,m;

bool cmp(int x,int y)
{
    return x>y;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=m;i++) scanf("%d%d",&t[i],&x[i]);
    int maxnxi=0;
    for (int i=m;i>=1;i--)
    {
        if (x[i]>maxnxi) maxnxi=x[i];
        else t[i]=0;//找到此时最大的xi就可以将之前的重复操作舍去。
    }
    for(int i=1;i<=m;i++)
    {
        if(t[i]==1)
        {
            sort(a+1,a+x[i]+1);
        }
        else if(t[i]==2)
        {
            sort(a+1,a+x[i]+1,cmp);
        }
    }
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    return 0;
}

完结，谢谢观看。