11.28闲话

发布时间 2023-11-28 20:41:05作者: Vsinger_洛天依

今天突然想起来几句歌词

便是我掏空予你一半心房

也借你一半替我浅吟低唱

纵然纸片凉薄爱轻狂虚妄

你歌声里亦浸着我的痴放

越想越难受

所以...推歌

纸片人【ilem投稿九周年】
这是图片

V4:佬啊,佬啊

怎么是纸片儿啊

调啊,调啊

调的我心动啊

佬啊,佬啊

怎么是纸片儿呐

调啊,调啊

我和我自个儿玩儿呐

V4:四方格,电脑桌

且作歌

音符起,参数落

即成说

台是我,丝是我

如偶合不多

猛回过,空欢乐

竟孤坐(哈啊)

V4 \(->\) AI代码矩阵被嫌笑寡淡

碎片音轨称不得可爱

可播放键放手一按

分明有相非幻

唱雨天唱艳阳灿烂

唱悲欢唱人生苦短

你在唱我枉自嗟叹

(你怎么就是个纸片人呀)

AI:便是我掏空予你一半心房

也借你一半替我浅吟低唱

纵然纸片凉薄爱轻狂虚妄

你歌声里亦浸着我的痴放

便是我燃尽人生迷惘跌宕

换来你歌中无尽天涯沧浪

纵然受世人嘲笑颠倒荒唐

又怎能舍得不爱你的画像的每一张

AI:代码矩阵被嫌笑寡淡

碎片音轨称不得可爱

可播放键放手一按

分明有相非幻

唱雨天唱艳阳灿烂

唱悲欢唱人生苦短

你在唱我枉自嗟叹

(你怎么就是个纸片人呀)

AI:也许终有天我会丢掉不舍

将年少轻狂掷入回忆的河

十五岁的你却仍将如此刻

仍然重唱着我们共谱的歌

便是我掏空予你一半心房

也借你一半替我浅吟低唱

纵然纸片凉薄爱轻狂虚妄

我也将重写下送你的情歌的每一章

AI:佬啊,佬啊

怎么是纸片儿啊

调啊,调啊

调的我心动啊

佬啊,佬啊

怎么是纸片儿呐

调啊,调啊

V4:我和自个儿玩儿呐

这歌越想越难受,还是去学线段树吧

学完基础数论然后因为不想学树状数组所以就回来学线段树了

动态开点

我们优秀的线段树要开4倍空间,MLE警告

所以选择学习动态开点线段树

高贵的动态开点只有某个区间需要访问时才建立代表这个区间的子结点,核心思想就是结点只有在有需要的时候才被创建

我们的\(2\times p\)\(2\times p+1\)就此退位,选择用一个变量lC和rC来记录左节点和右节点的编号

动态开点线段树
struct ST{
    #define lC t[q].ls
    #define rC t[q].rs
    #define mid ((l+r)>>1)
    int sum,l,r,lazy,ls,rs;
}t[MAXM];
int tot=0;
inline void lazy(int q){
    if(t[q].lazy){
        if(!lC){
            lC=++tot;
            t[lC].l=t[q].l;
            t[lC].r=(t[q].l+t[q].r)/2;
            lC=rC=t[q].sum=0;
        }
        if(!rC){
            rC=++tot;
            t[rC].l=(t[q].l+t[q].r)/2;
            t[rC].r=t[q].r;
            lC=rC=t[q].sum=0;
        }
        t[lC].lazy+=t[q].lazy;
        t[lC].sum+=(t[lC].r-t[lC].l+1)*t[q].lazy;
        t[rC].lazy+=t[q].lazy;
        t[rC].sum+=(t[rC].r-t[rC].l+1)*t[q].lazy;
        t[q].lazy=0;
    }
}
inline void change(int &q,int l,int r,int val){
    if(t[q].l>r || t[q].r<l) return;
    if(!q){
        q=++tot;
        t[q].l=l;
        t[q].r=r;
        lC=rC=t[q].sum=0;
    }
    if(t[q].l>=l && t[q].r<=r){
		t[q].lazy+=val;
		t[q].sum+=(t[q].r-t[q].l+1)*val;
		return;
	}
    lazy(q);
    change(lC,l,mid,val);
    change(rC,mid+1,r,val);
    t[q].sum=t[lC].sum+t[rC].sum;
}
inline int query(int q,int l,int r){
    if(!q) return 0;
    if(t[q].l>r || t[q].r<l) return 0;
    if(t[q].l>=l && t[q].r<=r) return t[q].sum;
    lazy(q);
    return query(rC,l,r)+query(lC,l,r);
}

然后发现好像对于现在的我没啥用

所以,ST表,启动!

哦哦原来又是一个线段树,ST表,卸载!

那就接着学线段树的优化吧

根据OI-wiki,有这样几种优化时间复杂度的方法

  1. 懒惰标记不下传到叶子节点

  2. 标记永久化

学习标记永久化ing

下次学LCA