10.14T3 线段树

动态最值（JSOI2007）2389

【问题描述】有一个包含n个元素的数组，要求实现以下操作：

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

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

例如有10个元素：

位置	1	2	3	4	5	6	7	8	9	10
元素	1	5	2	6	7	4	9	3	1	5

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

位置	1	2	3	4	5	6	7	8
元素	1	5	6	7	4	3	1	5

QUERY 2 8的结果为1 7。

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

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

【数据规模】

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

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

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

【样例输入】

10 4

1 5 2 6 7 4 9 3 1 5

2 2 8

1 3

1 6

2 2 8

【样例输出】

2 9

1 7

【分析】

线段树，注意处理删除后的移动，线段树不能真的移动，只能标记，通过区间内实有个数来统计计算将询问区间对应到原区间

code：

 1 #include<iostream>
 2 using namespace std;
 3 const int INF=0x7fffffff/2,Maxn=1000005;
 4 struct LineTree{int a,b,Max,Min,num;}Tree[Maxn*4];
 5 int a[Maxn],N,M,Max,Min;
 6 void Read()
 7 {  int i;
 8    scanf("%d%d",&N,&M);
 9    for(i=1;i<=N;i++)scanf("%d",&a[i]);
10 }
11 void Build(int v,int L,int R)
12 {  Tree[v].a=L;Tree[v].b=R;Tree[v].num=R-L+1;
13 if(L==R){  Tree[v].Max=a[L];Tree[v].Min=a[L];return; }
14    Build(2*v,L,(L+R)/2);
15    Build(2*v+1,(L+R)/2+1,R);
16    Tree[v].Max=max(Tree[2*v].Max,Tree[2*v+1].Max);
17    Tree[v].Min=min(Tree[2*v].Min,Tree[2*v+1].Min);
18 }
19 void Delete(int v,int X)
20 {  if(X==1&&Tree[v].num==1)
21  {Tree[v].Max=-INF;Tree[v].Min=INF;Tree[v].num=0;return;}
22    if(X<=Tree[2*v].num) Delete(2*v,X);
23 else Delete(2*v+1,X-Tree[2*v].num);
24    Tree[v].num--;
25 Tree[v].Max=max(Tree[2*v].Max,Tree[2*v+1].Max);
26    Tree[v].Min=min(Tree[2*v].Min,Tree[2*v+1].Min);
27 }
28 void Ask(int v,int x,int y)
29 {  if(x==1&&y==Tree[v].num)//刚好对应区间
30    {  Max=max(Max,Tree[v].Max);
31       Min=min(Min,Tree[v].Min);
32       return;
33    }
34    if(y<=Tree[2*v].num){Ask(2*v,x,y); return;}//在左区间内
35    if(x>Tree[2*v].num)//右区间，修改询问区间（统一减去左区间的有效数个数）
36 {Ask(2*v+1,x-Tree[2*v].num,y-Tree[2*v].num); return;}
37 //跨两个区间
38    Ask(2*v,x,Tree[2*v].num); 
39    Ask(2*v+1,1,y-Tree[2*v].num); 
40 }
41 void Deal()
42 {  int i,x,y,type;
43    for(i=1;i<=M;i++)
44    {  scanf("%d",&type);
45       if(type==1){scanf("%d",&x);Delete(1,x);}
46       if(type==2)
47       {  scanf("%d%d",&x,&y);Max=-INF; Min=INF;
48          Ask(1,x,y);
49          printf("%d %d
",Min,Max);
50       }
51    }
52 }
53 int main()
54 {  Read();
55    Build(1,1,N);
56    Deal();
57 }

over