Location>code7788 >text

P7706 Wenwen's Photographic Arrangement Problem Solution

Popularity：988 ℃/2024-08-21 18:59:48

P7706 Wenwen's Photographic Arrangement Problem Solution

original question

Read the question and realized it was a line tree. Single point modification + interval query.

The query value is a bit strange though, that's all, let's consider a line tree to maintain thisψ value (hereinafter referred to as the value to be found).

For an interval of values to be found, there are about four cases:

As shown above for each of the four cases:

  1. The maximum value to be found is in the left interval
  2. The maximum value to be found is in the right interval
  3. \(a_i & b_j\) in the left interval
  4. \(b_j & a_k\) In the right interval

Consider ways to merge:

For 1,2, return the larger of the left and right intervals to be solved.

For 3,4, maintain the interval around the\(lt\) together with\(rt\) , respectively, the larger\(a_i-b_j\) larger\(a_k-_j\) If you want to update it, you can just add the larger value on the other side.

From this, it follows that the values to be maintained by the line tree structure are:\(maxx,minn,lt,rt,mx\) , respectively, for the largest\(a\) smallest\(b\) larger\(a_i-b_j\) larger\(a_k-_j\) , and the maximum value to be found in this interval.

Thus the code can be obtained:

#include <bits/stdc++.h>
#define seq(q, w, e) for (int q = w; q <= e; q++)
#define ll long long
using namespace std;
const int maxn = 5e5+10;
const ll inf=-1e8-10;
struct pect{
    ll s,b; //Save Pictures
}a[maxn];
struct node{
    ll maxx,minn; //maxxinterval (math.)agreatest，minninterval (math.)bminimal
    ll lt,rt,mx; //ltinterval (math.) min(bj)-ai,rtinterval (math.) ak-min(bj)
}tree[maxn<<2];

ll ls(ll p){return p<<1;}
ll rs(ll p){return p<<1|1;}

node up_date(node a,node b){
    node p;
    =max(,);
    =min(,);
    =;
    =;
    =max(,max(,)); //三种情况取greatest
    =max(,max(,));
    =max(+,+); //情况取greatest
    =max(,max(,));
    return p;
}

void push_up(ll p){
    tree[p]=up_date(tree[ls(p)],tree[rs(p)]);
}

void build(ll p,ll pl,ll pr){
    if(pl==pr){
        tree[p].maxx=a[pl].s;
        tree[p].minn=a[pl].b;
        tree[p].lt=tree[p].rt=tree[p].mx=inf;
        return;
    }
    ll mid=(pl+pr)>>1;
    build(ls(p),pl,mid);
    build(rs(p),mid+1,pr);
    push_up(p);
}

void change(ll x,ll d,ll p,ll pl,ll pr,ll op){
    if(pl==pr){
        if(op==1) tree[p].maxx=d;
        if(op==2) tree[p].minn=d;
        return;
    }
    ll mid=(pl+pr)>>1;
    if(x<=mid) change(x,d,ls(p),pl,mid,op);
    else change(x,d,rs(p),mid+1,pr,op);
    push_up(p);
}

node query(ll l,ll r, ll p,ll pl,ll pr){
    if(l<=pl&&r>=pr)
        return tree[p];
    ll mid=(pl+pr)>>1;
    if(l>mid) return query(l,r,rs(p),mid+1,pr);
    if(r<=mid) return query(l,r,ls(p),pl,mid);
    return up_date(query(l,r,ls(p),pl,mid),query(l,r,rs(p),mid+1,pr));
}

ll n,m,op;

signed main()
{
    ios::sync_with_stdio(0);
    (0);(0);
    cin>>n>>m;
    seq(i,1,n){
        cin>>a[i].s;
    }
    seq(i,1,n){
        cin>>a[i].b;
    }
    build(1,1,n);
    while(m--){
        int x,y;
        cin>>op>>x>>y;
        if(op==1){
            change(x,y,1,1,n,1);
        }
        if(op==2){
            change(x,y,1,1,n,2);
        }
        if(op==3){
            cout<<query(x,y,1,1,n).mx<<endl;
        }    
    }
    return 0;
}
<Previous Next>