Good Partitions

Problem Statement

Lawliet has a sequence of numbers of length \( n \), denoted as \( a_1, a_2, \dots, a_n \), and he wants to determine how many good partitions exist. A partition size \( k \) is considered a good partition size if it satisfies \( 1 \leq k \leq n \) and, after dividing the sequence \( a \) into parts by partition size, each resulting sub-sequence is non-decreasing. The partitioning method is as follows:

The sequence \( a \) is divided into \( \lceil \frac{n}{k} \rceil \) parts.
For the \( i \)-th part (\( 1 \leq i \leq \lceil \frac{n}{k} \rceil - 1 \)), the elements are \( a_{(i-1) \times k + 1}, a_{(i-1) \times k + 2}, \dots, a_{i \times k} \). _
For the \( \lceil \frac{n}{k} \rceil \)-th part, the elements are \( a_{(\lceil \frac{n}{k} \rceil - 1) \times k + 1}, \dots, a_n \). Note that the length of the last part may be less than \( k \).

Lawliet finds this problem too simple, so he will make \( q \) modifications. Each modification provides two positive integers \( p \) and \( v \), indicating that the value of \( a_p \) will be changed to \( v \).

Your task is to help Lawliet calculate the number of good partition sizes before any modifications and after each modification.

Input

The first line contains an integer \( T \) (\( 1 \leq T \leq 10 \)), representing the number of test cases. For each test case:

The first line contains two integers \( n \) (\( 1 \leq n \leq 2 \cdot 10^5 \)) and \( q \) (\( 1 \leq q \leq 2 \cdot 10^5 \)), representing the length of the sequence and the number of modifications.
The second line contains \( n \) integers, representing the sequence \( a_1, a_2, \dots, a_n \) (\( 1 \leq a_i \leq 2 \cdot 10^9 \)).
The following \( q \) lines each contain two integers \( p \) (\( 1 \leq p \leq n \)) and \( v \) (\( 1 \leq v \leq 2 \cdot 10^9 \)), indicating that the element at the \( p \)-th position in the sequence will be modified to \( v \).
It is guaranteed that the sum of \( n \) and the sum of \( q \) over all test cases do not exceed \( 2 \cdot 10^5 \), respectively.

Output

For each test case, output \( q + 1 \) lines, representing the number of good partition sizes before any modifications and after each modification.

Solving

分析题目易得出：一个序列的好分隔，必定会使得当arr[i] > arr[i+1]时，arr[i] 与 arr[i+!]不在同一个分割之中，记 idx 为 arr[i] 的下标，则对于这一个点，其可能的有效分割是下标 idx 的所有因数。

故对于所有点及对整个序列的所有有效分割，即为所有这种点的下标的最大公因数的因子数，对于单点修改并求取整个序列GCD的信息维护，我们可以选择使用线段树，其每次调用维护的时间为O(logN)，可以在规定时限内解决问题。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109


#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
const int N = 2e5+10;
vector<int> d(N); 
void pre() // 固定写法，筛出一个数的所有因数数目 O(Nsqrt(N))
{
    for(int i=1;i<=N-10;i++)
    {
        for(int j=1;j*i<=N-10;j++)
        {
            d[i*j]++;
        }
    }
}
struct SegTree
{
    struct Node
    {
        int l,r;
        int gcd;
        Node() : l(0),r(0),gcd(0) {}
        inline int len()
        {
            return r - l + 1;
        }
    }tree[N<<2];
    vector<int> arr;

    void push_up(int p)
    {
        tree[p].gcd = __gcd(tree[ls(p)].gcd,tree[rs(p)].gcd);
    }

    SegTree(vector<int>& _arr) : arr(_arr)
    {
        build(1,1,(int)arr.size()-1);
    }

    void build(int p,int l,int r)
    {
        tree[p].l = l;
        tree[p].r = r;
        if(l == r)
        {
            tree[p].gcd = arr[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(ls(p),l,mid);
        build(rs(p),mid+1,r);
        push_up(p);
    }

    void updateval(int p,int x,int v)
    {
        if(tree[p].l == x and tree[p].r == x)
        {
            tree[p].gcd = v;
            arr[tree[p].l] = v;
            return;
        }
        int mid = (tree[p].l + tree[p].r) >> 1;
        if(x <= mid) updateval(ls(p),x,v);
        else updateval(rs(p),x,v);
        push_up(p);
    }
};
void solve()
{
    int n,q;
    cin >> n >> q;
    vector<int> arr(n+1);
    for(int i=1;i<=n;i++)
    {
        cin >> arr[i];
    }
    vector<int> de(n+1,0);
    for(int i=1;i<=n-1;i++)
    {
        if(arr[i] > arr[i+1]) de[i] = i;
    }
    SegTree seg(de);
    int res = seg.tree[1].gcd;
    if(res == 0) // 此时表示序列单调递减，可以取1~n共n种
    {
        cout << n << endl;
    }
    else cout << d[res] << endl;
    while(q--)
    {
        int x,v;
        cin >> x >> v;
        arr[x] = v; // 修改后判断是否会产生新的间断点
        if(arr[x-1] > arr[x]) seg.updateval(1,x-1,x-1);
        else seg.updateval(1,x-1,0);
        if(arr[x] > arr[x+1] and x + 1 <= n)
        {
            seg.updateval(1,x,x);
        }
        else seg.updateval(1,x,0);

        int res = seg.tree[1].gcd;
        if(res == 0)
        {
            cout << n << endl;
        }
        else cout << d[res] << endl;
    } 
}