题意：区间内乘积最小值，带修改。
解题关键：线段树裸题，考场上以为x y必须不等，还维护了次小值，尼玛嗨尼玛嗨，划水一整场，心态爆炸。
注意坐标需要+1
1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<algorithm> 5 #include<cmath> 6 #include<iostream> 7 #define inf 0x3f3f3f3f 8 using namespace std; 9 typedef long long ll; 10 const int maxn=131073; 11 ll a[maxn],tree1[maxn<<2],tree2[maxn<<2]; 12 void pushup(int rt){ 13 tree1[rt]=max(tree1[rt<<1|1],tree1[rt<<1]); 14 tree2[rt]=min(tree2[rt<<1|1],tree2[rt<<1]); 15 } 16 void build(ll rt,ll l,ll r){ 17 if(l==r){ 18 tree1[rt]=tree2[rt]=a[l]; 19 return; 20 } 21 ll mid=(l+r)>>1; 22 build(rt<<1,l,mid); 23 build(rt<<1|1,mid+1,r); 24 pushup(rt); 25 } 26 27 void update(ll rt,ll l,ll r,ll p,ll c){ 28 if(l>r) return; 29 if(l==r){ 30 tree1[rt]=tree2[rt]=c; 31 return; 32 } 33 ll mid=(l+r)>>1; 34 if(p<=mid) update(rt<<1, l, mid, p, c); 35 else update(rt<<1|1, mid+1, r, p, c); 36 pushup(rt); 37 } 38 39 ll query1(ll rt,ll l,ll r,ll tl,ll tr){ 40 if(tl>tr) return -inf; 41 if(tl<=l&&tr>=r){ 42 return tree1[rt]; 43 } 44 ll mid=(l+r)>>1,res=-inf; 45 if(tl<=mid) res=max(res,query1(rt<<1,l,mid,tl,tr)); 46 if(tr>mid) res=max(query1(rt<<1|1,mid+1,r,tl,tr),res); 47 return res; 48 } 49 50 ll query2(ll rt,ll l,ll r,ll tl,ll tr){ 51 if(tl>tr) return inf; 52 if(tl<=l&&tr>=r){ 53 return tree2[rt]; 54 } 55 ll mid=(l+r)>>1,res=inf; 56 if(tl<=mid) res=min(res,query2(rt<<1,l,mid,tl,tr)); 57 if(tr>mid) res=min(query2(rt<<1|1,mid+1,r,tl,tr),res); 58 return res; 59 } 60 61 int main(){ 62 ll n,m; 63 ios::sync_with_stdio(0); 64 cin.tie(0); 65 cout.tie(0); 66 ll t; 67 cin>>t; 68 while(t--){ 69 cin>>n; 70 n=1<<n; 71 memset(tree1, 0, sizeof tree1); 72 memset(tree2,0,sizeof tree2); 73 memset(a,0,sizeof a); 74 for(int i=1;i<=n;i++) cin>>a[i]; 75 build(1, 1, n); 76 cin>>m; 77 for(int i=0;i<m;i++){ 78 int a,b,c; 79 cin>>a>>b>>c; 80 if(a==1){ 81 ll ans1=query1(1,1,n,b+1,c+1); 82 ll ans2=query2(1,1,n,b+1,c+1); 83 if(ans1>=0&&ans2<0){ 84 cout<<1ll*ans1*ans2<<" "; 85 continue; 86 } 87 else if(ans1>=0&&ans2>=0){ 88 cout<<1ll*ans2*ans2<<" "; 89 continue; 90 } 91 else{ 92 cout<<1ll*ans1*ans1<<" "; 93 } 94 } 95 else{ 96 update(1, 1, n, b+1, c); 97 } 98 } 99 } 100 101 }