Minimum
题目链接：https://hihocoder.com/problemset/problem/1586
You are given a list of integers a0, a1, …, a2^k-1.
You need to support two types of queries:
-
Output Minx,y∈[l,r] {ax∙ay}.
-
Let ax=y.
Input
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 l r: Output Minx,y∈[l,r]{ax∙ay}. (0 ≤ l ≤ r < 2k)
-
2 x y: Let ax=y. (0 ≤ x < 2k, -2k ≤ y < 2k)
Output
For each query 1, output a line contains an integer, indicating the answer.
Sample Input
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
Sample Output
1
1
4
先给出一段翻译：
给出一个整数列表a0，a1，…，a2 ^ k-1。
您需要支持两种类型的查询：
1.输出Minx，y∈[l，r] {ax∙ay}。
2.设ax = y。
输入
第一行是整数T，表示测试用例的数量。 （1≤T≤10）。
对于每个测试用例：
第一行包含整数k（0≤k≤17）。
以下行包含2k个整数，a0，a1，…，a2 ^ k-1（-2k≤ai<2k）。
下一行包含一个整数（1≤Q<2k），表示查询数。然后是下一个Q行，每行是以下之一：
-
1 l r：输出Minx，y∈[l，r] {ax∙ay}。 （0≤l≤r<2k）
-
2 x y：设ax = y。 （0≤x<2k，-2k≤y<2k）
产量
对于每个查询1，输出一行包含一个整数，表示答案。
题意：在一段整数列表中进行两种类型的查询：
1.输出Minx，y∈[l，r] {ax∙ay}。
2.设ax = y。
解题思路：线段树的单源点查询，找出最大值和最小值；
（先留个版子 学好线段树再来填坑）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define inf 0x3f3f3f3f
#define lson l,m,root<<1
#define ll long long
#define rson m+1,r,root<<1|1
using namespace std;
const int N=1e6+10;
int st_min[N<<2],st_max[N<<2];
void PushUP(int root)
{
st_min[root]=min(st_min[root<<1],st_min[root<<1|1]);
st_max[root]=max(st_max[root<<1],st_max[root<<1|1]);
}
void build(int l,int r,int root)
{
if(l==r)
{
scanf("%d",&st_min[root]);
st_max[root]=st_min[root];
return ;
}
int m=(l+r)>>1;
build(lson);
build(rson);
PushUP(root);
}
void update(int p,int sc,int l,int r,int root)
{
if(l==r)
{
st_max[root]=sc;
st_min[root]=sc;
return ;
}
int m=(l+r)>>1;
if(p<=m)update(p,sc,lson);
else update(p,sc,rson);
PushUP(root);
}
int query_min(int L,int R,int l,int r,int root)
{
if (L<=l&&r<=R)
{
return st_min[root];
}
int m=(l+r)>>1;
int ret1=inf,ret2=inf;
if(L<=m)ret1=query_min(L,R,lson);
if(R>m) ret2=query_min(L,R,rson);
return min(ret1,ret2);
}
int query_max(int L,int R,int l,int r,int root)
{
if(L<=l&&r<=R)
{
return st_max[root];
}
int m=(l+r)>>1;
int ret1=-inf,ret2=-inf;
if(L<=m)ret1=query_max(L,R,lson);
if(R>m) ret2=query_max(L,R,rson);
return max(ret1,ret2);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
scanf("%d",&n);
int k=pow(2,n);
build(1,k,1);
scanf("%d",&m);
while(m--)
{
int x,a,b;
scanf("%d%d%d",&x,&a,&b);
if(x==1)
{
ll minnn=query_min(a+1,b+1,1,k,1);
ll maxxx=query_max(a+1,b+1,1,k,1);
if(minnn>0)
{
printf("%lld\n",minnn*minnn);
}
else if(maxxx>0)
{
printf("%lld\n",maxxx*minnn);
}
else
printf("%lld\n",maxxx*maxxx);
}
else
update(a+1,b,1,k,1);
}
}
return 0;
}
