ACM-ICPC国际大学生程序设计竞赛北京赛区(2017)网络赛 I.Minimum（线段树区间极值+分类讨论）

描述

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

题解：

直接线段树保存区间最大值和最小值，然后根据他们的正负情况来得出结果

代码：

#include<iostream>
#include<cstring>
#include<stdio.h>
#include<math.h>
#include<string>
#include<stdio.h>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<deque>
#include<algorithm>
#define ll long long
#define INF 1008611111
#define M (t[k].l+t[k].r)/2
#define lson k*2
#define rson k*2+1
using namespace std;
ll pmax,pmin;
struct node
{int l,r;ll minn;ll maxx;
}t[600000];
void pushup(int k)
{t[k].minn=min(t[lson].minn,t[rson].minn);t[k].maxx=max(t[lson].maxx,t[rson].maxx);
}
void build(int l,int r,int k)
{t[k].l=l;t[k].r=r;if(l==r){scanf("%lld",&t[k].minn);t[k].maxx=t[k].minn;return;}int mid=M;build(l,mid,lson);build(mid+1,r,rson);pushup(k);
}
void update(int pos,int k,int v)
{if(t[k].l==t[k].r){t[k].minn=v;t[k].maxx=v;return;}int mid=M;if(pos<=mid)update(pos,lson,v);elseupdate(pos,rson,v);pushup(k);
}
void query(int l,int r,int k)
{if(t[k].l==l&&t[k].r==r){pmin=min(t[k].minn,pmin);pmax=max(t[k].maxx,pmax);return;}int mid=M;if(r<=mid)query(l,r,lson);else if(l>mid)query(l,r,rson);else{query(l,mid,lson);query(mid+1,r,rson);}
}
int main()
{int i,j,n,m,test,k,d,x,y;scanf("%d",&test);while(test--){scanf("%d",&k);n=1;for(i=0;i<k;i++)n*=2;build(0,n-1,1);scanf("%d",&m);for(i=0;i<m;i++){scanf("%d%d%d",&d,&x,&y);if(d==1){pmin=INF;pmax=-INF;query(x,y,1);if(pmin>=0){printf("%lld\n",pmin*pmin);}else{if(pmax>=0)printf("%lld\n",pmax*pmin);elseprintf("%lld\n",pmax*pmax);}}else{update(x,1,y);}}}
}