首页 > 代码库 > nyoj-119 士兵杀敌（三） 线段树

nyoj-119 士兵杀敌（三） 线段树

2024-10-02 05:22:02   214人阅读

士兵杀敌（三）

时间限制：2000 ms  |  内存限制：65535 KB
难度：5
 
描述

南将军统率着N个士兵，士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进行比较，计算出两个人的杀敌数差值，用这种方法一方面能鼓舞杀敌数高的人，另一方面也算是批评杀敌数低的人，起到了很好的效果。

所以，南将军经常问军师小工第i号士兵到第j号士兵中，杀敌数最高的人与杀敌数最低的人之间军功差值是多少。

现在，请你写一个程序，帮小工回答南将军每次的询问吧。

注意，南将军可能询问很多次。

 
输入
只有一组测试数据
第一行是两个整数N,Q，其中N表示士兵的总数。Q表示南将军询问的次数。(1<N<=100000,1<Q<=1000000)
随后的一行有N个整数Vi(0<=Vi<100000000)，分别表示每个人的杀敌数。
再之后的Q行，每行有两个正正数m,n，表示南将军询问的是第m号士兵到第n号士兵。
输出
对于每次询问，输出第m号士兵到第n号士兵之间所有士兵杀敌数的最大值与最小值的差。
样例输入
5 2
1 2 6 9 3
1 2
2 4
样例输出
1
7
来源
经典改编
上传者
　　张云聪
题解
　　朴素的暴力暴力算法会超时，因为是O(n^2)的复杂度。可以用线段树来实现，时间复杂度是O(N*logN)的。
　　注意m，n的大小关系不确定。
代码
 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<bits/stdc++.h>
 6 using namespace std;
 7 
 8 #define MAXNUM 100000000
 9 #define MINNUM -1
10 const int M=1e5;
11 int a[M];
12 //根据题目，求区间最大值和最小值
13 struct{
14     int l,r;
15     int ans[2];   //a[0]最大值，a[1]最小值
16 }tree[M*4];
17 
18 void build(int x,int l,int r)
19 {
20     tree[x].l=l,tree[x].r=r;
21     tree[x].ans[0]=MINNUM,tree[x].ans[1]=MAXNUM;
22     if(l==r)    //叶子结点
23     {
24         tree[x].ans[1]=a[r];
25         tree[x].ans[0]=a[r];
26     }
27     else
28     {
29         int mid = (l+r)/2;
30         build(x<<1,l,mid);
31         build(x<<1|1,mid+1,r);
32         int a=tree[x<<1].ans[0],b=tree[x<<1|1].ans[0];
33         int c=tree[x<<1].ans[1],d=tree[x<<1|1].ans[1];
34         tree[x].ans[0]=max(a,b);
35         tree[x].ans[1]=min(c,d);
36     }
37 }
38 
39 void query(int x,int l,int r,int &_max,int &_min)
40 {
41     int L=tree[x].l,R=tree[x].r;
42     if(l<=L&&r>=R)
43     {
44         _max=tree[x].ans[0];
45         _min=tree[x].ans[1];
46         return;
47     }
48     else
49     {
50         int mid = (L+R)/2;
51         int _max1=MINNUM,_min1=MAXNUM;
52         if(mid>=l)  query(x<<1,l,r,_max,_min);
53         if(mid+1<=r)  query(x<<1|1,l,r,_max1,_min1);
54         if(_max1>_max) _max = _max1;
55         if(_min1<_min) _min = _min1;
56         return;
57     }
58 }
59 
60 int main()
61 {
62     int n,m;
63     scanf("%d %d",&m,&n);
64     for(int i=1;i<=m;i++)
65         scanf("%d",&a[i]);
66     build(1,1,m);
67     int l,r;
68     int _max=MINNUM,_min=MAXNUM;
69     while(n--)
70     {
71         _max=MINNUM,_min=MAXNUM;
72         scanf("%d %d",&l,&r);
73         if(l>r)
74         {
75             int temp;
76             temp = l;
77             l = r;
78             r = temp;
79         }
80         query(1,l,r,_max,_min);
81     }
82     return 0;
83 }

 

nyoj-119 士兵杀敌（三） 线段树


联系
我们