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

冷不防 2022-06-08 11:17 135阅读 0赞

时间限制: 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.

样例输入

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);
        else
            update(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);
                        else
                            printf("%lld\n",pmax*pmax);
                    }
                }
                else
                {
                    update(x,1,y);
                }
            }
        }
    }