HDU 6273 Master of GCD(差分)

試合テーマ:http://acm.hdu.edu.cn/downloads/CCPC2018-Hangzhou-ProblemSet.pdf
                             Problem J. Master of GCD
 
この問題は差分の思想を利用して,1つの区間[l,r]の各要素にxを加えると,arr[l]+x,arr[r+1]−xになる.その後、すべての区間が操作された後、ループで2番目から各値が自分と前の値の和に等しい.
ここの時間の複雑さはO(n)であり、暴力を振るうとO(n 2)であり、越えられないに違いない.

#include 
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define P pair 
const int MAXN = 1e5 + 7;
const ll mod = 998244353;
ll qpow(ll a, ll n)
{
    ll re = 1;
    while(n)
    {
        if(n&1)
            re = (re * a)%mod;
        n >>= 1;
        a = (a * a)%mod;
    }
    return re;
}

int a[MAXN], b[MAXN];

int main()
{
    ios::sync_with_stdio(0);
    int t, n, m;
    cin>>t;
    while(t--)
    {
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        cin>>n>>m;
        int l, r, x;
        while(m--)
        {
            cin>>l>>r>>x;
            if(x == 2)
            {
                a[l]++;
                a[r+1]--;
            }
            else
            {
                b[l]++;
                b[r+1]--;
            }
        }
        ll min1 = a[1], min2 = b[1];
        for(int i = 2; i <= n; i++)
        {
            a[i] += a[i-1];
            b[i] += b[i-1];
            if(a[i]