【校赛小分队之我们有个女生】训练赛6

int j=1;
solve(j);//第j个（按r排）manager来排a
for(int i=2; i<=m; i++)
{
    if(b[i].id>b[j].id&&b[i].t!=b[j].t)
    {
        solve(i);
        j=i;
    }
}

9 3
1 2 3 4 5 6 7 8 9
2 9
1 4
2 6

if(b[i].id>b[k].id)
{
    if(b[i].t!=b[j].t)
    {
        r[cnt++]=i;
        j=i;
    }
    k=i;
}

#include<cstdio>
#include<algorithm>
#define N 200005
using namespace std;
int n,m,a[N],c[N],r[N];
struct mng
{
    int r,t,id;
} b[N];
int cmp(mng a,mng b)
{
    return a.r>b.r;
}
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",&b[i].t,&b[i].r);
        b[i].id=i;
    }
    sort(b+1,b+1+m,cmp);//manager按r排降序
    int j=0,k=0,cnt=0;
    //筛选出r递减的manager序列
    for(int i=1; i<=m; i++)
    {
        if(b[i].id>b[k].id)
        {
            if(b[i].t!=b[j].t)
            {
                r[cnt++]=i;
                j=i;
            }
            k=i;
        }
    }
    for(int i=b[1].r+1; i<=n; i++) c[i]=a[i];
    sort(a+1,a+1+b[1].r);//a数组b[1].r前的排升序
    int tou=1,wei=b[1].r;
    for(int i=0; i<cnt; i++)
        if(b[r[i]].t==2)//当前的第r[i]个manager要降序
            for(int j=b[r[i]].r; j>b[r[i+1]].r; j--) //小的从右到左放过去
                c[j]=a[tou++];
        else
            for(int j=b[r[i]].r; j>b[r[i+1]].r; j--)
                c[j]=a[wei--];//大的从右到左放过去
    for(int i=1; i<=n; i++)
        printf("%d ",c[i]);
    return 0;
}