牛客练习赛49 D-筱玛爱线段树

筱玛爱线段树

• 分析

  刚开始看着挺懵的。注意到题目的条件
  1.区间加一 2.操作数区间加一
  根据分析，如果某一个类型为2的操作不可能形成一个自环，且只会影响前面的操作。据此，我们可以尝试从后往前做(重点一)，每次求出后面对当前操作的影响，然后接着更新前面的操作。我们建立一棵以操作编号为
  关键字的线段树，如果为类型二操作，明显，就得更新[l,r]的区间，至于要添加上多少操作数，肯定就是求之前的操作对当前点的影响。对于操作1，因为编号比其小的对它无法产生影响，编号比他大的已经算完了，直接加上求出这个操作的次数即可。

• 代码(线段树好啊)

#include<bits/stdc++.h>

#define ls now<<1
#define rs now<<1|1
#define ll long long

using namespace std;

const int N=1e5+10;
const ll mod=1e9+7;

int n,m;
ll s[N<<2],tag[N<<2],d[N];
int l[N],r[N],id[N];

inline void pd(int now,ll l,ll r)
{
    if(!tag[now]) return ;
    ll mid=(l+r)>>1;
    tag[ls]+=tag[now];
    tag[rs]+=tag[now];
    s[ls]+=(mid-l+1)*tag[now];
    s[rs]+=(r-mid)*tag[now];
    s[ls]%=mod;s[rs]%=mod;
    tag[ls]%=mod;tag[rs]%=mod;
    tag[now]=0;
}

inline ll find(int now,ll l,ll r,ll x)
{
    if(l==r) return s[now];
    pd(now,l,r);

    ll mid=(l+r)>>1;
    if(x<=mid) return find(ls,l,mid,x);
    else return find(rs,mid+1,r,x);
}

inline void add(int now,ll l,ll r,ll x,ll y,ll z)
{
    if(l>=x&&r<=y)
    {
        tag[now]+=z;tag[now]%=mod;
        s[now]+=(r-l+1)*z;
        s[now]%=mod;
        return ;
    }

    pd(now,l,r);
    ll mid=(l+r)>>1;
    if(x<=mid) add(ls,l,mid,x,y,z);
    if(mid<y) add(rs,mid+1,r,x,y,z);

    s[now]=s[ls]+s[rs];
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
        scanf("%d%d%d",&id[i],&l[i],&r[i]);

    add(1,1,m,1,m,1);
    for (int i=m;i>=1;i--)
    {
        if(id[i]==1) continue;
        ll ok=find(1,1,m,i);
        add(1,1,m,l[i],r[i],ok);
    }

    for (int i=m;i>=1;i--)
    {
        if(id[i]==2) continue;
        ll ok=find(1,1,m,i);
        d[l[i]]+=ok,d[r[i]+1]-=ok;
    }
    for (int i=1;i<=n;i++) d[i]=((d[i]+d[i-1]+mod)%mod+mod)%mod;

    for (int i=1;i<=n;i++) printf("%lld ",d[i]);

    return 0;
}