題目 & 解法

我先附上題目連結 簡單來說，就是區間取餘數 然後這東西可以用線段樹實作

然後問題來了，這種東西不能打 Lazy Tag 做（可以想一下為什麼，解答放文末），所以只能用類似於「區間開根號」的做法 在寫區間開根號的時候，我們用的是區間最大值線段樹，是的，區間最大值

理由很簡單，因為開根號開到最後，一定會朝向$1$收斂 所以只要當前區間的最大值為 $1$ 的時候，就不用繼續向下遞迴最修改了，對吧

同理，我們也可以用類似於這個的做法，一樣是區間最大值線段樹在修改時的終止條件是：當前區間最大值 ≤ 我們想要取模的那個數 這應該算是一種剪枝（吧

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>

#pragma GCC optimize ( "O3" )
#pragma loop_opt ( on )

using namespace std;

#define maxN 200005

int seg[maxN << 2];

void update ( int l, int r, int index, int value, int n ){
    if ( l == r )
        seg[n] += value;
    else{
        int mid = ( l + r ) >> 1, leftSon = n << 1, rightSon = leftSon | 1;
        if ( index <= mid )
            update ( l, mid, index, value, leftSon );
        else
            update ( mid + 1, r, index, value, rightSon );

        seg[n] = max ( seg[leftSon], seg[rightSon] );
    }
}

void modify ( int l, int r, int nowL, int nowR, int value, int n ){
    if ( seg[n] < value )
        return;
    if ( nowL == nowR )
        seg[n] %= value;
    else{
        int mid = ( nowL + nowR ) >> 1, leftSon = n << 1, rightSon = leftSon | 1;
        if ( r <= mid )
            modify ( l, r, nowL, mid, value, leftSon );
        else if ( mid < l )
            modify ( l, r, mid + 1, nowR, value, rightSon );
        else{
            modify ( l, mid, nowL, mid, value, leftSon );
            modify ( mid + 1, r, mid + 1, nowR, value, rightSon );
        }

        seg[n] = max ( seg[leftSon], seg[rightSon] );
    }
}

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );
    cout.tie ( 0 );

    int n, m, type, l, r, x, in;
    cin >> n;
    n--;
    for ( int i = 0 ; i <= n ; i++ ){
        cin >> in;
        update ( 0, n, i, in, 1 );
    }

    cin >> m;
    while ( m-- ){
        cin >> type;
        if ( type == 1 ){
            cin >> l >> r;
            update ( 0, n, r, l, 1 );
        }
        else if ( type == 2 ){
            cin >> l >> r >> x;
            modify ( l, r, 0, n, x, 1 );
        }
        else
            cout << seg[1] << '\n';
    }
}

所以其實這題也不難嘛

為什麼不能打 Lazy Tag？

。。。因為 mod 沒有疊加性啊

證明

然後我來證明一下為什麼這樣做幾乎等同於單點修改的東西會過 因為取 mod 至少會把數字砍掉一半（讀者可以自行想想） 所以總複雜度大約為 $O ( log ( max \lbrace a_i \rbrace ) )$ 左右 （此部分感謝 jd3 學長提供）