Codeforces 631C

题意：给定n和m。

给定一个长度为n的序列，m次操作。

接下来m次操作，每行第一个数若为1,则增序排列，若为2则降序排列，第二个数是排列的范围，即从第一个数排序到第某个数。

思路：

首先，对于其中范围最大的操作和其右方范围次大的操作之间有一个区间，我们可以知道这个区间的序列是按照范围最大的操作的序列进行的，因为右边不会有新的操作，左边的操作会被这次范围最大的操作取代。同理，向右边不断寻找最大的操作，然后能确定和其右边次大的操作之间的差值的区间的序列的顺序。

如果是增序，那么在确定差值区间的每个元素的时候最后的一定是整个里边最大的，反之则是最小的。我们用两棵平衡树来确定最大的和最小的，然后同时更新这两棵平衡数的数据。

坑点：

这里平衡树使用stl里边的multiset，因为难免序列里边有重复的数。但是multiset的erase函数如果直接把查找到数字当作参数的话会全部删除所有的相同的数。

#include<bits/stdc++.h>
using namespace std;
int jilu[200050];
struct st{
    int id,typ,fanwei;
};
st chuli[200050];
bool cmp(st a,st b){
    if(a.fanwei!=b.fanwei){
        return a.fanwei>b.fanwei;
    }
    return a.id>b.id;
}
multiset<int>da;
multiset<int>xiao;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&jilu[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&chuli[i].typ,&chuli[i].fanwei);
        chuli[i].id=i;
    }
    sort(chuli+1,chuli+1+m,cmp);
    /*for(int i=1;i<=m;i++){
        printf("%d %d
",chuli[i].id,chuli[i].fanwei);
    }
    return 0;*/
    st tmp=chuli[1];
    for(int i=1;i<=tmp.fanwei;i++){
        da.insert(-jilu[i]);
        xiao.insert(jilu[i]);
    }
    for(int i=2;i<=m;i++){
        if(chuli[i].id<tmp.id){
            continue;
        }
        else{
            if(tmp.typ==1){
                for(int j=tmp.fanwei;j>chuli[i].fanwei;j--){
                        int ttt=*da.begin();
                        da.erase(da.find(ttt));
                        xiao.erase(xiao.find(-ttt));
                        jilu[j]=-ttt;
                }
            }
            else{
                for(int j=tmp.fanwei;j>chuli[i].fanwei;j--){
                        int ttt=*xiao.begin();
                        da.erase(da.find(-ttt));
                        xiao.erase(xiao.find(ttt));
                        jilu[j]=ttt;
                }
            }
            tmp=chuli[i];
            if(tmp.id==m){
                break;
            }
        }
    }
    if(tmp.typ==1){
        for(int j=tmp.fanwei;j>0;j--){
                int ttt=*da.begin();
                da.erase(da.find(ttt));
                xiao.erase(xiao.find(-ttt));
                jilu[j]=-ttt;
            }
        }
    else{
    for(int j=tmp.fanwei;j>0;j--){
                int ttt=*xiao.begin();
                da.erase(da.find(-ttt));
                xiao.erase(xiao.find(ttt));
                jilu[j]=ttt;
            }
        }
    for(int i=1;i<=n;i++){
        printf("%d",jilu[i]);
        if(i!=n)
            printf(" ");
    }
}