鱼C论坛

 找回密码
 立即注册
查看: 151|回复: 4

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

[复制链接]
发表于 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 为样题):

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

  1. #include<bits/stdc++.h>
  2. #define int ll
  3. using namespace std;
  4. using ll = long long;
  5. const int MAXN = 1000007;
  6. int n,m;
  7. ll laz[5000007];
  8. ll a[5000007],w[5000007];

  9. void pushup(int u);
  10. void build(const int u,int l, int r);
  11. bool InRange(int L,int R,int l,int r);
  12. bool OutofRange(int L,int  R,int l,int r);
  13. ll query(int u,int L,int R,int l,int r);
  14. void maketag(int u,int len, ll x);
  15. void pushdown(int u,int L,int R);
  16. void update(int u,int L, int R,int l,int r,ll x);


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

  20. void build(const int u, int l, int r){
  21.         if(l==r){
  22.                 w[u]=a[l];
  23.                 return;
  24.         }
  25.         int mid = (l+r)/2;
  26.         build(u*2,l,mid);
  27.         build(u*2+1,mid+1,r);
  28.         pushup(u);
  29. }

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

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


  36. ll query(int u, int L, int R, int l, int r){ //cha2xun2
  37. //        if(L>R)return 0;
  38.         if(InRange(L,R,l,r)){ //包含于
  39.                 return w[u];
  40.         }
  41.         else if(!OutofRange(L,R,l,r)){ //交集
  42.                 int mid = (L+R)/2;
  43.                 //printf("HERE!! , u=%lld, L=%lld,R=%lld,mid=%lld\n",u,L,R,mid);
  44.                 if(L!=R)pushdown(u,L,R);
  45.                 return query(u*2,L,mid,l,r)+query(u*2+1,mid+1,R,l,r);
  46.         }
  47.         else{
  48.                 return 0;
  49.         } //空集
  50. }

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

  55. void pushdown(int u,int L,int R){
  56.         int mid = (L+R)/2;
  57.         maketag(u*2,mid-L+1,laz[u]);
  58.         maketag(u*2+1,R-mid,laz[u]);
  59.         laz[u]=0;
  60. }

  61. void update(int u,int L,int R,int l,int r,ll x){
  62.         if(InRange(L,R,l,r)){
  63.                 maketag(u,R-L+1,x);
  64.         }
  65.         else if(!OutofRange(L,R,l,r)){
  66.                 int mid = (L+R)/2;
  67.                 pushdown(u,L,R);
  68.                 update(u*2,L,mid,l,r,x);
  69.                 update(u*2+1,mid+1,R,l,r,x);
  70.                 pushup(u);
  71.         }
  72. }

  73. signed main(){
  74.         scanf("%lld%lld",&n,&m);
  75.         for(int i=1;i<=n;++i){
  76.                 scanf("%lld",&a[i]);
  77.         }
  78.         build(1,1,n);
  79.         while(m--){
  80.                 int op,x,y;
  81.                 ll k;
  82.                 scanf("%lld",&op);
  83.                 scanf("%lld%lld",&x,&y);
  84.                 if(op==1){
  85.                         scanf("%lld",&k);
  86.                         update(1,1,n,x,y,k);
  87.                 }else{
  88.                         printf("%lld\n",query(1,1,n,x,y));
  89.                 }
  90.         }
  91.         return 0;
  92. }
复制代码


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

使用道具 举报

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

使用道具 举报

发表于 2024-5-12 16:14:05 | 显示全部楼层
放心,论坛本来就是为了人人交流而生,人人交流在论坛上是不会被取代的。况且,人人交流中产生的学习、友情是AI永远无法理解无法替代的。
AI确实有很多好处,可以解决很多问题,但是许多更重要的问题都是AI无法解决的。这就是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
回复

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-5-30 03:03

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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