- #include<iostream>
- #include<cstdio>
- #include<cmath>
- #include<string>
- #include<cstring>
- using namespace std;
- const int MAXNODE = (1<<20)+5;
- const int MAX = 2e7+10;//2*10^6+10
- const int INF = 0x7fffffff;
- struct NODE{
- int maxvalue, minvalue;
- int left, right;
- }node[MAXNODE];
- int father[MAX];
- void BuildTree(int i, int left, int right)
- {
- node[i].minvalue = INF;
- node[i].maxvalue = -INF;
- node[i].left = left;
- node[i].right = right;
- if(right == left)
- {
- father[left] = i;
- return;
- }
- BuildTree(i<<1, left, (int)(floor(left+right)/2.0));
- BuildTree((i<<1)+1, (int)(floor(left+right)/2.0)+1, right);
- }
- //自底向上更新
- void UpdateTree(int ri)
- {
- if(ri <= 1)
- return;
- int fi = ri/2;
- int a = node[fi<<1].maxvalue;
- int b = node[(fi<<1)+1].maxvalue;
- node[fi].maxvalue = max(a, b);
- a = node[fi<<1].minvalue;
- b = node[(fi<<1)+1].minvalue;
- node[fi].minvalue = min(a, b);
- UpdateTree(ri/2);
- }
- int Max, Min;
- //自顶向上查询
- void Query_max(int i, int l, int r)
- {
- if(node[i].left == l && node[i].right == r)
- {
- Max = max(Max, node[i].maxvalue);
- return;
- }
- i <<= 1;
- if(l <= node[i].right)
- {
- if(r <= node[i].right)
- {
- Query_max(i, l, r);
- }
- else
- {
- Query_max(i, l, node[i].right);
- }
- }
- i++;
- if(r >= node[i].left)
- {
- if(l >= node[i].left)
- {
- Query_max(i, l, r);
- }
- else
- {
- Query_max(i, node[i].left, r);
- }
- }
- }
- void Query_min(int i, int l, int r)
- {
- if(node[i].left == l && node[i].right == r)
- {
- Min = min(Min, node[i].minvalue);
- return;
- }
- i <<= 1;
- if(l <= node[i].right)
- {
- if(r <= node[i].right)
- {
- Query_min(i, l, r);
- }
- else
- {
- Query_min(i, l, node[i].right);
- }
- }
- i++;
- if(r >= node[i].left)
- {
- if(l >= node[i].left)
- {
- Query_min(i, l, r);
- }
- else
- {
- Query_min(i, node[i].left, r);
- }
- }
- }
- int main()
- {
- int k, t, n, g, a, b, c;
- long long ans;
- ios::sync_with_stdio(false);
- cin>>t;
- //cout<<INF<<-INF<<endl;
- while(t--)
- {
- cin>>k;
- BuildTree(1, 1, 1<<k);
- for(int i = 1; i <= 1<<k; i++)
- {
- cin>>g;
- node[father[i]].maxvalue = node[father[i]].minvalue = g;
- UpdateTree(father[i]);
- }
- cin>>n;
- for(int i = 1; i <= n; i++)
- {
- Max = -INF;
- Min = INF;
- cin>>a>>b>>c;
- if(a == 1)
- {
- Query_max(1, b+1, c+1);
- Query_min(1, b+1, c+1);
- //cout<<Max<<" "<<Min<<endl;
- if(Max <= 0)
- {
- ans = (long long)Max*Max;
- cout<<ans<<endl;
- }
- else if(Min >= 0)
- {
- ans = (long long)Min*Min;
- cout<<ans<<endl;
- }
- else
- {
- ans = (long long)Min*Max;
- cout<<ans<<endl;
- }
- }
- else if(a == 2)
- {
- node[father[b+1]].maxvalue = node[father[b+1]].minvalue = c;
- UpdateTree(father[b+1]);
- }
- }
- }
- return 0;
- }
来源: http://www.cnblogs.com/x-1204729564/p/7586828.html