描述
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 2k integers, a0, a1, …, a2^k-1 (-2k ≤ ai < 2k).
The next line contains a integer (1 ≤ Q < 2k), 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 < 2k)
2. 2 x y: Let ax=y. (0 ≤ x < 2k, -2k ≤ y < 2k)
输出
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 解题思路：
之前没看到有负号和可以相等，想复杂了，zz,其实很简单，要想区间内两个数的乘积最小，那么当区间最大值max>=0,区间最小值min>=0时，最小的不就是min的平方（因为可以相
等），当max<0,min<0时， 最小的就是max*max了，当max>0.min<0时最小的就是min*max.
实现代码：
#include <cstdio>
#include <cstring>
#include<iostream>
#include<cmath>
#define inf 0x7fffffff
#define lson l , m , rt << 1
#define ll long long
#define rson m + 1 , r , rt << 1 | 1
using namespace std;
const int maxn = ; int st_min[maxn<<],st_max[maxn<<]; inline int minn(int a,int b) { return a>b?b:a; }
inline int maxx(int a,int b) { return a>b?a:b; }
void PushUP(int rt)
{
st_min[rt] = minn(st_min[rt<<],st_min[rt<<|]);
st_max[rt] = maxx(st_max[rt<<],st_max[rt<<|]);
}
void build(int l,int r,int rt) {
if (l == r)
{
scanf("%d",&st_min[rt]);
st_max[rt] = st_min[rt];
return ;
}
int m = (l + r) >> ;
build(lson);
build(rson);
PushUP(rt);
} int query_min(int L,int R,int l,int r,int rt)
{
if (L <= l && r <= R) {
return st_min[rt];
}
int m = (l + r) >> ;
int ret1 = inf,ret2 = inf;
if (L <= m) ret1 = query_min(L , R , lson);
if (R > m) ret2 = query_min(L , R , rson);
return minn(ret1,ret2);
}
void update(int p,int num,int l,int r,int rt) {
if (l == r) {
st_max[rt] = num;
st_min[rt] = num;
return ;
}
int m = (l + r) >> ;
if (p <= m) update(p , num , lson);
else update(p , num , rson);
PushUP(rt);
}
int query_max(int L,int R,int l,int r,int rt)
{
if (L <= l && r <= R) {
return st_max[rt];
}
int m = (l + r) >> ;
int ret1 = -inf,ret2 = -inf;
if (L <= m) ret1 = query_max(L , R , lson);
if (R > m) ret2 = query_max(L , R , rson);
return maxx(ret1,ret2);
} int main()
{
int n,m,t,i,k,x,y,z,ms;
for(i=;i<;i++)
ms++;
long long sum;
scanf("%d",&t);
while(t--)
{
scanf("%d",&k);
int n = pow(,k);
build(,n,);
scanf("%d",&m);
while(m--){
scanf("%d%d%d",&x,&y,&z);
if(x==){
y+=;
update(y,z,,n,);
}
else{
y+=;z+=;
ll ans1 = query_min(y,z,,n,);
ll ans2 = query_max(y,z,,n,);
if(ans1<&&ans2>=){
sum = ans1*ans2;
printf("%lld\n",sum);
}
else if(ans1<&&ans2<){
sum = ans2 * ans2;
cout<<sum<<endl;
}
else{
sum = ans1*ans1;
printf("%lld\n",sum);
}
}
}
}
return ;
}