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

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

线段树操作，原来题并不难。。。。。

当时忽略了一个重要问题，就是ax*ay要最小时，x、y可以相等，那就简单了！结果显然是模最小的数的平方或者是个负数。

要求乘积最小只要求区间内最大值、最小值和绝对值小的数，再判断min,max正负就行了。

 下面的代码相当于建了三个树分别存Min，Max，Mid（abs(Min)）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 #define lson l,m,rt<<1
  7 #define rson m+1,r,rt<<1|1
  8 using namespace std;
  9 typedef long long ll;
 10 const int maxn=(1<<17)+2000;
 11 int Max[maxn<<2],Min[maxn<<2],Mid[maxn<<2];
 12 
 13 int mid(int a,int b)
 14 {
 15     if(abs(a)<abs(b)) return a;
 16     else return b;
 17 }
 18 
 19 void PushUpMax(int rt)
 20 {
 21     Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
 22 }
 23 
 24 void PushUpMin(int rt)
 25 {
 26     Min[rt]=min(Min[rt<<1],Min[rt<<1|1]);
 27 }
 28 
 29 void PushUpMid(int rt)
 30 {
 31     Mid[rt]=mid(Mid[rt<<1],Mid[rt<<1|1]);
 32 }
 33 
 34 
 35 void Build(int l,int r,int rt)
 36 {
 37     if(l==r){
 38         scanf("%d",&Max[rt]);
 39         Min[rt]=Mid[rt]=Max[rt];
 40         return;
 41     }
 42     int m=(l+r)>>1;
 43     Build(lson);
 44     Build(rson);
 45     PushUpMax(rt);
 46     PushUpMin(rt);
 47     PushUpMid(rt);
 48 }
 49 
 50 void Update(int pos,int val,int l,int r,int rt)
 51 {
 52     if(l==r){
 53         Mid[rt]=Min[rt]=Max[rt]=val;
 54         return;
 55     }
 56     int m=(l+r)>>1;
 57     if(pos<=m) Update(pos,val,lson);
 58     else Update(pos,val,rson);
 59     PushUpMax(rt);
 60     PushUpMin(rt);
 61     PushUpMid(rt);
 62 }
 63 
 64 int QueryMax(int L,int R,int l,int r,int rt)
 65 {
 66     if(L<=l&&r<=R){
 67         return Max[rt];
 68     }
 69     int m=(l+r)>>1;
 70     int res=-maxn-5000;
 71     if(L<=m) res=max(res,QueryMax(L,R,lson));
 72     if(R>m) res=max(res,QueryMax(L,R,rson));
 73     return res;
 74 }
 75 
 76 int QueryMin(int L,int R,int l,int r,int rt)
 77 {
 78     if(L<=l&&r<=R){
 79         return Min[rt];
 80     }
 81     int m=(l+r)>>1;
 82     int res=maxn+5000;
 83     if(L<=m) res=min(res,QueryMin(L,R,lson));
 84     if(R>m) res=min(res,QueryMin(L,R,rson));
 85     return res;
 86 }
 87 
 88 int QueryMid(int L,int R,int l,int r,int rt)
 89 {
 90     if(L<=l&&r<=R){
 91         return Mid[rt];
 92     }
 93     int m=(l+r)>>1;
 94     int res=maxn;
 95     if(L<=m) res=mid(res,QueryMid(L,R,lson));
 96     if(R>m) res=mid(res,QueryMid(L,R,rson));
 97     return res;
 98 }
 99 
100 int main()
101 {
102     int T,n,m,k,a,b;
103     scanf("%d",&T);
104     while(T--)
105     {
106         scanf("%d",&n);
107         n=1<<n;
108         Build(1,n,1);
109         scanf("%d",&m);
110         while(m--)
111         {
112             scanf("%d%d%d",&k,&a,&b);
113             a++;
114             if(k==1){
115                 b++;
116                 ll t1=(ll)QueryMax(a,b,1,n,1);
117                 ll t2=(ll)QueryMin(a,b,1,n,1);
118                 ll t3=(ll)QueryMid(a,b,1,n,1);
119                 if((t1>=0)&&(t2<=0))
120                     printf("%lld
",t1*t2);
121                 else if(t1<0||t2>0)
122                     printf("%lld
",t3*t3);
123             }
124             else Update(a,b,1,n,1);
125         }
126     }
127     return 0;
128 }

 从[0,n-1]建树

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 #define lson l,m,rt<<1
  7 #define rson m+1,r,rt<<1|1
  8 using namespace std;
  9 typedef long long ll;
 10 const int maxn=(1<<17)+2000;
 11 int Max[maxn<<2],Min[maxn<<2],Mid[maxn<<2];
 12 
 13 int mid(int a,int b)
 14 {
 15     if(abs(a)<abs(b)) return a;
 16     return b;
 17 }
 18 
 19 void PushUpMax(int rt)
 20 {
 21     Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);
 22 }
 23 
 24 void PushUpMin(int rt)
 25 {
 26     Min[rt]=min(Min[rt<<1],Min[rt<<1|1]);
 27 }
 28 
 29 void PushUpMid(int rt)
 30 {
 31     Mid[rt]=mid(Mid[rt<<1],Mid[rt<<1|1]);
 32 }
 33 
 34 void Build(int l,int r,int rt)
 35 {
 36     if(l==r){
 37         scanf("%d",&Max[rt]);
 38         Min[rt]=Mid[rt]=Max[rt];
 39         return;
 40     }
 41     int m=(l+r)>>1;
 42     Build(lson);
 43     Build(rson);
 44     PushUpMax(rt);
 45     PushUpMin(rt);
 46     PushUpMid(rt);
 47 }
 48 
 49 void Update(int pos,int val,int l,int r,int rt)
 50 {
 51     if(l==r){
 52         Max[rt]=Min[rt]=Mid[rt]=val;
 53         return;
 54     }
 55     int m=(l+r)>>1;
 56     if(pos<=m) Update(pos,val,lson);
 57     else Update(pos,val,rson);
 58     PushUpMax(rt);
 59     PushUpMin(rt);
 60     PushUpMid(rt);
 61 }
 62 
 63 int QueryMax(int L,int R,int l,int r,int rt)
 64 {
 65     if(L<=l&&r<=R){
 66         return Max[rt];
 67     }
 68     int m=(l+r)>>1;
 69     int res=-maxn;
 70     if(L<=m) res=max(res,QueryMax(L,R,lson));
 71     if(R>m) res=max(res,QueryMax(L,R,rson));
 72     return res;
 73 }
 74 
 75 int QueryMin(int L,int R,int l,int r,int rt)
 76 {
 77     if(L<=l&&r<=R){
 78         return Min[rt];
 79     }
 80     int m=(l+r)>>1;
 81     int res=maxn;
 82     if(L<=m) res=min(res,QueryMin(L,R,lson));
 83     if(R>m) res=min(res,QueryMin(L,R,rson));
 84     return res;
 85 }
 86 
 87 int QueryMid(int L,int R,int l,int r,int rt)
 88 {
 89     if(L<=l&&r<=R){
 90         return Mid[rt];
 91     }
 92     int m=(l+r)>>1;
 93     int res=maxn;
 94     if(L<=m) res=mid(res,QueryMid(L,R,lson));
 95     if(R>m) res=mid(res,QueryMid(L,R,rson));
 96     return res;
 97 }
 98 
 99 int main()
100 {
101     int T,n,m,c,a,b;
102     scanf("%d",&T);
103     while(T--)
104     {
105         scanf("%d",&n);
106         n=1<<n;
107         Build(0,n-1,1);
108         scanf("%d",&m);
109         while(m--)
110         {
111             scanf("%d%d%d",&c,&a,&b);
112             if(c==1){
113                 ll t1=QueryMax(a,b,0,n-1,1);
114                 ll t2=QueryMin(a,b,0,n-1,1);
115                 ll t3=QueryMid(a,b,0,n-1,1);
116                 if(t1>=0&&t2<=0)
117                     printf("%lld
",t1*t2);
118                 else
119                     printf("%lld
",t3*t3);
120             }
121             else Update(a,b,0,n-1,1);
122         }
123     }
124     return 0;
125 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/zxhyxiao/p/7616020.html