首先 ，Chtholly 美图欣赏 + 学习 Chtholly Tree
其实我写这 Chtholly Tree 就是来宣传珂学的
学了珂朵莉树，是不是感觉很爽
（15min AC luogu 紫题，别人线段树标记打到想哭，我写个 ODT 直接水过 23333）
那我们先写一个水题练练手
脑洞治疗仪 ？？
emmm, 看到题目的时候，我首先觉得将现在的题目连在一起觉得可以写成小说，而且各种类型的都有
好了，对于题意，可以简化一下：
操作 1：把区间全部赋值成 0，Chtholly 一剑解决（qwq
操作 2：把区间中的 1 的数量统计一下并变成 0，暴力去修补脑洞的区间
操作 3：查询区间中最长连续的 1，暴力求和
很明显，基本暴力 , 直接水过 (ノ≧∇≦)ノ 又愉快的水了一题
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
using namespace std;
#define fors(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(x,i) memset((x),(i),sizeof((x)))
#define max(x,y) ((x) < (y) ? (y) : (x))
#define min(x,y) ((x) < (y) ? (x) : (y))
#define abs(x) ((x) < 0 ? -(x) : (x))
#define Debug(...) fprintf(stderr,__V_ARGS__);
#define IO(x) freopen(""#x"","r",stdin);freopen(""#x"","w",stdout);
int read(){
int s=0,f=1;
char c=getchar();
while(c>'9' || c<'0') {if(c == '-') f = -1; c=getchar();}
while(c <='9' && c>='0') {s = s*10 + c - 48; c=getchar();}
return s*f;
}
void write(int x){
if(x == 0) putchar('0');
if(x < 0) putchar('-'),x=-x;
static int sta[36];
int tot=0;
while(x){
sta[tot++] = x%10;
x/=10;
}
while(tot){
putchar(sta[--tot]+48);
}
}
namespace Chtholly{
struct node
{
int l,r;
mutable int v;
node(int ls,int rs = -1,int vv = 0) : l(ls),r(rs),v(vv) {}
bool operator < (const node &ano) const{
return l < ano.l;
}
};
set<node> s;
#define itset set<node> ::iterator
#define init(); itset itr = split(r+1) , itl = split(l);
itset split(int pos){//基本操作
itset it = s.lower_bound(node(pos));
if(it != s.end() && it->l == pos)
return it;
--it;
if(it->r < pos)
return s.end();
int ls=it->l , rs= it->r;
int vv= it->v;
s.erase(it);
s.insert(node(ls,pos-1,vv));
return s.insert(node(pos,rs,vv)).first;
}
void assign_val(int l,int r,int k){
init();
s.erase(itl,itr);
s.insert(node(l,r,k));
}
void KO(int l,int r,int x,int y){
itset itr = split(r+1) ,itl = split(l);
int ans = 0;
for(itset it = itl ; it!=itr ; ++it){
if(it->v){
ans+=it->r - it->l +1;
}
}//取出能用的
s.erase(itl,itr);
s.insert(node(l,r,0));//删除掉，并合并赋值为 0
if(!ans)
return ;
itr = split(y+1) , itl = split(x);
//开始治疗，如果比 修复的总数还大的话，直接全部赋值为 1，return
if(ans >= y-x+1){
s.erase(itl,itr);
s.insert(node(x,y,1));//可以直接代替 assign
return ;
}
//找到临界点，赋值为 1，return
for(itset it = itl; it!=itr; ++it){
if(it->v == 0){
ans -= it->r - it->l +1;
if(ans < 0){
assign_val(it->l, it->r + ans, 1);
return ;
}
else it->v = 1;
}
}
}
int query(int l,int r){
init();
int ans = 0,tmp = 0;
for(;itl != itr ; ++itl){
if(!itl->v){
ans+=itl->r - itl->l +1;
}
else
{
tmp = max(ans , tmp);
ans = 0;
}
}
return max(ans,tmp);//结尾注意也要 max 一下
}
};
using namespace Chtholly;
int main(int argc, char const *argv[])
{
int n=read(),m=read();
s.insert(node(1,n,1));
while(m--){
int op=read(),a=read(),b=read();
if(op == 0){
assign_val(a,b,0);
}
else if(op == 1){
int x=read(),y=read();
KO(a,b,x,y);
}
else if(op == 2){
write(query(a,b));
puts(" ");
}
}
return 0;
}
emmm ，重点 ，重点。
染色
这是一道树链剖分套线段树的题，大约有一半的操作就是珂朵莉树的区间赋值，可以考虑珂朵莉树骗分。（然后一不小心就 A 了, 233333） 剩下的就是裸的树链剖分了
//去掉了一些头文件（因为太长了 qwq
const int maxn = 1e6+7;
int n,m;
const int inf = (unsigned int)(1<<31) - 1;
struct node
{
int v,u;
}edge[maxn];
int head[maxn],w[maxn],dis[maxn],tot;
void add(int u,int v){
edge[++tot].v= v;
edge[tot].u = head[u];
head[u] = tot;
}
namespace Chtholly{//首先珂朵莉 操作
struct node
{
int l,r;
mutable int v;
node(int ls,int rs = -1,int vv = 0) : l(ls),r(rs),v(vv) {}
bool operator < (const node &ano)const{
return l < ano.l;
}
};
set<node> s;
#define itset set<node> :: iterator
#define init() itset itr=split(r+1),itl=split(l)
itset split(int pos){
itset it = s.lower_bound(node(pos));
if(it!=s.end() && it->l == pos)
return it;
--it;
if(it->r < pos)
return s.end();
int ls = it->l ,rs = it->r;
int vv = it->v;
s.erase(it);
s.insert(node(ls,pos-1,vv));
return s.insert(node(pos,rs,vv)).first;
}
void assign_val(int l,int r,int k){
init();
s.erase(itl,itr);
s.insert(node(l,r,k));
}
//以上均是板子
typedef node lcset;
lcset operator + (lcset a,lcset b){
return lcset(a.l ? a.l : b.l , b.r ? b.r : a.r , a.v+b.v-(a.r==b.l));
}
//这样的一个 lcset 表示左边颜色为 l，右边颜色为 r，共有 v 段颜色。
//由于树链中的操作，我们重载一下运算符，不过要注意用 typedef 重定义一个 node
//不然编译器使用会引起歧义
void init(int l,int r){
int cnt = 1,last = dis[l];
fors(i,l+1,r){
if(dis[i] != last){
s.insert(node(i-cnt,i-1,last));
cnt = 1;
last = dis[i];
}
else ++cnt;
}
s.insert(node(r-cnt+1,r,last));
}//简单的初始化
lcset query(int l,int r){
lcset ans = lcset(0);
init();
for(;itl != itr;++itl)
ans = ans+lcset(itl->v , itl->v , 1);
return ans;
}
}
using namespace Chtholly;
namespace HPD{
int son[maxn],id[maxn],fa[maxn],cnt,depth[maxn],top[maxn],siz[maxn];
int qrange(int x,int y){
lcset lans = lcset(0) , rans = lcset(0);//先初始化两个，代表左边的值，右边的值
while(top[x] != top[y]){
if(depth[top[x]] < depth[top[y]]){//当两个点不在同一条链上
rans = query(id[top[y]],id[y]) + rans;
y = fa[top[y]];////把 y 跳到 y 所在链顶端的那个点的上面一个点
}//分别对两部分求值
else {
lans = query(id[top[x]] , id[x]) + lans;
x = fa[top[x]];
}
}
if(depth[x] > depth[y])
lans = query(id[y],id[x]) + lans;
else rans = query(id[x] , id[y]) + rans;
swap(lans.l , lans .r);
return (lans + rans).v;
}
void uprange(int x,int y,int k){
//直接树剖板子
while(top[x] != top[y]){
if(depth[ top[x] ] < depth[ top[y] ]) swap(x,y);
assign_val(id[top[x]] , id[x] , k);
x = fa[top[x]];
}
if(depth[x] > depth[y]) swap(x,y);
assign_val(id[x],id[y], k);
}
void dfs1(int x,int f,int dep){
depth[x] = dep;
fa[x] = f;
siz[x] = 1;
int maxson = -1;//记录重儿子的儿子数
for(int i = head[x] ; i; i=edge[i].u){
int v = edge[i].v;
if(v == f) continue;//若为父亲则 continue
dfs1(v,x,dep+1);//dfs 其儿子
siz[x] += siz[v];//把它的儿子数加到它身上
if(siz[v] > maxson) son[x] = v,maxson = siz[v];
//标记每个非叶子节点的重儿子编号
}
}
void dfs2(int x,int topf){//x 当前节点，topf 当前链的最顶端的节点
id[x] = ++cnt;
dis[cnt] = w[x];//把每个点的初始值赋到新编号上来
top[x] = topf;//这个点所在链的顶端
if(!son[x]) return ;
dfs2(son[x] , topf);//按先处理重儿子，再处理轻儿子的顺序递归处理
for(int i=head[x];i;i=edge[i].u){
int v = edge[i].v;
if(v == fa[x] || v == son[x]) continue;
dfs2(v,v);//对于每一个轻儿子都有一条从它自己开始的链
}
}
}
using namespace HPD;
int main(int argc, char const *argv[])
{
n=read(),m=read();
fors(i,1,n){
w[i]=read();
}
fors(i,1,n-1){
int a=read(),b=read();
add(a,b),add(b,a);
}
dfs1(1,0,1);
dfs2(1,1);
init(1,n);
char tmp[5];
while(m--){
int x,y,z;
scanf("%s",tmp);
if(tmp[0] == 'C'){
x=read(),y=read(),z=read();
uprange(x,y,z);
}
else if(tmp[0] == 'Q'){
x=read(),y=read();
write(qrange(x,y));
puts(" ");
}
}
return 0;
}
上午写了一下树剖的板子，然后愉悦的颓废了一上午，下午看到这题一下就想到 Chtholly（深陷其中无法自拔 23333）
xzy dalao 直接写了一个珂朵莉链，然后我就呆了 （蒟蒻：直接套板子 ；大佬：改进算法 Orz）
其实据说还可以线段树维护珂朵莉树 （emmm 为什么不直接写个线段树？？？
暴力数据结构只是用来骗骗分的，如果数据不随机，T 的概率很大，至于现在能 A 的几题都还只是数据水（因为以前还没有 Chtholly 23333）。（不过我还是很喜欢 Chtholly (ノ≧∇≦)ノ
0 条评论