题目链接：http://codeforces.com/problemset/problem/631/C
Each month Blake gets the report containing main economic indicators of the company "Blake Technologies". There are n commodities produced by the company. For each of them there is exactly one integer in the final report, that denotes corresponding revenue. Before the report gets to Blake, it passes through the hands of m managers. Each of them may reorder the elements in some order. Namely, the i-th manager either sorts first ri numbers in non-descending or non-ascending order and then passes the report to the manager i + 1, or directly to Blake (if this manager has number i = m).
Employees of the "Blake Technologies" are preparing the report right now. You know the initial sequence ai of length n and the description of each manager, that is value ri and his favourite order. You are asked to speed up the process and determine how the final report will look like.
The first line of the input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the number of commodities in the report and the number of managers, respectively.
The second line contains n integers ai (|ai| ≤ 109) — the initial report before it gets to the first manager.
Then follow m lines with the descriptions of the operations managers are going to perform. The i-th of these lines contains two integers tiand ri (
, 1 ≤ ri ≤ n), meaning that the i-th manager sorts the first ri numbers either in the non-descending (if ti = 1) or non-ascending (if ti = 2) order.
Print n integers — the final report, which will be passed to Blake by manager number m.
3 1
1 2 3
2 2
2 1 3
4 2
1 2 4 3
2 3
1 2
2 4 1 3
In the first sample, the initial report looked like: 1 2 3. After the first manager the first two numbers were transposed: 2 1 3. The report got to Blake in this form.
In the second sample the original report was like this: 1 2 4 3. After the first manager the report changed to: 4 2 1 3. After the second manager the report changed to: 2 4 1 3. This report was handed over to Blake.
题意:给一个N个大小的数组,进行M次操作。一次操作包含t,r，t为1则是序号1到r非递减排序（递增排序）t为2则是序号1到r非递增排序（递减排序）
最后输出操作后的数组。
解释下第二个样例，原来是 1 2 4 3。
第一次操作2 3 则序号1到3的数降序排列为 4 2 1 3
第二次操作1 2 则序号1到2的数升序排列为 2 4 1 3
思路：暴力肯定是不行的，时间复杂度太高了O（m*nlogn）。我们不得不想怎么优化，去减掉一些不需要的操作。
比如:后面的操作r大于前者的操作r时，是不是前者的操作白做了呢？因为这种情况后者会覆盖前者的操作，所以可以去到前者没用的操作。
这样操作r会成一个递减趋势。我们会想到用栈存储有用的操作，再依次排序，但是依旧超时。
哪怎么办呢？我们仔细想一下。操作r已经把数组截成一段一段的了。我们只要先排序，再一段一段取就好了。不太懂我们举个栗子先
5 4
5 2 4 1 3
1 2
1 3
1 1
2 2
我们知道只有第二次和第四次操作有用。而第二次操作的r 3 和第四次操作的r 2已经将数组截成三份
5 2| 4| 1 3
我们可以知道1 3不用排序，可以直接放入答案数组
而剩下的我们先排序（这里用的是升序排）(红色为已经排好放入答案数组了）
2 4| 5| 1 3
而第二次操作r 3和下一次操作r 2之间的数放入答案数组，这里正好是升序直接将5放入数组
2 4| 5| 1 3
最后将2 4降序，反过来放入答案
4 2| 5|1 3
我们为什么取操作与操作之间的数呢？因为我们后面操作的排序方向不一定和前面相同，但是我们可以保证操作与操作之间的数排序方向。
比如就是刚刚举的列子，第二次操作和第四次操作排序方向就不同，但是序号2到3（就是数字5）一定是升序排的，但序号1到2是降序，不能直接放入答案数组，他是降序，所以反过来放入数组。
我用的是双向队列。
具体代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
struct node{
int t,r;
};
int a[200005],ans[200005];
deque<node>q;
int main()
{
int n,m;
node p,temp;
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<m;i++)
{
cin>>p.t>>p.r;
while(!q.empty())
{
temp=q.back();
if(p.r>=temp.r)//保存操作递减序列
q.pop_back();
else
break;
}
q.push_back(p);
}
p=q.front();
for(int i=p.r;i<n;i++)//将不用排序的可以直接放入答案数组
ans[i]=a[i];
sort(a,a+p.r);//用升序排列剩下的
int w=q.size();
int l=0,r=p.r,k=0;
for(int i=0;i<w-1;i++)
{
p=q.front();
q.pop_front();
temp=q.front();
if(p.t==1)//升序
{
k=0;
for(int j=temp.r;j<p.r;j++)
{
ans[j]=a[r-p.r+temp.r+k];
k++;
}
r-=k;
}
else if(p.t==2)//降序
{
k=0;
for(int j=p.r-1;j>=temp.r;j--)
{
ans[j]=a[l+k];
k++;
}
l+=k;
}
}
p=q.front();
q.pop_front();
if(p.t==1)//最后一个操作的处理
{
k=0;
for(int i=0;i<p.r;i++)
{
ans[i]=a[r-p.r+k];
k++;
}
}
else if(p.t==2)
{
k=0;
for(int i=p.r-1;i>=0;i--)
{
ans[i]=a[l+k];
k++;
}
}
cout<<ans[0];
for(int i=1;i<n;i++)
cout<<" "<<ans[i];
cout<<endl;
return 0;
}