首先 ,Chtholly 美图欣赏 + 学习Chtholly Tree

sd

其实我写这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 (ノ≧∇≦)ノ

s

分类: 文章

B_Z_B_Y

虽然也包含些许残酷 , 时间毕竟对任何人都很温柔-。---2018 NOIP 退役人士

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *