ACM-ICPC2017北京网络赛(I) Minimum
时间限制: 1000ms
单点时限: 1000ms
内存限制: 256MB
描述
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.
样例输入
样例输出
题目大意：有两种操作。第一，给定区间，求区间内任意两个数字（可以是同一个数字）乘积的最小值；第二，可以更改某个点的值。
线段树模板题，在线段树内保存一个最大值maxans，一个最小值minans，当minans>0时，最小值为minansminans；当maxans<0时，最小值为maxansmaxanx；其余情况为minans*maxans；
代码如下：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N=1<<18;
struct node
{
int maxx;
int minn;
int val;
}tree[N*4];
int maxans;
int minans;
int data[N];
void build(int l,int r,int i)
{
if(l==r)
{
tree[i].val=data[l];
tree[i].maxx=data[l];
tree[i].minn=data[l];
return ;
}
int mid=(l+r)/2;
build(l,mid,i*2);
build(mid+1,r,i*2+1);
tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);
tree[i].minn=min(tree[i*2+1].minn,tree[i*2].minn);
}
void updata(int l,int r,int pos,int i,int change)
{
if(l==r&&l==pos)
{
tree[i].val=change;
tree[i].maxx=change;
tree[i].minn=change;
return ;
}
int mid=(l+r)/2;
if(pos<=mid)
updata(l,mid,pos,i*2,change);
if(pos>mid)
updata(mid+1,r,pos,i*2+1,change);
tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);
tree[i].minn=min(tree[i*2+1].minn,tree[i*2].minn);
}
void query(int l,int r,int L,int R,int i)
{
if(l>=L&&r<=R)
{
//printf("%d\n",tree[i].val);
maxans=max(maxans,tree[i].maxx);
minans=min(minans,tree[i].minn);
return ;
}
int mid=(l+r)/2;
if(L<=mid)
query(l,mid,L,R,i*2);
if(R>mid)
query(mid+1,r,L,R,i*2+1);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(data,0,sizeof(data));
memset(tree,0,sizeof(tree));
int tmp;
scanf("%d",&tmp);
int num=1<<tmp;
//printf("num=%d\n",num);
for(int i=1;i<=num;i++)
scanf("%d",&data[i]);
/*
for(int i=1;i<=num;i++)
printf("%d ",data[i]);
printf("\n");
*/
build(1,num,1);
int m;
int sym;
int a,b;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&sym,&a,&b);
//printf("a=%d b=%d\n",a,b);
if(sym==2)
{
a++;
updata(1,num,a,1,b);
}
if(sym==1)
{
a++;
b++;
maxans=-1<<18;
minans=1<<18;
//printf("a=%d b=%d\n",a,b);
query(1,num,a,b,1);
//printf("minn=%d maxx=%d\n",minans,maxans);
if(maxans<=0)
printf("%lld\n",(long long)maxans*maxans);
else if(minans>0)
printf("%lld\n",(long long)minans*minans);
else
printf("%lld\n",(long long)minans*maxans);
}
}
}
return 0;
}