Codeforces631C【栈维护+瞎搞】

题意：

百度。

思路：

如果该查询的R比前面的所有都大，那么前面所有都失效。

那么我先预处理出这些有效的。

那最坏的情况不就是栈里面元素（R）很多

n,n-1,n-2,n-3,n-4而且都是相反排序的。。。

总不能每次都那样循环一下，跟着他变吧。

所以找特性：

如果有序列132456

我的栈是

1 6

2 5

1 3

2 2

那么第一步从sort完：123456，那么这个a[6]=6肯定是确定了对吧。

继续看 2 5：我们能确定 a[5]=1,a[4]=2 对吧

继续看1 3 ：我们能确定a[3]=5。

继续看2 2：我们能确定a[2]=3,a[1]=4.

最后输出。这样我觉得仔细自己想想就能瞎搞出来了！自己想出来的方法才有乐趣啊~

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

const int N=2e5+10;

struct asd{

	int flag;

	int R;

}e[N];

stack<asd>q;

int a[N],b[N][2];

int tp[N];

bool cmp(int x,int y)

{

	return x>y;

}

int main()

{

	asd now,nex;

	int n,t;

	scanf("%d%d",&n,&t);

	for(int i=1;i<=n;i++)

		scanf("%d",&a[i]);

	for(int i=1;i<=t;i++)

		scanf("%d%d",&e[i].flag,&e[i].R);

	for(int i=1;i<=t;i++)

	{

		while(!q.empty()&&q.top().R<e[i].R)

			q.pop();

		if(!q.empty()&&e[i].flag==q.top().flag)

			continue;

		q.push(e[i]);

	}

	int num=0;

	while(!q.empty())

	{

		num++;

		b[num][0]=q.top().flag;b[num][1]=q.top().R;

		q.pop();

	}

	if(b[num][0]==1)

		sort(a+1,a+b[num][1]+1);

	else

		sort(a+1,a+b[num][1]+1,cmp);

	if(num==1)

	{

		for(int i=1;i<=n;i++)

			printf("%d ",a[i]);

		return 0;

	}

	int ii=n,jj=1,ij=n;

	int s=1;

	for(;ij>b[num][1];ij--,ii--)

		tp[ij]=a[ij];

	for(int i=num;i>=2;i--)

	{

		int cnt=b[i][1]-b[i-1][1];

		if(s%2==0)

			for(int p=1;p<=cnt;p++,ij--,jj++)

				tp[ij]=a[jj];

		else

			for(int p=1;p<=cnt;p++,ij--,ii--)

				tp[ij]=a[ii];

		s++;

	}

	if(s%2==0)

		for(int p=1;p<=b[1][1];p++,ij--,jj++)

			tp[ij]=a[jj];

	else

		for(int p=1;p<=b[1][1];p++,ij--,ii--)

				tp[ij]=a[ii];

	for(int i=1;i<=n;i++)

		printf("%d ",tp[i]);

	return 0;

}

/*

6 4

1 3 4 5 2 6

1 6

2 5

1 3

2 2

*/

巴特西

Codeforces631C【栈维护+瞎搞】

最新文章

热门文章