hihoCoder 1586 Minimum 【线段树】 (ACM-ICPC国际大学生程序设计竞赛北京赛区(2017)网络赛)

#1586 : Minimum
时间限制:1000ms

单点时限:1000ms

内存限制:256MB

描述

You are given a list of integers a0, a1, …, a2^k-1.

You need to support two types of queries:

1. Output Minx,y∈[l,r] {ax∙ay}.

2. Let ax=y.

输入

The first line is an integer T, indicating the number of test cases. (1≤T≤10).

For each test case:

The first line contains an integer k (0 ≤ k ≤ 17).

The following line contains 2^k integers, a0, a1, …, a2^k-1 (-2^k ≤ ai < 2^k).

The next line contains a integer (1 ≤ Q < 2^k), indicating the number of queries. Then next Q lines, each line is one of:

1. 1 l r: Output Minx,y∈[l,r]{ax∙ay}. (0 ≤ l ≤ r < 2^k)

2. 2 x y: Let ax=y. (0 ≤ x < 2^k, -2^k ≤ y < 2^k)

输出

For each query 1, output a line contains an integer, indicating the answer.
样例输入
1
3
1 1 2 2 1 1 2 2
5
1 0 7
1 1 2
2 1 2
2 2 2
1 1 2
样例输出
1
1
4

题目链接：

　　http://hihocoder.com/problemset/problem/1586

题目大意：

　　给2ⁿ个数，两种操作

　　1 输出Min_x,y∈[l,r]{a_x*a_y}.

　　2 令a_x=y

题目思路：

　　【线段树】

　　记录每个区间的最大最小值，并维护，询问时获取当前区间最大最小值，分情况讨论

　　0在最小值左边，0在最小值和最大值之间，0在最大值右边，共3种情况。

　　分别计算答案即可。

　　修改时修改单点值。

  1 /****************************************************
  2 
  3     Author : Coolxxx
  4     Copyright 2017 by Coolxxx. All rights reserved.
  5     BLOG : http://blog.csdn.net/u010568270
  6 
  7 ****************************************************/
  8 #include<bits/stdc++.h>
  9 #pragma comment(linker,"/STACK:1024000000,1024000000")
 10 #define abs(a) ((a)>0?(a):(-(a)))
 11 #define lowbit(a) (a&(-a))
 12 #define sqr(a) ((a)*(a))
 13 #define mem(a,b) memset(a,b,sizeof(a))
 14 const double EPS=0.00001;
 15 const int J=10;
 16 const int MOD=1000000007;
 17 const int MAX=0x7f7f7f7f;
 18 const double PI=3.14159265358979323;
 19 const int N=150004;
 20 using namespace std;
 21 typedef long long LL;
 22 double anss;
 23 LL aans;
 24 int cas,cass;
 25 int n,m,lll,ans;
 26 int min1[N+N],max1[N+N];
 27 void update(int k)
 28 {
 29     min1[k]=min(min1[k+k],min1[k+k+1]);
 30     max1[k]=max(max1[k+k],max1[k+k+1]);
 31 }
 32 void change(int l,int r,int x,int y,int k)
 33 {
 34     if(r<x || x<l)return;
 35     if(l==r)
 36     {
 37         min1[k]=y;
 38         max1[k]=y;
 39         return;
 40     }
 41     int mid=(l+r)>>1;
 42     change(l,mid,x,y,k+k);
 43     change(mid+1,r,x,y,k+k+1);
 44     update(k);
 45 }
 46 void query(int l,int r,int a,int b,int k,int d[])
 47 {
 48     if(r<a || b<l)
 49     {
 50         d[0]=MAX;
 51         d[1]=-MAX;
 52         return;
 53     }
 54     if(a<=l && r<=b)
 55     {
 56         d[0]=min1[k];
 57         d[1]=max1[k];
 58         return;
 59     }
 60     if(l==r)
 61     {
 62         d[0]=min1[k];
 63         d[1]=max1[k];
 64         return;
 65     }
 66     int mid=(l+r)>>1;
 67     int d1[2],d2[2];
 68     query(l,mid,a,b,k+k,d1);
 69     query(mid+1,r,a,b,k+k+1,d2);
 70     update(k);
 71     
 72     d[0]=min(d1[0],d2[0]);
 73     d[1]=max(d1[1],d2[1]);
 74 }
 75 int main()
 76 {
 77     #ifndef ONLINE_JUDGE
 78     freopen("1.txt","r",stdin);
 79 //    freopen("2.txt","w",stdout);
 80     #endif
 81     int i,j,k;
 82     int x,y,z;
 83     for(scanf("%d",&cass);cass;cass--)
 84 //    init();
 85 //    for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
 86 //    while(~scanf("%d",&n))
 87     {
 88         scanf("%d",&n);
 89         n=pow(2,n);
 90         for(i=1;i<=n;i++)
 91         {
 92             scanf("%d",&x);
 93             min1[n+i-1]=x;
 94             max1[n+i-1]=x;
 95         }
 96         for(i=n-1;i;i--)
 97             update(i);
 98         scanf("%d",&m);
 99         for(i=1;i<=m;i++)
100         {
101             scanf("%d%d%d",&z,&x,&y);
102             if(z==1)
103             {
104                 x++,y++;
105                 int d[2];
106                 query(1,n,x,y,1,d);
107                 if(0<=d[0])
108                     aans=1LL*d[0]*d[0];
109                 else if(d[0]<0 && 0<=d[1])
110                     aans=1LL*d[0]*d[1];
111                 else  aans=1LL*d[1]*d[1];
112                 printf("%lld
",aans);
113             }
114             else
115             {
116                 x++;
117                 change(1,n,x,y,1);
118             }
119         }
120     }
121     return 0;
122 }
123 /*
124 //
125 
126 //
127 */

View Code