题解 |K题题解

板子题，维护一个二维差分数组，之后套线段树的板子就能过了

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000007
#define ll long long
int mod=1e9+7;
unsigned ll n,m,a[MAXN],b[MAXN],c[MAXN],ans[MAXN<<2],tag[MAXN<<2];
inline ll ls(ll x)
{
    return x<<1;
}
inline ll rs(ll x)
{
    return x<<1|1;
}
inline void push_up(ll p)
{
    ans[p]=(ans[ls(p)]+ans[rs(p)])%mod;
}
void build(ll p,ll l,ll r)
{
    tag[p]=0;
    if(l==r){ans[p]=a[l]%mod;return ;}
    ll mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
} 
inline void f(ll p,ll l,ll r,ll k)
{
    tag[p]=(tag[p]+k)%mod;
    ans[p]=(ans[p]+(k*(r-l+1))%mod)%mod;
}
inline void push_down(ll p,ll l,ll r)
{
    ll mid=(l+r)>>1;
    f(ls(p),l,mid,tag[p]);
    f(rs(p),mid+1,r,tag[p]);
    tag[p]=0;
}
inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k)
{
    if(nl<=l&&r<=nr)
    {
        ans[p]=(ans[p]+(k*(r-l+1))%mod)%mod;
        tag[p]=(tag[p]+k)%mod;
        return ;
    }
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
    if(nr>mid)update(nl,nr,mid+1,r,rs(p),k);
    push_up(p);
}
inline void update2(ll nn,ll l,ll r,ll p,ll k)
{
    if(l==r&&l==nn){
        ans[p]=(ans[p]+k)%mod;
        return;
    }
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nn<=mid)update2(nn,l,mid,ls(p),k);
    if(nn>mid)update2(nn,mid+1,r,rs(p),k);
    push_up(p);
}
ll query2(ll nn,ll l,ll r,ll p)
{
    ll res=0;
    if(r==l&&l==nn)return ans[p];
    ll mid=(l+r)>>1;
    push_down(p,l,r);
    if(nn<=mid)res=(res+query2(nn,l,mid,ls(p))%mod)%mod;
    if(nn>mid) res=(res+query2(nn,mid+1,r,rs(p))%mod)%mod;
    return res%mod;
}
void solve(){
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<=n;i++)a[i]=0;
    build(1,1,n);
    while(m--){
        ll op,x;
        scanf("%lld%lld",&op,&x);
        if(op==1){
           update2(x,1,n,1,1);
        }
        else{
            update2(x,1,n,1,1);
            if(x+1<=n)update(x+1,n,1,n,1,2);
        }
    }
    for(int i=1;i<=n;i++)a[i]=query2(i,1,n,1)%mod;

    for(int i=1;i<=n;i++){
        b[i]=(b[i-1]+a[i])%mod;
        c[i]=(c[i-1]+b[i])%mod;
        printf("%lld ",c[i]);
    }
    printf("\n");
}
int main(){
    ll t;
    cin>>t;
    while(t--)solve();
    return 0;
}