2021.11.4测试T1-妹子

题目

今天测试，直接挂完了

写了四个小时，最后发现自己题目理解错误了

有两个区间，在输入了 \(l\) 和 \(r\) 以后，进行查询

\[ min(max(a_1,a_2,...a_p,b_{p+1},...b_n)
\]

即在选定了 \(l\) 和 \(r\) 以后，选定一个\(p\)将\(a\)区间从\(1\)到\(p\)，\(b\)区间从\(p+1\)到\(r\)组成一个新的区间，求其最大值，在对不同\(p\)的取值取最小值

\[_{（注意）题目中没有写逗号，导致我认为是求乘了}
\]

第一种情况当\(a\)的最大值在\(b\)的最大值的前面那么所选区间就一定会经过两个最大值之一 则答案为：

\[min(max(a[l，r]),max(b[l,r]))
\]

第二种： \(a\)的最大值在\(b\)的最大值后面

（1）当一定经过两个或两个之一时，则答案和第一种相同 （2）两个都不经过

则在区间\([x_1,x_2]\)查找\(a\)的最大和\(b\)的最大，再进行比较其位置

如果为第一种，则答案为

\[min(max(a[x_1，x_2]),max(b[x_1,x_2]))
\]

第二种则继续，利用分治思想

直到停止

主要结构：线段树存储最值，区间，加上懒标以及最重要的最值的位置

1：build

 1 void build(int k,int l,int r,int cas){

 2     t[k].l=l,t[k].r=r;

 3     if(l==r){

 4         if(cas==1) t[k].mx=a[l];

 5         else t[k].mx=b[l];

 6         t[k].pos=l;

 7         t[k].lz=0;

 8         return;

 9     }

10     int mid=(l+r)>>1;

11     build(lc,l,mid,cas);

12     build(rc,mid+1,r,cas);

13     pushup(k);

14 }

2：更新

 1 void update(int k,int l,int r,int val){

 2     if(t[k].l>=l && t[k].r<=r){

 3         t[k].lz+=val;

 4         t[k].mx+=val;

 5         return;

 6     }

 7     pushdown(k);

 8     int mid=(t[k].l+t[k].r)>>1;

 9         if(l<=mid) update(lc,l,r,val);

10     if(r>mid) update(rc,l,r,val);

11     pushup(k);

12 }    

3：pushup与pushdown

 1 void pushup(int k){

 2         if(t[lc].mx>=t[rc].mx){

 3             t[k].mx=t[lc].mx;

 4             t[k].pos=t[lc].pos;

 5     }

 6     else{

 7         t[k].mx=t[rc].mx;

 8         t[k].pos=t[rc].pos;

 9     }

10 }

11 void pushdown(int k){

12     if(t[k].lz){

13         t[lc].mx+=t[k].lz;

14         t[rc].mx+=t[k].lz;

15         t[lc].lz+=t[k].lz;

16         t[rc].lz+=t[k].lz;

17         t[k].lz=0;

18     }

19 }

4：查询区间位置

node query(int k,int l,int r){

    if(t[k].l>=l && t[k].r<=r) return (node){t[k].mx,t[k].pos};

    pushdown(k);

    int mid=(t[k].l+t[k].r)>>1;

    node res,now;res.mx=-inf;

    if(l<=mid){

        now=query(lc,l,r);

        if(res.mx<now.mx){

            res.mx=now.mx;

            res.pos=now.pos;

        }

    }

    if(r>mid){

        now=query(rc,l,r);

        if(res.mx<now.mx){

            res.mx=now.mx;

            res.pos=now.pos;

        }

    }

    return res;

}

因为有两个区间，所以建树定义结构体：

struct tree{

    struct nde{

        int l,r,mx,pos,lz;//pos表示最值位置

    }t[N<<2];

    void pushup(int k){

        if(t[lc].mx>=t[rc].mx){

            t[k].mx=t[lc].mx;

            t[k].pos=t[lc].pos;

        }

        else{

            t[k].mx=t[rc].mx;

            t[k].pos=t[rc].pos;

        }

    }

    void pushdown(int k){

        if(t[k].lz){

            t[lc].mx+=t[k].lz;

            t[rc].mx+=t[k].lz;

            t[lc].lz+=t[k].lz;

            t[rc].lz+=t[k].lz;

            t[k].lz=0;

        }

    }

    void build(int k,int l,int r,int cas){

        t[k].l=l,t[k].r=r;

        if(l==r){

            if(cas==1) t[k].mx=a[l];

            else t[k].mx=b[l];

            t[k].pos=l;

            t[k].lz=0;

            return;

        }

        int mid=(l+r)>>1;

        build(lc,l,mid,cas);

        build(rc,mid+1,r,cas);

        pushup(k);

    }

    void update(int k,int l,int r,int val){

        if(t[k].l>=l && t[k].r<=r){

            t[k].lz+=val;

            t[k].mx+=val;

            return;

        }

        pushdown(k);

        int mid=(t[k].l+t[k].r)>>1;

        if(l<=mid) update(lc,l,r,val);

        if(r>mid) update(rc,l,r,val);

        pushup(k);

    }

    node query(int k,int l,int r){

        if(t[k].l>=l && t[k].r<=r) return (node){t[k].mx,t[k].pos};

        pushdown(k);

        int mid=(t[k].l+t[k].r)>>1;

        node res,now;res.mx=-inf;

        if(l<=mid){

            now=query(lc,l,r);

            if(res.mx<now.mx){

                res.mx=now.mx;

                res.pos=now.pos;

            }

        }

        if(r>mid){

            now=query(rc,l,r);

            if(res.mx<now.mx){

                res.mx=now.mx;

                res.pos=now.pos;

            }

        }

        return res;

    }

}A,B;//又学到了

最后总代码：

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define lc k<<1

  4 #define rc k<<1|1

  5 #define num ch-'0'

  6 void get(int &res)

  7 {

  8     char ch;bool flag=0;

  9     while(!isdigit(ch=getchar()))

 10         (ch=='-')&&(flag=true);

 11     for(res=num;isdigit(ch=getchar());res=res*10+num);

 12     (flag)&&(res=-res);

 13 }

 14 const int N=6e5+5,inf=0x3f3f3f3f;

 15 int n,m,a[N],b[N];

 16 struct node{

 17     int mx,pos;

 18 };

 19 struct tree{

 20     struct nde{

 21         int l,r,mx,pos,lz;

 22     }t[N<<2];

 23     void pushup(int k){

 24         if(t[lc].mx>=t[rc].mx){

 25             t[k].mx=t[lc].mx;

 26             t[k].pos=t[lc].pos;

 27         }

 28         else{

 29             t[k].mx=t[rc].mx;

 30             t[k].pos=t[rc].pos;

 31         }

 32     }

 33     void pushdown(int k){

 34         if(t[k].lz){

 35             t[lc].mx+=t[k].lz;

 36             t[rc].mx+=t[k].lz;

 37             t[lc].lz+=t[k].lz;

 38             t[rc].lz+=t[k].lz;

 39             t[k].lz=0;

 40         }

 41     }

 42     void build(int k,int l,int r,int cas){

 43         t[k].l=l,t[k].r=r;

 44         if(l==r){

 45             if(cas==1) t[k].mx=a[l];

 46             else t[k].mx=b[l];

 47             t[k].pos=l;

 48             t[k].lz=0;

 49             return;

 50         }

 51         int mid=(l+r)>>1;

 52         build(lc,l,mid,cas);

 53         build(rc,mid+1,r,cas);

 54         pushup(k);

 55     }

 56     void update(int k,int l,int r,int val){

 57         if(t[k].l>=l && t[k].r<=r){

 58             t[k].lz+=val;

 59             t[k].mx+=val;

 60             return;

 61         }

 62         pushdown(k);

 63         int mid=(t[k].l+t[k].r)>>1;

 64         if(l<=mid) update(lc,l,r,val);

 65         if(r>mid) update(rc,l,r,val);

 66         pushup(k);

 67     }

 68     node query(int k,int l,int r){

 69         if(t[k].l>=l && t[k].r<=r) return (node){t[k].mx,t[k].pos};

 70         pushdown(k);

 71         int mid=(t[k].l+t[k].r)>>1;

 72         node res,now;res.mx=-inf;

 73         if(l<=mid){

 74             now=query(lc,l,r);

 75             if(res.mx<now.mx){

 76                 res.mx=now.mx;

 77                 res.pos=now.pos;

 78             }

 79         }

 80         if(r>mid){

 81             now=query(rc,l,r);

 82             if(res.mx<now.mx){

 83                 res.mx=now.mx;

 84                 res.pos=now.pos;

 85             }

 86         }

 87         return res;

 88     }

 89 }A,B;

 90 int check(int l,int r){

 91     if(l>r) return -inf;

 92     node ma=A.query(1,l,r);

 93     node mb=B.query(1,l,r);

 94     if(ma.pos<=mb.pos) return min(ma.mx,mb.mx);

 95     else{

 96         return min(min(ma.mx,mb.mx),max(check(mb.pos+1,ma.pos-1),max(A.query(1,l,mb.pos).mx,B.query(1,ma.pos,r).mx)));

 97     }

 98 }

 99 int main(){

100     //freopen("girl.in","r",stdin);

101     //freopen("girl.out","w",stdout);

102     get(n);get(m);

103     for(int i=1;i<=n;i++) get(a[i]);

104     for(int i=1;i<=n;i++) get(b[i]);

105     A.build(1,1,n,1);B.build(1,1,n,2);

106     char str;int l,r,k;

107     for(int i=1;i<=m;i++){

108         cin>>str;

109         get(l);get(r);get(k);

110         if(str=='A') A.update(1,l,r,k);

111         else B.update(1,l,r,k);

112         get(l);get(r);

113         cout<<check(l,r)<<endl;

114     }

115     return 0;

116 }

2021.11.4测试T1-妹子的相关教程结束。