Welcome to My Blog!

this is a website

Posted on Edited on

Solution

首先，注意到对于两个数ai,aja_i, a_j，mm的最大值为∣ai−aj∣\left|a_i - a_j\right|，且可以取到。

对于ai,ai+1,⋯ ,aja_i, a_{i + 1}, \cdots, a_j，mm的最大值为gcd⁡(∣ai−ai+1∣,⋯ ,∣aj−1−aj∣)\gcd(\left|a_i - a_{i + 1}\right|, \cdots, \left|a_{j - 1} - a_j\right|)，且可以取到，因为：

  1. mm如果比gcd⁡(∣ai−ai+1∣,⋯ ,∣aj−1−aj∣)\gcd(\left|a_i - a_{i + 1}\right|, \cdots, \left|a_{j - 1} - a_j\right|)大，那么一定存在∣ak−ak+1∣≢0mod  m  ⟺  ak−ak+1≠km(k∈Z)\left|a_k - a_{k + 1}\right| \not\equiv 0\mod m\iff a_k - a_{k + 1}\neq km(k\in\textbf{Z})，矛盾。
  2. m=gcd⁡(∣ai−ai+1∣,⋯ ,∣aj−1−aj∣)m=\gcd(\left|a_i - a_{i + 1}\right|, \cdots, \left|a_{j - 1} - a_j\right|)时，任意两个数ak−ah=(ak−ak+1)+(ak+1−ak+2)+⋯+(ah−1−ah)=(k1+k2+⋯kh−k)ma_k - a_h = (a_k - a_{k + 1}) + (a_{k + 1} - a_{k + 2}) + \cdots + (a_{h - 1} - a_h) = (k_1 + k_2 + \cdots k_{h - k})m，所以满足条件。

根据以上分析，确定区间就可以直接求出mm。这个时候有两种解决方法：

  1. 利用倍增，每个数往后倍增直到m=1m=1，时间复杂度O(nlog⁡nlog⁡max⁡ai)O(n\log n\log \max a_i)。利用st表可以做到O(nlog⁡max⁡ai+nlog⁡n)O(n\log\max a_i + n\log n)。
  2. 利用baka's trick进行双指针：每一时刻都有三个指针：l,r,midl, r, mid，其中mid∈[l,r]mid\in [l, r]，并且每一时刻[l,mid],[l+1,mid],⋯ ,[mid−1,mid][l, mid], [l + 1, mid], \cdots, [mid - 1, mid]的贡献已经处理好。当ll要跨越midmid的时候，将midmid设为rr，并让ll从rr倒序遍历回来，处理好新的[l,mid],[l+1,mid],⋯ ,[mid−1,mid][l, mid], [l + 1, mid], \cdots, [mid - 1, mid]的贡献。通过这样反复横跳，可以实现无删的双指针（只要单调且可加就可以双指针）。由于rr总共动nn次，midmid是单调增加的，也最多总共动nn格，而ll除了本身要动的nn下，最多再把midmid走的路径走一遍，也是只要动O(n)O(n)下。故要计算的次数还是O(n)O(n)的。这样时间复杂度就是O(nlog⁡max⁡ai)O(n\log\max a_i)。

Code

Show Code 
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
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 2e5 + 1;
LL A[N], B[N], rev[N]; int n;
inline LL gcd(LL a, LL b){
    while (b){
        a %= b;
        a ^= b ^= a ^= b;
    }
    return a;
}
signed main(){
    int t; cin >> t;
    while (t--){
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> A[i];
        for (int i = 1; i < n; ++i) B[i] = abs(A[i] - A[i + 1]), rev[i] = 0;
        int l = 1, mid = 0;
        int ans = 1;
        LL sum = 0;
        for (int r = 1; r < n; ++r){
            sum = gcd(sum, B[r]);
            while (l <= mid && gcd(sum, rev[l]) == 1) ++l;
            if (l > mid){ // 超过mid时重新计算
                mid = r, rev[mid] = B[mid];
                for (int i = mid - 1; i >= l; --i){
                    rev[i] = gcd(rev[i + 1], B[i]);
                }
                sum = 0;
            }
            while (l <= mid && gcd(sum, rev[l]) == 1) ++l;
            ans = max(ans, r - l + 2);
        }
        cout << ans << endl;
    }
    return 0;
}

Posted on Edited on

普通BST(Binary Search Tree)：一种二叉树，保证所有节点的值都比左儿子大（如有），且比右儿子小（如有）。这样，这种二叉树的前序遍历就一定是一个递增序列。

在随机情况下，这个数据结构的表现非常好，但是有心人总喜欢卡它，比如说这道题就过不去：

https://www.luogu.com.cn/problem/P3369

Show Code 
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
#include<bits/stdc++.h>
using namespace std;
const int N = 100001, INF = 1e7 + 1;
int rt, son[N][2]/*两个儿子*/, 
        val[N]/*当前节点值*/, 
        cnt[N]/*当前节点个数*/, 
        sz[N]/*当前节点子树内个数*/, 
        tot/*总结点数*/;
inline int newnode(int x){ // 加新点
    val[++tot] = x;
    cnt[tot] = 1;
    sz[tot] = 1;
    return tot;
}
inline void pushup(int x){ // 更新节点信息
    sz[x] = sz[son[x][0]] + sz[son[x][1]] + cnt[x];
}
int Insert(int u, int x){ // 插入节点，值为x
    if (!u) return newnode(x);
    if (val[u] == x) return ++cnt[u], u; // 多个表达式用逗号连接，返回最后一个。
    if (val[u] < x) son[u][1] = Insert(son[u][1], x);
    else son[u][0] = Insert(son[u][0], x);
    return pushup(u), u;
}
void Delete(int u, int x){ // 删除值为x的节点
    if (val[u] == x) --cnt[u];
    else if (val[u] < x) Delete(son[u][1], x);
    else Delete(son[u][0], x);
    return pushup(u);
}
int Rank(int u, int x){ // 查询x是第几大的节点
    if (!u) return 1;
    if (val[u] < x) return sz[son[u][0]] + cnt[u] + Rank(son[u][1], x);
    else if (val[u] == x) return sz[son[u][0]] + 1;
    else return Rank(son[u][0], x);
}
int QueryK(int u, int k){ // 查询排名为k的数
    if (k <= sz[son[u][0]]) return QueryK(son[u][0], k);
    if (k <= sz[son[u][0]] + cnt[u]) return val[u];
    return QueryK(son[u][1], k - sz[son[u][0]] - cnt[u]);
}
signed main(){
    int n; scanf("%d", &n);
    while (n--){
        int opt, x; scanf("%d%d", &opt, &x);
        if (opt == 1) rt = Insert(rt, x);
        else if (opt == 2) Delete(rt, x);
        else if (opt == 3) printf("%d\n", Rank(rt, x));
        else if (opt == 4) printf("%d\n", QueryK(rt, x));
        else if (opt == 5) printf("%d\n", QueryK(rt, Rank(rt, x) - 1));
        else if (opt == 6) printf("%d\n", QueryK(rt, Rank(rt, x + 1)));
    }
    return 0;
}

Posted on Edited on

对拍器（Python, generated by SJTU-DeepSeek）：

Read more »

Posted on Edited on

反复使用deepseek以及一点点人工修改得到一下python代码。

支持界面内加todo，删todo，拖拽排序，tick后自动排序。

Read more »

Posted on Edited on

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"
Read more »
0%