前言

好久沒有發題解了，今天心血來潮來寫一篇吧 今天的內容是 CodeForces Education Round 37 ( Rated for Div.2 )的 pF pF，感覺很難？其實還好， 因為這是 Education

題目

不管，翻譯下題目好了，畢竟原題是英文的 要原題連結的在這

給定一個長度為N的序列，並有兩種輸入要處理：

1. 對區間 $l, r$ 做操作 $D$（等等寫在下面）
2. 查詢區間和

操作 $D$ ：把該數字轉換成此數字的因數個數，例如原先的數字是 $6$ ，則操作後會變成 $4$（ $6$ 的因數有 $\{1, 2, 3, 6\}$，共四個）

解法

嗯。。。區間操作？區間和？ 怎麼看都是線段樹，但是問題是：操作 因為操作要查詢的是因數個數，我想不到更好的做法，所以就直接暴力，但是我只有跑到 $\sqrt{N}$，證明我等等再打

好，我們先觀察一下：

1. 只要數字是 $1$ 或 $2$ 就不用繼續操作下去了，對吧（ $2$ 的因數有 $1, 2$，$1$ 的因數只有 $1$ ，所以這兩個數字怎麼操作之後不會變）
2. 越小的數字出現機率越大，也就是更容易使用，所以我們再建一個表，把用過的數字存起來，如果這個數字沒有計算過再算，不然就直接回傳結果

接著是最後一個問題：該如何處理區間操作 對於處理這種無法打 Lazy Tag 的問題（因為這題就算打 Lazy Tag 還是要做 $K$（需要進行的操作次數）次，所以打 Lazy Tag 並沒有任何意義） 不過有種做法叫找收斂點（終止點）

剛剛有提到，當數字為 $1$ 或 $2$ 進行操作並沒有任何意義，所以可以把此區間到底還有沒有 $\ge 2$ 的數字當作是否繼續進行操作的依據

到這，可能有人想到我之前發的某一題，題目是區間取模，所以紀錄區間最大值，如果有比當前需要操作的$m$還有大的數字才需要繼續進行操作，詳細可以看這篇

不過大概算了一下，這樣需要開到$8\times N$的記憶體，感覺會 MLE 所以我先拿區間和開刀，如果當前區間和 $\ge 2\times range（區間大小）$ 再繼續進行操作 。。。然後我就 WA 了，請想想如果當前區間內元素為 $\{ 1, 1, 1, 3 \}$ 的時候

有夠陰，總和為 $8$ ，乍看之下不需要做操作，但是實際上卻有需要進行修改的數字 所以我只能再開一顆線段樹（ bool的），記錄當前區間是否有數字 $\ge 2$

本來不想要開第二顆線段樹，到頭來還不是開了

code

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

using namespace std;

typedef long long LL;
#define maxN 300005

LL sum[maxN << 2], dp[1000005];
bool used[maxN << 2];
vector < int > prime;
bitset < 1005 > lib;

inline int D ( int n ){
    if ( dp[n] != -1 )
        return dp[n];
    double www = sqrt ( n );
    int ma = www, res = 0, maa = ma + 1;
    for ( int i = 1 ; i < maa ; i++ )
        n % i ? res : res++;

    return dp[n] = res * 2 - ( www == ma ? 1 : 0 );
}

inline void build ( int l, int r, int n ){
    if ( l == r ){
        cin >> sum[n];
        used[n] = ( sum[n] > 2 );
    }
    else{
        int mid = ( l + r ) >> 1, leftSon = n << 1, rightSon = leftSon | 1;
        build ( l, mid, leftSon );
        build ( mid + 1, r, rightSon );

        sum[n] = sum[leftSon] + sum[rightSon];
        used[n] = ( used[leftSon] || used[rightSon] );
    }
}

inline LL query ( int l, int r, int nowL, int nowR, int n ){
    if ( l <= nowL && nowR <= r )
        return sum[n];
    int mid = ( nowL + nowR ) >> 1, leftSon = n << 1, rightSon = leftSon | 1;
    if ( r <= mid )
        return query ( l, r, nowL, mid, leftSon );
    if ( mid < l )
        return query ( l, r, mid + 1, nowR, rightSon );
    return query ( l, r, nowL, mid, leftSon ) + query ( l, r, mid + 1, nowR, rightSon );
}

inline void modify ( int l, int r, int nowL, int nowR, int n ){
    if ( !used[n] )
        return;
    if ( nowL == nowR ){
        sum[n] = D ( sum[n] );
        used[n] = ( sum[n] > 2 );
    }
    else{
        int mid = ( nowL + nowR ) >> 1, leftSon = n << 1, rightSon = leftSon | 1;
        if ( r <= mid )
            modify ( l, r, nowL, mid, leftSon );
        else if ( mid < l )
            modify ( l, r, mid + 1, nowR, rightSon );
        else{
            modify ( l, r, nowL, mid, leftSon );
            modify ( l, r, mid + 1, nowR, rightSon );
        }

        sum[n] = sum[leftSon] + sum[rightSon];
        used[n] = ( used[leftSon] || used[rightSon] );
    }
}

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

    lib[0] = lib[1] = true;
    for ( int i = 2 ; i < 1005 ; i++ ){
        if ( !lib[i] ){
            prime.push_back ( i );
            for ( int j = i << 1 ; j < 1005 ; j += i )
                lib[j] = true;
        }
    }

    memset ( dp, -1, sizeof dp );
    int n, m, type, l, r, stop;
    cin >> n >> m;
    build ( 1, n, 1 );

    while ( m-- ){
        cin >> type >> l >> r;
        if ( type == 1 )
            modify ( l, r, 1, n, 1 );
        else
            cout << query ( l, r, 1, n, 1 ) << '\n';
    }
}

證明（？

接下來來證明一下（也不能算是證明啦）為什麼只需要跑過 $\sqrt{N}$ 的數字就好了 假設現在要進行操作的數字為$N$，且有另外一個數字 $i$ 為 $N$ 的因數 這樣代表說 $\frac{N}{i}$ 也是另外一個$N$的因數對吧，我們在這邊令 $j = \frac{N}{i} \to i \times j = N$ 假設 $i\le j$ 帶入上面的式子，$i^2\le N\to i\le\sqrt{N}$ 故得證

。。。好啦，我感覺我寫的證明不是對的 > < 以上證明僅供參考