题目9 : Minimum
时间限制:
1000ms
单点时限:
1000ms
内存限制:
256MB
-
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
样例输出
描述
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 1 4题意：查询给定区间两个数字乘积的最小值注意数字存在负数！！！！！首先求出该区间的最小值和最大值，若最小值大于等于0，那么数字乘积的最小值就是最小值的平方；反之，如果最大值小于0，那乘积的最小值一定是正的，即为最大值的平方，否则就为最小值和最大值的乘积求区间最值问题并修改 则用树状数组 或 线段树代码如下：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef long long int ll; const int MAXN =131084;
const int INF=0x3f3f3f3f;
ll a[MAXN], h[MAXN], l[MAXN];
ll n,m;
ll pow1(ll a,ll b)
{ll res=1,base=a;while(b){if(b&1)res*=base;base*=base;b=b>>1;}return res;
} ll lowbit(ll x)
{ return x & (-x);
}
void updata_min(ll x)
{ ll lx, i; while (x <= n) { h[x] = a[x]; lx = lowbit(x); for (i=1; i<lx; i<<=1) h[x] = min(h[x], h[x-i]); x += lowbit(x); }
}
void updata_max(ll x)
{ll lx, i; while (x <= n) { l[x] = a[x]; lx = lowbit(x); for (i=1; i<lx; i<<=1) l[x] = max(l[x], l[x-i]); x += lowbit(x); }
}
ll query_max(ll x, ll y)
{ ll ans = -INF; while (y >= x) { ans = max(a[y], ans); y --; for (; y-lowbit(y) >= x; y -= lowbit(y)) ans = max(l[y], ans); } return ans;
}
ll query_min(ll x, ll y)
{ ll ans = INF; while (y >= x) { ans = min(a[y], ans); y --; for (; y-lowbit(y) >= x; y -= lowbit(y)) ans = min(h[y], ans); } return ans;
}
int main()
{ ll i, j, x, y, ans_min,ans_max; char c; int t; scanf("%d",&t);while(t--){scanf("%lld",&n);n=pow1(2,n);for (i=1; i<=n; i++) h[i] = 0; for (i=1;i<=n;i++)l[i] = 0;for (i=1; i<=n; i++) { scanf("%lld",&a[i]); updata_min(i); updata_max(i);} scanf("%d",&m);for (i=1; i<=m; i++) { int p;scanf("%d%lld%lld",&p,&x,&y); //cout<<p<<endl;//cout<<endl;if(p==1) {ans_min = query_min(x+1,y+1);//ans_max = query_max(x+1,y+1);//cout<<ans_min<<" "<<ans_max<<endl; if(ans_min>=0)printf("%lld\n",ans_min*ans_min);else{ans_max = query_max(x+1 ,y+1);if(ans_max<=0)printf("%lld\n",ans_max*ans_max);else printf("%lld\n",ans_min*ans_max); }}else{a[x+1]=y;updata_min(x+1);updata_max(x+1);}} } return 0;
}