最敏捷的机器人

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 88  Solved: 39

[][][][] []

Description

Wind设计了很多机器人。但是它们都认为自己是最强的，于是，一场比赛开始了……机器人们都想知道谁是最敏捷

的，于是它们进行了如下一个比赛。首先，他们面前会有一排共n个数，它们比赛看谁能最先把每连续k个数中最大

和最小值写下来，当然，这些机器人运算速度都很快，它们比赛的是谁写得快。但是Wind也想知道答案，你能帮助

他吗？ 

Input

每组测试数据 

第1行为n,k(1<=k<=n<=100000) 

第2行共n个数，为数字序列，所有数字均在longint范围内。 

Output

共n-k+1行 

第i行为第i~i+k-1这k个数中的最大和最小值 

Sample Input

5 31 2 3 4 5

Sample Output

3 14 25 3 【注释】由于输入文件太大。特将数据范围缩小10倍，希望大家努力优化算法。

HINT

陷入被printf坑成疯狂RE的INF洞

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #define inf INT_MAX 6 using namespace std; 7 struct point{ 8     int maxv,minv; 9 }tree[400010];10 int n,k;11 int a[100001];12 struct segment_tree{13     void Build(int root,int l,int r)14     {15         if (l==r)16         {17             tree[root].maxv=tree[root].minv=a[l];18             return;19         }20         int mid=(l+r)>>1;21         Build(root*2,l,mid);22         Build(root*2+1,mid+1,r);23         tree[root].maxv=max(tree[root*2].maxv,tree[root*2+1].maxv);24         tree[root].minv=min(tree[root*2].minv,tree[root*2+1].minv);25     }26     void Query(int root,int l,int r,int x,int y,int &maxx,int &minx)27     {28         if (x<=l && y>=r)29         {30             maxx=max(tree[root].maxv,maxx);31             minx=min(tree[root].minv,minx);32             return;33         }34         int mid=(l+r)>>1;35         if (x<=mid)36             Query(root*2,l,mid,x,y,maxx,minx);37         if (y>mid)38             Query(root*2+1,mid+1,r,x,y,maxx,minx);39     }40 }S;41 int main()42 {43     scanf("%d%d",&n,&k);44     for (int i=1;i<=n*4+1;i++)45         tree[i].maxv=-inf,tree[i].minv=inf;46     for (int i=1;i<=n;i++)47         scanf("%d",&a[i]);48     S.Build(1,1,n);49     for (int i=1;i<=n-k+1;i++)50     {51         int maxx=-inf,minx=inf;52         S.Query(1,1,n,i,i+k-1,maxx,minx);53         printf("%d",maxx),putchar(' '),printf("%d\n",minx);54     }55     return 0;56 }