数组范围更新

Question

你有 n 个长度为 0 的数组。您必须执行 2 种类型的 m 命令。

type 1: l r (l ≤ l ≤ r ≤ n) — Increase all elements of the array by one, whose indices belong to the range [l, r].

type 2: l r (1 ≤ l ≤ r ≤ m) — Execute all the commands whose indices are in the range [l, r]. It's guaranteed that r is strictly less than the
enumeration/number of the current command.

输入：

第一行包含整数n和m。接下来的 m 行包含以下格式的命令，在语句中描述：t, l, r，其中 t - 类型数（1 或 2）。

输出：

执行每条命令后打印一个数组a。数字必须用空格分隔。由于数字可能非常大，打印它们模 109 + 7。

限制条件：

1 ≤ n, m ≤ 105

Answer 1

这是codechef的问题，你可以看社论here 这是我的源代码

#include<bits/stdc++.h>
#define mp(x,y) make_pair((x),(y))
#define ll long long int
#define mem(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define MOD (ll)(1e9+7)
#define X first
#define all(a) a.begin(),a.end()
#define Y second
#define f(i,a,b) for(int i=a;i<b;i++)
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

struct query{
    int type,l,r;
};
query q[100005];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        vll a(n+1,0),c(m+1,0);
        ll sum=0;
        for(int i=1;i<=m;i++){
            cin>>q[i].type>>q[i].l>>q[i].r;
        }
        for(int i=m;i>=1;i--){
          //  f(i,1,m+1)cout<<c[i]<<" ";cout<<"\n";
            c[i-1]+=c[i];
            c[i-1] = (c[i-1]+MOD)%MOD;
            if(q[i].type==2){
                c[q[i].r]+=c[i]+1;
                c[q[i].r] = (c[q[i].r]+MOD)%MOD;
                c[q[i].l-1]-=c[i]+1;
                c[q[i].l-1] = (c[q[i].l-1]+MOD)%MOD;
            }
        }
        for(int i=1;i<=m;i++){
            if(q[i].type==1){
                a[q[i].r]+=c[i]+1;
                a[q[i].r] = (a[q[i].r]+MOD)%MOD;
                a[q[i].l-1]-=(c[i]+1);
                a[q[i].l-1] = (a[q[i].l-1]+MOD)%MOD;
            }
        }
        for(int i=n-1;i>=1;i--){
            a[i] = a[i+1]+a[i];
            a[i] = (a[i]+MOD)%MOD;
        }
        f(i,1,n+1)cout<<a[i]<<" ";
        cout<<"\n";
    }
    return 0;
}

数组范围更新

range update on array

arrays

fenwick-tree

segment-tree

输入：

输出：

限制条件：