崛起的滑稽 @ 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
@崛起的滑稽 但是珂朵莉树板子紫(?啊