有没有区间染色单点查询的题?

题目总版

崛起的滑稽 @ 2024-11-03 13:19:31

rt,想hack下我的区间染色单点查询线段树

#include <bits/stdc++.h>
//#define int int64_t
//#define int __int128
//#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
const int MAXN=1e5+10;
struct LazySegmentTree{
#define lc(x) (x<<1)
#define rc(x) ((x<<1)|1)
#define mid(l,r) ((l+r)>>1)
    struct Node{
        int color;
    };

    Node tr[MAXN<<2];

    void push_up(int p){
        tr[p].color=(tr[lc(p)].color==tr[rc(p)].color&&tr[lc(p)].color!=-1?tr[lc(p)].color:-1);
        //左右子树颜色相同:取子树颜色,否则-1表示不相同
    }

    void push_down(int p,int l,int r){
        if(tr[p].color!=-1&&l<r){
            tr[lc(p)].color=tr[p].color;
            tr[rc(p)].color=tr[p].color;
        }
    }

    void build(int p,int l,int r){
        tr[p]={0};//初始没有颜色
        if(l==r){
            return ;
        }
        build(lc(p),l,mid(l,r));
        build(rc(p),mid(l,r)+1,r);
        push_up(p);
    }

    void update(int p,int l,int r,int L,int R,int k){
    //  cout<<p<<endl;
        if(tr[p].color==k){//修改优化,当当前大区间和染色颜色一样,不需要染色
            return ;
        }
        if(l>=L&&r<=R){
            tr[p].color=k;
            push_down(p,l,r);
            return ;
        }
        push_down(p,l,r);
        if(L<=mid(l,r))
            update(lc(p),l,mid(l,r),L,R,k);
        if(R>mid(l,r))
            update(rc(p),mid(l,r)+1,r,L,R,k);
        push_up(p);
    }

    int query(int p,int l,int r,int k){//本题只需要单点查询
        if(tr[p].color!=-1){
            return tr[p].color;//查询优化,当一个大区间是齐色不需要向下查询
        }
        if(l==k&&k==r){//到底了
            return tr[p].color;
        }
        push_down(p,l,r);
        int res=0;
        if(k<=mid(l,r))
            res=query(lc(p),l,mid(l,r),k);
        else
            res=query(rc(p),mid(l,r)+1,r,k);
        push_up(p);
        return res;
    }
};
LazySegmentTree lst;

by Edward2019 @ 2024-11-03 13:34:07

P4348


by Atri_Lobato @ 2024-11-04 21:35:09

P8463 @崛起的滑稽 试试看(私货夹带


by 崛起的滑稽 @ 2024-11-04 22:03:34

@Edward2019 我嘞个黑啊


by 崛起的滑稽 @ 2024-11-04 22:03:54

@Atri_Lobato 虽然但是啥私货(?


by Atri_Lobato @ 2024-11-04 22:07:20

@崛起的滑稽 伟大的柯学()()


by 崛起的滑稽 @ 2024-11-05 19:45:44

@Atri_Lobato 昨天没仔细看没发现()末日三问题面居然不是珂朵莉树的题()


by Atri_Lobato @ 2024-11-05 22:15:38

@崛起的滑稽 但是珂朵莉树板子紫(?啊


|