再敲线段树

今天下午又敲了一次线段树，洛谷线段树1敲了一遍，大概40min？
然后线段树2敲了2遍，其中第二遍用了18min46s…
想想3min平衡树的lxl，真是珂怕啊…
但是敲第二遍的时候不明白为什么update还要下放懒标记，导致查错查了好长时间…
最后想了一下发现如果不下方懒标记的话，就会导致后面的乘操作没有作用到懒标记上，自然会导致出错。
期间还屡次忘记删掉freopen…话说没删freopen竟然是RE…详细来说是killed…这个以后要注意。

代码部分

下面是第一题的线段树代码：(中间出错的地方已经标出，还练了一下English[chinglish]…)

//深夜线段树？有点zuo...
#include<bits/stdc++.h>
using namespace std;
const int maxn=100001;
long long a[maxn],k;
int n,m,x,y;
struct segtreenode
{
  long long sumv[maxn<<2],add[maxn<<2];
  inline void pushup(int o)
  {
    sumv[o]=sumv[o<<1]+sumv[o<<1|1];
  }
  void build(int o,int l,int r)
  {
    if(l==r){sumv[o]=a[l];return;}
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o);//forget pushup
  }
  inline void pushdown(int o,int l,int r)
  {
    if(!add[o])return;
    int mid=(l+r)>>1;
    sumv[o<<1]+=add[o]*(mid-l+1);add[o<<1]+=add[o];
    sumv[o<<1|1]+=add[o]*(r-mid);add[o<<1|1]+=add[o];
    add[o]=0;//forget clear the lazy tag
    //pushup(o);//pushup by mistake
  }
  inline void addsum(int o,int l,int r,int s,int t,long long p)
  {
    if(l>=s&&r<=t){sumv[o]+=p*(r-l+1);add[o]+=p;return;}
    int mid=(l+r)>>1;
    pushdown(o,l,r);//forget pushdown
    if(mid>=s)addsum(o<<1,l,mid,s,t,p);
    if(mid<t)addsum(o<<1|1,mid+1,r,s,t,p);
    pushup(o);
  }
   long long querysum(int o,int l,int r,int s,int t)
  {
    if(l>=s&&r<=t)return sumv[o];
    long long ans=0;
    int mid=(l+r)>>1;
    if(add[o])pushdown(o,l,r);//forget to judge if the lazy tag is 0
    if(mid>=s)ans+=querysum(o<<1,l,mid,s,t);
    if(mid<t)ans+=querysum(o<<1|1,mid+1,r,s,t);
    return ans;
  }
}segtree;
int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)
    scanf("%lld",&a[i]);
  segtree.build(1,1,n);
  while(m--)
  {
    scanf("%d",&x);
    if(x==1)
    {
      scanf("%d%d%lld",&x,&y,&k);
      segtree.addsum(1,1,n,x,y,k);
    }
    else
    {
      scanf("%d%d",&x,&y);
      printf("%lld\n",segtree.querysum(1,1,n,x,y));
    }
  }
  return 0;
}

然后是第二次写的线段树2代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100001;
int n,m,p;
long long k,a[maxn];
struct sgt
{
  long long sumv[maxn<<2],add[maxn<<2],mul[maxn<<2];
  inline void pushup(int o)
  {
    sumv[o]=sumv[o<<1]+sumv[o<<1|1];
  }
  void build(int o,int l,int r)
  {
    add[o]=0;mul[o]=1;
    if(l==r){sumv[o]=a[l];return;}
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o);
  }
  inline void pushdown(int o,int l,int r)
  {
    if(add[o]==0&&mul[o]==1)return;
    int mid=(l+r)>>1;
    sumv[o<<1]*=mul[o];sumv[o<<1]+=add[o]*(mid-l+1);sumv[o<<1]%=p;
    //forget to mul (mid-l+1)
    add[o<<1]*=mul[o];add[o<<1]+=add[o];add[o<<1]%=p;
    mul[o<<1]*=mul[o];mul[o<<1]%=p;
    sumv[o<<1|1]*=mul[o];sumv[o<<1|1]+=add[o]*(r-mid);sumv[o<<1|1]%=p;
    add[o<<1|1]*=mul[o];add[o<<1|1]+=add[o];add[o<<1|1]%=p;
    mul[o<<1|1]*=mul[o];mul[o<<1|1]%=p;
    add[o]=0;mul[o]=1;
  }
  inline void update(int o,int l,int r,int s,int t,long long addd,long long mull)
  {
    if(l>=s&&r<=t)
    {
      sumv[o]*=mull;sumv[o]+=addd*(r-l+1);sumv[o]%=p;
      add[o]*=mull;add[o]+=addd;add[o]%=p;
      mul[o]*=mull;mul[o]%=p;
      return;
    }
    int mid=(l+r)>>1;
    pushdown(o,l,r);//forget pushdown
    if(mid>=s)update(o<<1,l,mid,s,t,addd,mull);
    if(mid<t)update(o<<1|1,mid+1,r,s,t,addd,mull);
    pushup(o);
  }
  inline long long query(int o,int l,int r,int s,int t)
  {
    if(l>=s&&r<=t)return sumv[o];
    long long ans=0;
    int mid=(l+r)>>1;
    pushdown(o,l,r);
    if(mid>=s)ans+=query(o<<1,l,mid,s,t);
    if(mid<t)ans+=query(o<<1|1,mid+1,r,s,t);
    return ans%p;
  }
}segtree;
int main()
{
  int x,y;
  scanf("%d%d%d",&n,&m,&p);
  for(int i=1;i<=n;i++)
  {
    scanf("%lld",&a[i]);
  }
  segtree.build(1,1,n);
  while(m--)
  {
    scanf("%d",&x);
    if(x==1)
    {
      scanf("%d%d%lld",&x,&y,&k);
      segtree.update(1,1,n,x,y,0,k);
    }
    else if(x==2)
    {
      scanf("%d%d%lld",&x,&y,&k);
      segtree.update(1,1,n,x,y,k,1);
    }
    else 
    {
      scanf("%d%d",&x,&y);
      printf("%lld\n",segtree.query(1,1,n,x,y));
    }
  }
  return 0;
}