Thinking problem -- the application of backward order difference

Title Description

Xiaoma is a good one who loves line trees.

Xiaoma's grandfather, Ma ye, was beaten by Xiaoma in the game, so he became angry and decided to give Xiaoma such a data structure problem:

Given an array AA of length nn, the value of each entry at the beginning is 00.

The following two operations are supported, totaling mm operations:

1 lr1lr: add the value of each term of Al ∼ ArAl ∼ Ar to 11.

2 lr2lr: perform all operations with the operation number in [l,r][l,r] once, to ensure that rr is less than the number of the current operation.

After mm operations, you should tell Ma ye what the AA array looks like.

Since the answer may be large, you only need to output the value of each number in array AA in the sense of modulus 109 + 7109 + 7.

Enter a description:

The first row has two numbers, n,mn,m, which respectively represent the array length and the number of operations.
Next mm lines, each line has three numbers of opt,l,ropt,l,r, representing an operation.

Output Description:

Output a total of nn lines, indicating the value of A1 ∼ AnA1 ∼ An after mm operations.

Example 1

input

copy

output

copy

3 3 3 0

Remarks:

For 100% data, 1 ≤ n ≤ 105,1 ≤ m ≤ 1051 ≤ n ≤ 105,1 ≤ m ≤ 105.

First, save all operations, and then reverse order difference can be solved.

In fact, two differences are used, one is used in the actual numerical array, and the other is used in the number of operations (reverse order).

I. why do I have to reverse order? We know that the number of operations is determined by the subsequent operations.

We know that the number of operations in the last operation must be one, and so on, we can get the number of operations in each of the previous operations.

The code + comments are as follows:

//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#pragma GCC optimize(2)
//#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include<sstream>
#include<iterator>
#include<cstring>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<list>
#include<set>

using namespace std;
typedef double dou;
typedef long long ll;
typedef pair<int, int> pii;

#define pai acos(-1.0)
#define M 200005
#define inf 1e18
#define mod 1000000007
#define left k<<1
#define right k<<1|1
#define W(a) while(a)  
#define ms(a,b) memset(a,b,sizeof(a))

struct Data
{
    ll Opt, L, R;
}num[M];//operation

ll n, m, pos, pre;
ll ans[M], cnt[M];//ans Is a differential sequence. cnt Is the number of operations

void init()
{
    ms(cnt, 0);
    ms(ans, 0);
    pos = pre = 0;
    cnt[m] = 1;//We know that the number of last operations must be one
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> num[i].Opt >> num[i].L >> num[i].R;//Save the operation
    }
    init();
    for (int i = m; i >= 1; i--)
    {
        pos += cnt[i];//Differential get operation times
        pos = (pos + mod) % mod;
        if (num[i].Opt == 1)
        {
            ans[num[i].L] += pos;
            ans[num[i].R + 1] -= pos;
        }
        else
        {
            cnt[num[i].R] += pos;
            cnt[num[i].L - 1] -= pos;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        pre += ans[i];
        cout << (pre + mod) % mod<<' ' ;
    }
    return 0;
}

Keywords: PHP less Linker iOS

Added by Fira on Fri, 01 Nov 2019 16:05:34 +0200

Programming VIP