题意：给你一个序列（长度不超过2^17），支持两种操作：单点修改；询问区间中最小的ai*aj是多少（i可以等于j）。
只需要线段树维护区间最小值和最大值，如果最小值大于等于0，那答案就是minv*minv；
如果最大值小于等于零，那么答案就是maxv*maxv；
要是最小值小于零，最大值大于零，答案就是minv*maxv。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 140000
int maxv[N<<2],minv[N<<2];
int T,n;
void buildtree(int rt,int l,int r){
if(l==r){
scanf("%d",&minv[rt]);
maxv[rt]=minv[rt];
return;
}
int m=(l+r>>1);
buildtree(rt<<1,l,m);
buildtree(rt<<1|1,m+1,r);
maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);
minv[rt]=min(minv[rt<<1],minv[rt<<1|1]);
}
void update(int p,int v,int rt,int l,int r){
if(l==r){
minv[rt]=maxv[rt]=v;
return;
}
int m=(l+r>>1);
if(p<=m){
update(p,v,rt<<1,l,m);
}
else{
update(p,v,rt<<1|1,m+1,r);
}
maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);
minv[rt]=min(minv[rt<<1],minv[rt<<1|1]);
}
int qmin(int ql,int qr,int rt,int l,int r){
if(ql<=l && r<=qr){
return minv[rt];
}
int m=(l+r>>1),res=2147483647;
if(ql<=m){
res=min(res,qmin(ql,qr,rt<<1,l,m));
}
if(m<qr){
res=min(res,qmin(ql,qr,rt<<1|1,m+1,r));
}
return res;
}
int qmax(int ql,int qr,int rt,int l,int r){
if(ql<=l && r<=qr){
return maxv[rt];
}
int m=(l+r>>1),res=-2147483647;
if(ql<=m){
res=max(res,qmax(ql,qr,rt<<1,l,m));
}
if(m<qr){
res=max(res,qmax(ql,qr,rt<<1|1,m+1,r));
}
return res;
}
int q;
int main(){
int op,x,y;
scanf("%d",&T);
for(;T;--T){
scanf("%d",&n);
n=(1<<n);
memset(minv,0,sizeof(minv));
memset(maxv,0,sizeof(maxv));
buildtree(1,1,n);
scanf("%d",&q);
for(int i=1;i<=q;++i){
scanf("%d%d%d",&op,&x,&y);
if(op==1){
++x; ++y;
int minn=qmin(x,y,1,1,n);
int maxx=qmax(x,y,1,1,n);
if(minn>=0){
printf("%lld\n",(ll)minn*(ll)minn);
}
else if(maxx<=0){
printf("%lld\n",(ll)maxx*(ll)maxx);
}
else{
printf("%lld\n",(ll)minn*(ll)maxx);
}
}
else{
++x;
update(x,y,1,1,n);
}
}
}
return 0;
}