学步园

动态最值 [ SCOI2006 ]

minmax

5s/256MB

有一个包含n个元素的数组，要求实现以下操作：

DELETE k：删除位置k上的数。右边的数往左移一个位置。

QUERY i j：查询位置i~j上所有数的最小值和最大值。

例如有10个元素：

QUERY 2 8的结果为2 9。依次执行DELETE 3和DELETE 6（注意这时删除的是原始数组的元素7）后数组变为：

QUERY 2 8的结果为1 7。

【输入】

输入文件minmax.in第一行包含两个数n, m，表示原始数组的元素个数和操作的个数。第二行包括n个数，表示原始数组。以下m行，每行格式为1 k或者2 i j，其中第一个数为1表示删除操作，为2表示询问操作。

【输出】

输出文件minmax.out对每个询问操作输出一行，包括两个数，表示该范围内的最小值和最大值。

【样例输入】

10 4

1 5 2 6 7 4 9 3 15

2 2 8

1 3

1 6

2 2 8

【样例输出】

2 9

1 7

【限制】

50%的数据满足1<=n, m<=10⁴，删除操作不超过100个

100%的数据满足1<=n, m<=10⁶, 1<=m<=10⁶

对于所有的数据，数组中的元素绝对值均不超过10⁹

^{这一题和前面operation那一题都很难}

^{但不同的是，operation那一题思维难度不大，而这一题要稍微想想}

^{题目已经很明确地说了是动态的区间，那么我们写线段树又怎么写成动态的呢？}

^{其实根本不用写动态线段树，我们只需要多维护一个节点个数即可}

^{我们先想想线段树在往下传的时候是m=(l+r)/2，然后下面再从 [ l , m ] 和 [ m + 1 , r ] 这两个区间内找}

^{那么我们可以维护一个 sum[ ] 来表示当前区间还剩多少个点，}

^{比如我们要找区间 [ a , b ]，那么我们只需把当前节点 p 的左儿子p*2 的sum值和 a 来作比较，如果 a <= sum[p*2] 的话就说明 [ a , b ] 这个区间在左儿子中有一部分}

^{这样就可以解决上面所说的动态的问题了}

^{cena测试结果}

/*

http://blog.csdn.net/jiangzh7

By Jiangzh
*/
#include<cstdio>
const int N=1000000+10;
const int inf=0x3f3f3f3f;

int n,m;
int _min[N*4],_max[N*4],sum[N*4];

inline int Min(int a,int b){return a<b?a:b;}
inline int Max(int a,int b){return a>b?a:b;}
struct status
{
	int min,max;
	status(){min=inf;max=-inf;}
};

void renew(int p)
{
	sum[p]=sum[p<<1]+sum[(p<<1)+1];
	_min[p]=Min(_min[p<<1],_min[(p<<1)+1]);
	_max[p]=Max(_max[p<<1],_max[(p<<1)+1]);
}

void in_tree(int p,int l,int r,int a,int c)
{
	if(l==r && l==a)
	{
		_min[p]=_max[p]=c;
		sum[p]=1;
		return;
	}
	int m=(l+r)>>1;
	if(a<=m) in_tree(p<<1,l,m,a,c);
	if(a>m) in_tree((p<<1)+1,m+1,r,a,c);
	renew(p);
}

void segment_delete(int p,int l,int r,int a)
{
	if(l==r)
	{
		_min[p]=inf;
		_max[p]=-inf;
		sum[p]=0;
		return;
	}
	int m=(l+r)>>1;
	if(a<=sum[p<<1]) segment_delete(p<<1,l,m,a);
	else segment_delete((p<<1)+1,m+1,r,a-sum[p<<1]);
	renew(p);
}

status query(int p,int l,int r,int a,int b)
{
	status temp;
	if(b-a+1==sum[p])
	{
		temp.min=_min[p];
		temp.max=_max[p];
		return temp;
	}
	int m=(l+r)>>1;
	if(b<=sum[p<<1]) temp=query(p<<1,l,m,a,b);
	else if(a>sum[p<<1]) temp=query((p<<1)+1,m+1,r,a-sum[p<<1],b-sum[p<<1]);
	else{
		status x1,x2;
		x1=query(p<<1,l,m,a,sum[p<<1]);
		x2=query((p<<1)+1,m+1,r,1,b-sum[p<<1]);
		temp.min=Min(x1.min,x2.min);
		temp.max=Max(x1.max,x2.max);
	}
	return temp;
}

void work()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		in_tree(1,1,n,i,x);
	}
	for(int i=1;i<=m;i++)
	{
		int op,x,y;
		scanf("%d",&op);
		if(op==1)//delete
		{
			scanf("%d",&x);
			segment_delete(1,1,n,x);
		}
		else{//query
			scanf("%d%d",&x,&y);
			status ans=query(1,1,n,x,y);
			printf("%d %d\n",ans.min,ans.max);
		}
		//for(int p=1;p<=15;p++) printf("i:min=%d max=%d sum=%d\n",_min[p],_max[p],sum[p]);puts("");
	}
}

int main()
{
	freopen("minmax.in","r",stdin);
	freopen("minmax.out","w",stdout);
	work();
	return 0;
}