洛谷 P3372 【模板】线段树 1 题解

Analysis

新学了一种很骚气的线段树写法，就是把整个线段树放到一个struct里面，然后可以直接调用里面的函数

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #define int long long
  6 #define maxn 100010
  7 using namespace std;
  8 inline int read()
  9 {
 10     int x=0;
 11     bool f=1;
 12     char c=getchar();
 13     for(; !isdigit(c); c=getchar()) if(c=='-') f=0;
 14     for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+c-'0';
 15     if(f) return x;
 16     return 0-x;
 17 }
 18 inline void write(int x)
 19 {
 20     if(x<0){putchar('-');x=-x;}
 21     if(x>9)write(x/10);
 22     putchar(x%10+'0');
 23 }
 24 int n,m,a[maxn];
 25 struct Segment_tree
 26 {
 27     struct Segment_tree_node
 28     {
 29         int l,r,val,tag;
 30     }node[maxn*4];
 31     int n;
 32     inline int size() {return n;}
 33     inline int left_s(int x) {return (x<<1);}
 34     inline int right_s(int x) {return ((x<<1)|1);}
 35     inline void calc(int x,int y)
 36     {
 37         node[x].tag+=y;
 38         node[x].val+=y*(node[x].r-node[x].l+1);
 39     }
 40     inline void push_up(int x)
 41     {
 42         node[x].val=node[left_s(x)].val+node[right_s(x)].val;
 43     }
 44     inline void push_down(int x)
 45     {
 46         calc(left_s(x),node[x].tag);
 47         calc(right_s(x),node[x].tag);
 48         node[x].tag=0;
 49     }
 50     inline void build(int x)
 51     {
 52         node[x].tag=0;
 53         if(node[x].l==node[x].r)
 54         {
 55             node[x].val=a[node[x].l];
 56             return;
 57         }
 58         int mid=(node[x].l+node[x].r)>>1;
 59         node[left_s(x)].l=node[x].l;
 60         node[left_s(x)].r=mid;
 61         build(left_s(x));
 62         node[right_s(x)].l=mid+1;
 63         node[right_s(x)].r=node[x].r;
 64         build(right_s(x));
 65         push_up(x);
 66     }
 67     inline void init(int l,int r)
 68     {
 69         n=r-l+1;
 70         node[1].l=1;
 71         node[1].r=n;
 72         build(1);
 73     }
 74     inline void update(int x,int l,int r,int v)
 75     {
 76         if(l<=node[x].l&&node[x].r<=r)
 77         {
 78             calc(x,v);
 79             return;
 80         }
 81         push_down(x);
 82         if(l<=node[left_s(x)].r) update(left_s(x),l,r,v);
 83         if(node[right_s(x)].l<=r) update(right_s(x),l,r,v);
 84         push_up(x);
 85      }
 86      inline int query(int x,int l,int r)
 87      {
 88          if(l<=node[x].l&&node[x].r<=r) return node[x].val;
 89          push_down(x);
 90          int ans=0;
 91          if(l<=node[left_s(x)].r)ans+=query(left_s(x),l,r);
 92          if(node[right_s(x)].l<=r)ans+=query(right_s(x),l,r);
 93          return ans;
 94      }
 95 }t;
 96 signed main()
 97 {
 98     n=read();m=read();
 99     for(int i=1;i<=n;i++) a[i]=read();
100     t.init(1,n);
101     for(int i=1;i<=m;i++)
102     {
103         int x=read();
104         if(x==1)
105         {
106             int x=read(),y=read(),z=read();
107             t.update(1,x,y,z);
108         }
109         else if(x==2)
110         {
111             int x=read(),y=read();
112             write(t.query(1,x,y));
113             printf("\n");
114         }
115     }
116     return 0;
117 }

请各位大佬斧正