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

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

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

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

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            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)
          
           >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<
           
            =0)&&(t2<=0))120 printf("%lld\n",t1*t2);121 else if(t1<0||t2>0)122 printf("%lld\n",t3*t3);123 }124 else Update(a,b,1,n,1);125 }126 }127 return 0;128 }
           
          
         
        
       
      
     

 从[0,n-1]建树

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             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)
           
            >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<
            
             =0&&t2<=0)117 printf("%lld\n",t1*t2);118 else119 printf("%lld\n",t3*t3);120 }121 else Update(a,b,0,n-1,1);122 }123 }124 return 0;125 }