鱼C论坛

 找回密码
 立即注册
查看: 1202|回复: 11

[数据结构] 别来无恙【线段树模板】-育碧

[复制链接]
发表于 2024-5-12 10:55:14 | 显示全部楼层 |阅读模式
1鱼币
本帖最后由 豆嘉木 于 2024-5-12 10:57 编辑

前言

()

自上了高中并成为一名OIer起,我很久没上过这个论坛
毕竟在我印象里鱼C主要资源比较偏向语法学习
当然也很多高质量的精品文章,但不太可能像小甲鱼做的python和c++那样系统

一个月前我再次登上了鱼C
(在此浅浅吐槽一下)
诚然,鱼C是个很优秀的论坛(我的两千育碧足以证明我的忠心)
但是无处不在的AI让我感觉特别难受
互助板块里的AI就像个纸张
私以为这个AI也不见得能解决多少问题
还少了很多人情味
而且更重要的是现在的论坛让我感觉死气沉沉
(吐槽终)

AI禁区暂时对我而言是一片净土
但是这也太离谱了
论坛本身就是人人之间互相交流的平台,难道不是应该以真人交流为主?
可现在人人交流却只限于 AI禁区 这一个板块
应该开一个AI专区,而不是开一个AI禁区

不是我不能适应AI,我很支持AI,但是我认为论坛不应该让AI这么泛滥

正文

作为AI禁区-数据结构版的第一篇文章
在此奉上我的线段树模板(以 洛谷P3372 为样题):

(先交个代码,后面有时间再补讲解)
(也有可能之后在算法区发后续内容,若如此我也会在这搞个传送门)

#include<bits/stdc++.h>
#define int ll
using namespace std;
using ll = long long;
const int MAXN = 1000007;
int n,m;
ll laz[5000007];
ll a[5000007],w[5000007];

void pushup(int u);
void build(const int u,int l, int r);
bool InRange(int L,int R,int l,int r);
bool OutofRange(int L,int  R,int l,int r);
ll query(int u,int L,int R,int l,int r);
void maketag(int u,int len, ll x);
void pushdown(int u,int L,int R);
void update(int u,int L, int R,int l,int r,ll x);


void pushup(int u){
        w[u]=w[u*2]+w[u*2+1]; 
}

void build(const int u, int l, int r){
        if(l==r){
                w[u]=a[l];
                return;
        }
        int mid = (l+r)/2;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        pushup(u);
}

bool InRange(int L, int R, int l, int r){
        return (L>=l)&&(R<=r);
}

bool OutofRange(int L, int R, int l, int r){
        return (L>r)||(R<l);
}


ll query(int u, int L, int R, int l, int r){ //cha2xun2 
//        if(L>R)return 0;
        if(InRange(L,R,l,r)){ //包含于 
                return w[u];
        }
        else if(!OutofRange(L,R,l,r)){ //交集 
                int mid = (L+R)/2;
                //printf("HERE!! , u=%lld, L=%lld,R=%lld,mid=%lld\n",u,L,R,mid);
                if(L!=R)pushdown(u,L,R); 
                return query(u*2,L,mid,l,r)+query(u*2+1,mid+1,R,l,r);
        }
        else{
                return 0;
        } //空集 
}

void maketag(int u,int len,ll x){
        laz[u]+=x;
        w[u]+=len*x; 
}

void pushdown(int u,int L,int R){
        int mid = (L+R)/2;
        maketag(u*2,mid-L+1,laz[u]);
        maketag(u*2+1,R-mid,laz[u]); 
        laz[u]=0;
}

void update(int u,int L,int R,int l,int r,ll x){
        if(InRange(L,R,l,r)){
                maketag(u,R-L+1,x);
        }
        else if(!OutofRange(L,R,l,r)){
                int mid = (L+R)/2;
                pushdown(u,L,R);
                update(u*2,L,mid,l,r,x);
                update(u*2+1,mid+1,R,l,r,x);
                pushup(u);
        }
}

signed main(){
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=n;++i){
                scanf("%lld",&a[i]); 
        }
        build(1,1,n);
        while(m--){
                int op,x,y;
                ll k;
                scanf("%lld",&op);
                scanf("%lld%lld",&x,&y);
                if(op==1){
                        scanf("%lld",&k);
                        update(1,1,n,x,y,k);
                }else{
                        printf("%lld\n",query(1,1,n,x,y));
                }
        }
        return 0;
}


最佳答案

查看完整内容

放心,论坛本来就是为了人人交流而生,人人交流在论坛上是不会被取代的。况且,人人交流中产生的学习、友情是AI永远无法理解无法替代的。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-5-12 10:55:15 | 显示全部楼层
放心,论坛本来就是为了人人交流而生,人人交流在论坛上是不会被取代的。况且,人人交流中产生的学习、友情是AI永远无法理解无法替代的。
AI确实有很多好处,可以解决很多问题,但是许多更重要的问题都是AI无法解决的。这就是AI的局限性,也许永远也无法打破。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-5-12 15:18:25 | 显示全部楼层
其实流量降低并不能全怪 AI,整个行业都进入了低谷期,希望早日熬过去吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-5-12 19:09:57 | 显示全部楼层
zhangchenyvn 发表于 2024-5-12 16:14
放心,论坛本来就是为了人人交流而生,人人交流在论坛上是不会被取代的。况且,人人交流中产生的学习、友情 ...


同意
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-5-14 18:59:51 | 显示全部楼层
有点难
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-7-5 21:33:01 | 显示全部楼层
码风很像《深进》的,对于竞赛来说感觉非常抽象,但是非常工程化。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2024-7-9 21:47:08 | 显示全部楼层
zhangjinxuan 发表于 2024-7-5 21:33
码风很像《深进》的,对于竞赛来说感觉非常抽象,但是非常工程化。

不太灵活是吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-7-10 08:16:29 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-7-10 08:36:26 | 显示全部楼层
小甲鱼的二师兄 发表于 2024-5-12 15:18
其实流量降低并不能全怪 AI,整个行业都进入了低谷期,希望早日熬过去吧

不瞒,AI降低了人与人的交流,原来没AI我们还交流交流,现在AI泛滥,我是连看都懒得看。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-7-10 08:39:05 | 显示全部楼层
zhangchenyvn 发表于 2024-5-12 16:14
放心,论坛本来就是为了人人交流而生,人人交流在论坛上是不会被取代的。况且,人人交流中产生的学习、友情 ...

一个由AI主导的论坛,你觉得还会有人原意交流?
看看鱼C现在,再看看鱼C以前。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-7-10 17:17:40 | 显示全部楼层
小甲鱼的二师兄 发表于 2024-5-12 15:18
其实流量降低并不能全怪 AI,整个行业都进入了低谷期,希望早日熬过去吧

初二的时候这还是个热门行业,甚至当时还在想着当个码农然后孤寡至死算了。
然后然后,我高三毕业了这会儿就听到了行业低迷的消息。
我:走了去干农业得了。
不开玩笑报了个农业大学,等录取ing
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-7-10 17:18:51 | 显示全部楼层
ba21 发表于 2024-7-10 08:39
一个由AI主导的论坛,你觉得还会有人原意交流?
看看鱼C现在,再看看鱼C以前。

草……还真,昨天扔了个帖子上来没多久就有回复,还以为是之前的朋友来了,结果一看结尾说是AI发的,瞬间失望。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-11 03:26

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表