wp_11_27

[toc]

数组构造

C_Meximum_Array_2.cpp

杂

欧拉筛和最大公约数

#include <iostream>
#include <vector>
#include <numeric> // 用于 std::gcd (C++17), 但手写gcd更通用

using namespace std;

// ================= 配置区域 =================
const int MAXN = 1000005; // 筛的范围，根据题目要求修改 (通常 1e6 到 1e7)
// ===========================================

// --- 变量定义 ---
// primes: 用来存所有的质数
// min_prime: min_prime[i] 表示数字 i 的最小质因子 (可选，用于快速分解质因数)
// phi: 欧拉函数 phi[i] 表示 1...i 中与 i 互质的数的个数
// is_prime: 标记数组，true 表示是质数，false 表示是合数 (或者是 bool not_prime)
vector<int> primes; 
int min_prime[MAXN]; 
int phi[MAXN];       
bool is_not_prime[MAXN]; // 为了防止 bool 初始化陷阱，通常用 "is_not_prime" (默认为false，即默认都是质数)

// ==========================================================
// 核心模块 1: 欧拉筛 (Linear Sieve)
// 时间复杂度: O(N) - 绝对线性，不随数据波动
// ==========================================================
void euler_sieve(int n) {
    // 1. 初始化
    // 0 和 1 既不是质数也不是合数，但在代码逻辑中要把它们标记掉
    is_not_prime[0] = is_not_prime[1] = true;
    phi[1] = 1; // 1 的欧拉函数特例为 1

    // 2. 开始遍历每一个数
    for (int i = 2; i <= n; i++) {
        // 如果当前数没有被标记过，说明它是质数
        if (!is_not_prime[i]) {
            primes.push_back(i); // 把它加入质数列表
            phi[i] = i - 1;      // 质数 p 的欧拉函数是 p-1
            min_prime[i] = i;    // 质数的最小质因子是它自己
        }

        // 3. 用当前已有的质数去筛掉合数
        // j 是 primes 数组的下标，primes[j] 是当前的质数
        for (int j = 0; j < primes.size(); j++) {
            // 计算要筛掉的合数：当前数 i * 质数 primes[j]
            // 如果乘积超过了范围，直接停止
            if (i * primes[j] > n) break;

            // 标记这个合数
            int composite_num = i * primes[j];
            is_not_prime[composite_num] = true;
            min_prime[composite_num] = primes[j]; // 记录它的最小质因子

            // === [核心逻辑] 欧拉筛的灵魂 ===
            // 如果 i 能够被当前的质数 primes[j] 整除
            // 说明 i 已经被 primes[j] 筛过了（或者包含这个因子）
            // 那么 i * primes[j+1] 这个合数，应该由 primes[j] 后面更大的质数来筛吗？
            // 不！为了保证线性复杂度，每个数只能被它"最小"的质因子筛掉。
            // 因为 primes[j] 是 i 的因子，所以 primes[j] 也一定是 (i * primes[j+1]) 的最小因子。
            // 如果我们不 break，继续用更大的质数筛，就会导致重复筛选，退化成 O(N log log N)。
            if (i % primes[j] == 0) {
                // 此时更新积性函数 phi 的公式 (特殊情况)
                phi[composite_num] = phi[i] * primes[j];
                break; // 必须立刻跳出循环！
            } else {
                // 如果 i 不能被 primes[j] 整除 (互质情况)
                // phi 的积性性质: phi(a * b) = phi(a) * phi(b)
                phi[composite_num] = phi[i] * (primes[j] - 1);
            }
        }
    }
}

// ==========================================================
// 核心模块 2: 最大公约数 (GCD) & 最小公倍数 (LCM)
// 时间复杂度: O(log(min(a, b)))
// ==========================================================

// 递归写法 (推荐，现代编译器优化后极快)
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 最小公倍数 = (a * b) / gcd(a, b)
// 注意：先除后乘，防止 a * b 直接溢出 long long
long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    return (a / gcd(a, b)) * b;
}

int main() {
    // 优化 I/O
    ios::sync_with_stdio(0); cin.tie(0);

    // 1. 必须先调用筛法预处理
    // 假设题目范围是 1000
    euler_sieve(1000); 

    // --- 用法演示 ---
    
    // 1. 判断是否为质数 O(1)
    int x = 997;
    if (!is_not_prime[x]) {
        cout << x << " is a prime number." << endl;
    }

    // 2. 输出前 10 个质数
    cout << "Top 10 primes: ";
    for(int i = 0; i < 10 && i < primes.size(); i++) {
        cout << primes[i] << " ";
    }
    cout << endl;

    // 3. 查询欧拉函数 (比 x 小且与 x 互质的数的个数)
    // 比如 phi(8) = 4 (即 1, 3, 5, 7)
    cout << "phi(8) = " << phi[8] << endl;

    // 4. GCD / LCM
    cout << "GCD(24, 36) = " << gcd(24, 36) << endl;
    cout << "LCM(24, 36) = " << lcm(24, 36) << endl;

    return 0;
}

#include <iostream>

using namespace std;

// ==========================================
// 1. 配置区域
// ==========================================
using ll = long long; // 使用 long long 防止运算溢出
const int MOD = 1e9 + 7; // 题目通常给定的模数 (必须是质数)

// ==========================================
// 2. 核心算法模版
// ==========================================

// 函数：快速幂 (Binary Exponentiation)
// 作用：快速计算 (base^exp) % MOD
// 复杂度：O(log exp)
ll qpow(ll base, ll exp) {
    ll res = 1;
    while (exp > 0) {
        // 如果指数是奇数，乘上底数
        if (exp & 1) res = res * base % MOD;
        // 底数翻倍，指数减半
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

// 函数：求乘法逆元 (Modular Inverse)
// 作用：求 n 在模 MOD 下的逆元 (相当于求 1/n)
// 原理：费马小定理 -> n^(MOD-2)
// 限制：MOD 必须是质数
ll inv(ll n) {
    return qpow(n, MOD - 2);
}

// ==========================================
// 3. 实际使用演示
// ==========================================

// 封装一个安全的除法函数 (可选，方便调用)
// 计算 (a / b) % MOD
ll div_mod(ll a, ll b) {
    // 核心步骤：
    // 1. 算出 b 的逆元 (inv_b)
    // 2. 这里的 a 可能是非常大的数，也可以是已经取模过的数
    // 3. 结果 = a * inv_b % MOD
    return (a % MOD) * inv(b) % MOD;
}

int main() {
    // 优化输入输出速度
    ios::sync_with_stdio(0); cin.tie(0);

    // --- 场景一：基础验证 ---
    // 我们知道 10 / 2 = 5
    ll a = 10;
    ll b = 2;
    
    cout << "场景一 (10/2):" << endl;
    // 调用逆元逻辑
    // 步骤 A: 算出 b(2) 的逆元
    ll b_inverse = inv(b); 
    // 步骤 B: 计算 a * 逆元
    ll res = a * b_inverse % MOD; 
    
    cout << "10 / 2 (mod 1e9+7) = " << res << endl; // 输出 5
    cout << "---------------------------" << endl;


    // --- 场景二：ACM 常见的大数除法 ---
    // 假设题目要求计算: (10^18) / 5  % (1e9+7)
    // 注意：这里的 10^18 已经大到 long long 存不下了，
    // 通常 a 是在之前的步骤里通过不断取模算出来的。
    
    cout << "场景二 (大数除法):" << endl;
    
    // 模拟 a 非常大的情况，假设 a 经过之前的计算已经是取模后的结果了
    // 假设真实的 A = 1000000000000000005 (很大)
    // 我们手头只有 A % MOD 的值
    ll huge_A = 1000000000000000005LL; 
    ll A_mod = huge_A % MOD; // 此时 A_mod 只是一个较小的数
    ll B = 5;

    // 错误演示：直接除
    // cout << A_mod / B << endl; // 绝对错误！取模后的数变小了，不能直接除 B

    // 正确演示：乘逆元
    // 这一步本质是： (A * (1/B)) % MOD
    ll ans = A_mod * inv(B) % MOD;

    cout << "结果: " << ans << endl;

    // 验证一下：
    // 真实结果应该是 huge_A / 5 = 200000000000000001
    // 我们看看 200000000000000001 % MOD 是多少
    cout << "验证: " << (huge_A / B) % MOD << endl;
    
    return 0;
}

stl

// ==========================================
// 1. 万能头与加速 (必写!)
// ==========================================
#include <bits/stdc++.h> 
using namespace std;

int main() {
    // 关流加速 (防止 cin/cout 超时)
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0); 

    // ==========================================
    // 2. vector (动态数组) - 真的很常用
    // ==========================================
    vector<int> v;
    v.push_back(1);      // 尾部插入
    v.pop_back();        // 尾部删除
    v.size();            // 获取长度
    v.clear();           // 清空
    v.empty();           // 判空 (true为空)
    
    // 排序 (默认从小到大)
    sort(v.begin(), v.end()); 
    // 去重 (必须先排序!)
    v.erase(unique(v.begin(), v.end()), v.end()); 

    // ==========================================
    // 3. string (字符串) - 别再看成子序列了!
    // ==========================================
    string s = "abcdef";
    // 截取: s.substr(开始下标, 长度)
    string sub = s.substr(1, 3); // "bcd"
    
    // 查找: s.find("子串") -> 返回下标，找不到返回 string::npos
    if (s.find("cd") != string::npos) { 
        // 找到了
    }
    
    // 字典序比较: 直接用 > < ==
    string s1 = "apple", s2 = "banana";
    if (s1 < s2) {} // true

    // ==========================================
    // 4. sort 与 自定义比较 (结构体排序必备)
    // ==========================================
    struct Node { int x, y; };
    vector<Node> a;
    
    // 规则: x 从小到大排; 如果 x 一样，y 从大到小排
    sort(a.begin(), a.end(), [&](Node n1, Node n2) {
        if (n1.x != n2.x) return n1.x < n2.x; 
        return n1.y > n2.y; 
    });

    // ==========================================
    // 5. 二分查找 (神器! 必须背! 数组必须有序!)
    // ==========================================
    vector<int> nums = {1, 3, 5, 7, 9};
    // lower_bound: 第一个 >= k 的位置
    // upper_bound: 第一个 > k 的位置
    int k = 5;
    int pos1 = lower_bound(nums.begin(), nums.end(), k) - nums.begin(); // 返回下标
    int pos2 = upper_bound(nums.begin(), nums.end(), k) - nums.begin(); 
    
    // 如果找不到，返回值等于 nums.size()

    // ==========================================
    // 6. map (键值对) & set (自动排序去重)
    // ==========================================
    map<string, int> mp;
    mp["apple"] = 1;
    // 查找键是否存在
    if (mp.count("apple")) {} // 1存在, 0不存在
    // 遍历 map
    for (auto p : mp) {
        // p.first 是 key, p.second 是 value
    }

    set<int> st; // 自动从小到大排序，不重复
    st.insert(5);
    st.erase(5);
    // set 的二分查找要用自带的，否则慢死
    auto it = st.lower_bound(3); 

    // ==========================================
    // 7. priority_queue (优先队列 - 贪心/Dijkstra用)
    // ==========================================
    // 默认是大根堆 (最大的在 top)
    priority_queue<int> pq; 
    // 小根堆 (最小的在 top) - 常用!
    priority_queue<int, vector<int>, greater<int>> min_pq; 
    
    pq.push(10);
    int top = pq.top(); // 取队头
    pq.pop(); // 删队头

    // ==========================================
    // 8. 数学常用小工具
    // ==========================================
    // 最大公约数 GCD
    int g = __gcd(12, 18); 
    // 最小公倍数 LCM = (a*b) / gcd(a,b)
    
    // 绝对值
    int x = abs(-5);
    
    // 交换
    swap(x, g);
    
    // max/min 找最大最小
    int mx = max(1, 2);
    int mn = min({1, 2, 3, 4}); // 多个数要加 {}

    // 赋值 (慎用 memset 除非初始化为 0 或 -1)
    int arr[100];
    memset(arr, 0, sizeof(arr)); // 全部清零
    memset(arr, -1, sizeof(arr)); // 全部设为 -1
    // 如果要设为极大值 (0x3f3f3f3f 约为 1e9)
    memset(arr, 0x3f, sizeof(arr)); 
    
    // 全排列 (暴力破解用)
    vector<int> p = {1, 2, 3};
    do {
        // 这里处理每一种排列
    } while (next_permutation(p.begin(), p.end()));

    return 0;
}

字符串

#include <bits/stdc++.h>
using namespace std;

int main() {
    // ==========================================
    // 1. 读入带空格的字符串 (整行读入)
    // ==========================================
    string s;
    // cin >> s;         // 遇到空格就停止，不能读句子
    getline(cin, s);     // 读入一整行 (包括空格)! 
    // 注意: 如果前面用了 cin >> n，记得先用 cin.ignore() 吃掉换行符再 getline

    // ==========================================
    // 2. 截取子串 (Substr) - 最常用的功能
    // ==========================================
    // s.substr(开始下标, 截取长度) 
    // 注意: 第二个参数是长度，不是结束下标！
    string sub = s.substr(2, 3); // 从下标2开始，截取3个字符

    // ==========================================
    // 3. 查找 (Find)
    // ==========================================
    string t = "abc";
    int pos = s.find(t); // 查找 t 在 s 中第一次出现的位置
    
    // 必须判断是否找到！
    if (pos != string::npos) {
        // 找到了，pos 是下标
    } else {
        // 没找到
    }
    
    // rfind(): 从右往左找 (找最后一个出现的位置)
    int last_pos = s.rfind(t);

    // ==========================================
    // 4. 数字 <--> 字符串 互转 (神器!)
    // ==========================================
    // A. 字符串 转 数字
    string num_str = "12345";
    int n = stoi(num_str);       // 转 int
    long long ll = stoll(num_str); // 转 long long (防爆int)
    
    // B. 数字 转 字符串
    int x = 996;
    string x_str = to_string(x); // 变成 "996"

    // ==========================================
    // 5. 反转字符串 (判断回文必备)
    // ==========================================
    string s2 = "hello";
    reverse(s2.begin(), s2.end()); // s2 变成了 "olleh"
    
    // 判断回文常用套路:
    string temp = s;
    reverse(temp.begin(), temp.end());
    if (s == temp) { /* 是回文 */ }

    // ==========================================
    // 6. 修改与删除
    // ==========================================
    string S = "hello world";
    // 插入: insert(下标, 字符串)
    S.insert(5, " my"); // "hello my world"
    
    // 删除: erase(开始下标, 删除长度)
    S.erase(5, 3); // 删除 " my"
    
    // 替换: replace(开始下标, 长度, 替换成的内容)
    S.replace(6, 5, "C++"); // 把 world 换成 C++

    // ==========================================
    // 7. 字符判断与大小写转换
    // ==========================================
    char c = 'A';
    
    // 判断类 (返回 true/false)
    if (isdigit(c)) {} // 是数字吗 '0'-'9'
    if (isalpha(c)) {} // 是字母吗 'a'-'z' 或 'A'-'Z'
    if (islower(c)) {} // 是小写吗
    if (isupper(c)) {} // 是大写吗
    
    // 转换类 (注意: 只能转单个字符)
    char low = tolower('A'); // 'a'
    char up = toupper('b');  // 'B'
    
    // 把整个字符串转小写
    for(int i=0; i<s.size(); i++) s[i] = tolower(s[i]);

    // ==========================================
    // 8. 字典序 (Lexicographical Order)
    // ==========================================
    // 字符串可以直接比较大小，比的是字典序
    // "abc" < "abd" (true)
    // "abc" < "abcd" (true, 短的在前)
    // "10" < "2" (true! 字符 '1' < '2') -> 这是一个经典坑点！
    // 只有转换成数字比较才是数值大小，直接比 string 是按字符ASCII码比。

    return 0;
}

string s = "0123456789";

// 1. 最常用的写法：指定起点和长度
// 从下标 2 开始，切 3 个字符
string s1 = s.substr(2, 3); 
// 结果: "234" (下标2, 3, 4) -> 没错，是 "234"，不是 "23"！

// 2. 只填起点：切到末尾
// 从下标 5 开始，一直切到最后
string s2 = s.substr(5); 
// 结果: "56789"

// 3. 常见的坑 (易错点!)
// 很多人以为 s.substr(2, 5) 是从下标2切到下标5... 错！！！
string s3 = s.substr(2, 5);
// 结果: "23456" (从下标2开始，往后数5个字符)

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s = "Hello World";

    // ==========================================
    // 1. 信息与状态 (基础必知)
    // ==========================================
    s.size();       // 获取长度 (常用)
    s.length();     // 和 size() 一模一样
    s.empty();      // 判断是否为空 (true 为空)
    s.clear();      // 清空字符串，变成 ""
    s.front();      // 获取第一个字符，等价于 s[0]
    s.back();       // 获取最后一个字符，等价于 s[s.size()-1]

    // ==========================================
    // 2. 构造与初始化 (快速造串)
    // ==========================================
    string s1(5, 'A');  // 生成 "AAAAA" (想要几个重复字符时超好用！)
    string s2(s, 0, 3); // 拷贝 s 的从下标0开始的3个字符 -> "Hel" (类似 substr 的构造版)

    // ==========================================
    // 3. 查找类 API (侦探功能)
    // ==========================================
    // A. 从左往右找
    // 返回第一次出现的位置下标，找不到返回 string::npos
    int pos1 = s.find("World"); 
    
    // B. 从右往左找 (找最后一个)
    // 比如找文件名后缀 "test.cpp.bak" 里的最后一个 '.'
    int pos2 = s.rfind('.'); 

    // C. 查找“任意一个”字符 (高级用法!)
    // 查找 s 中第一个属于 "aeiou" 的字符的位置 (找元音)
    int pos3 = s.find_first_of("aeiou"); 
    
    // D. 查找“第一个不属于”的字符 (高级用法!)
    // 查找 s 中第一个不是数字的字符
    int pos4 = s.find_first_not_of("0123456789");

    // ==========================================
    // 4. 修改类 API (除了 substr 还有这些!)
    // ==========================================
    // A. 截取 (回顾)
    // s.substr(pos, len);  // 返回新串，原串 s 不变！

    // B. 插入
    // s.insert(pos, "内容");
    s.insert(5, " My");     // 在下标5插入 -> "Hello My World"

    // C. 删除 (慎用，会改变原串下标)
    // s.erase(pos, len);   // 从 pos 开始删 len 个
    s.erase(5, 3);          // 删除 3 个字符

    // D. 替换
    // s.replace(pos, len, "新内容"); 
    // 把下标6开始的5个字符(World)换成"Cpp"
    s.replace(6, 5, "Cpp"); // -> "Hello Cpp"

    // E. 拼接
    s += "!!!";             // 最常用的写法
    s.append(" 123");       // 等同于 +=
    s.push_back('A');       // 在末尾加一个【字符】(只能加字符)
    s.pop_back();           // 删掉末尾一个字符

    // ==========================================
    // 5. 转换类 (数字 <-> 字符串)
    // ==========================================
    // String -> Int/Long Long
    int n = stoi("123");         // 字符串转 int
    long long ll = stoll("1234567890123"); // 字符串转 long long
    double d = stod("3.14");     // 字符串转 double

    // Int/Long Long -> String
    string ns = to_string(123);  // 任意数字转字符串

    // ==========================================
    // 6. 秘密武器：stringstream (空格切割神器)
    // ==========================================
    // 场景：题目给你一行句子 "I love ACM algorithm"，让你把单词一个个取出来
    // 不要自己写 for 循环判断空格！用这个！
    
    string line = "I love ACM algorithm";
    stringstream ss(line); // 把字符串塞进流里
    string word;
    while (ss >> word) {   // 像 cin 一样一个个读，自动跳过空格
        cout << word << endl; 
        // 第一次输出 I，第二次 love，第三次 ACM...
    }

    // ==========================================
    // 7. 配合 algorithm 库的常用操作
    // ==========================================
    // 排序
    sort(s.begin(), s.end()); 
    
    // 反转
    reverse(s.begin(), s.end()); 
    
    // 计数 (数数里面有几个 'A')
    int cnt = count(s.begin(), s.end(), 'A'); 
    
    // 去重 (类似 vector，先排序再 unique)
    auto end_unique = unique(s.begin(), s.end());
    s.erase(end_unique, s.end()); // 必须配合 erase 才能真删掉

    // 大小写转换 (暴力转全小写)
    // transform(开始, 结束, 目标开始, ::tolower);
    transform(s.begin(), s.end(), s.begin(), ::tolower);

    return 0;
}

冰茶鸡鸡

int fa[N]; // 存每个人的“爸爸”

// 初始化: 每个人是自己的爸爸
void init(int n) {
    for (int i = 1; i <= n; i++) fa[i] = i;
}

// 查找 (带路径压缩): 找祖宗
int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]); // 路径压缩，下次找更快
}

// 合并: 把 x 和 y 所在的家族合并
void join(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        fa[rootX] = rootY; // 让 X 的祖宗认 Y 的祖宗为爸爸
    }
}

// 查询: 两个点是否连通
bool isConnected(int x, int y) {
    return find(x) == find(y);
}

图论

• 多人去同一个地方（多起点 -> 单终点）
  • 题目特征：题目给了 $N$ 个人（或者 $N$ 个城市），问：“这 $N$ 个人都要去同一个目的地 $T$ 集合，请问谁离目的地最远/最近？或者所有人走的总路程是多少？”
  • 为什么不能直接做？如果你按照正常的思维：每个人跑一次 Dijkstra，就要跑 $N$ 次。时间复杂度爆炸，绝对超时 (TLE)。反向建边怎么破？
  • 逻辑： “$A$ 走到 $B$” 等价于 “在反向图中，从 $B$ 走到 $A$”。
  • 操作：建反图（所有箭头掉头）。只从目的地 $T$ 出发，在反向图上跑一次 Dijkstra。跑出来的 dist[i]，意思就是 “原图中 $i$ 号点走到目的地 $T$ 的最短距离”。
  • 收益： 跑 $N$ 次变成跑 1 次，秒杀。
• 有去有回（往返最短路）
  • 题目特征：题目问：“邮递员从起点 $1$ 送信到 $N$ 个地方，送完还得回到起点 $1$，求最小的总路程。”或者简单的问：“求 $A$ 到 $B$ 再回到 $A$ 的最短路径。”
  • 反向建边怎么破？去程： 在正向图上跑一次 Dijkstra（起点 $1$），得到 dist_to[i]（从家去别处的距离）。
  • 回程： 在反向图上再跑一次 Dijkstra（还是从起点 $1$ 开始跑！），得到 dist_back[i]。
  • 注意：反向图上从 1 出发到 i 的距离，其实就是原图里 i 回到 1 的距离。
  • 答案： 第 $i$ 个地点的往返总路程 = dist_to[i] + dist_back[i]。

小鸡鸡桥

• 断环为链 (Breaking the Circular Array)
  • 什么时候用？题目特征： 题目说“大家围成一个圈坐着”、“项链上的珠子”、“环形跑道”。
  • 难点： 数组是直的，环是圆的，处理“下标越界”或者“跨过终点回到起点”非常麻烦，容易写全是 Bug。
  • 神操作：复制一遍！ 把原数组 a[1…n] 复制一份接在后面，变成 a[1…2n]。比如原数组是 [1, 2, 3]，新数组变成 [1, 2, 3, 1, 2, 3]。
  • 效果： 环上任意一段长度为 $N$ 的路径，现在都在这个 $2N$ 的直数组里变成了连续的一段。
  • 做法： 以后再也不用 % n 取模了，直接在 1 到 2n 的范围里做滑动窗口或者前缀和。

#include <bits/stdc++.h>
using namespace std;

const int N = 200005; // 注意！因为要复制一遍，数组大小要开 2*N 以上！
int a[N]; // 原数组
int s[N]; // 前缀和数组 (如果题目需要求区间和)

int main() {
    int n;
    cin >> n;

    // ==========================================
    // 核心操作：读入 + 复制 + (可选)前缀和
    // ==========================================
    for (int i = 1; i <= n; i++) {
        cin >> a[i];       // 读入第 i 个数
        a[i + n] = a[i];   // 【断环为链】把第 i 个数复制到 i+n 的位置
    }

    // 现在的数组长这样 (假设 n=3, 数据是 1 2 3):
    // 下标: 1  2  3  4  5  6
    // 数据: 1  2  3  1  2  3
    // 你可以直接在 1 到 2*n 的范围内跑循环，完全不用取模！

    // (可选) 计算前缀和: 用于快速求区间和
    for (int i = 1; i <= 2 * n; i++) {
        s[i] = s[i - 1] + a[i];
    }

    // ==========================================
    // 典型用法：枚举长度为 n 的所有区间
    // ==========================================
    // 比如：找一个长度为 n 的区间，使得区间和最大
    int max_sum = -1e9;
    
    for (int i = 1; i <= n; i++) {
        // 当前区间是: [i, i + n - 1]
        // 这是一个长度为 n 的窗口，涵盖了环上的一种情况
        
        // 利用前缀和快速计算这段的和
        // sum = s[右端点] - s[左端点 - 1]
        int current_sum = s[i + n - 1] - s[i - 1];
        
        max_sum = max(max_sum, current_sum);
    }

    cout << max_sum << endl;
    return 0;
}

速度查询

// 1. 数二进制里有几个 1 (popcount)
int x = 13; // 二进制 1101
int cnt = __builtin_popcount(x); // 结果 3
// 注意：如果是 long long，要用 __builtin_popcountll(x)

// 2. 数二进制末尾有几个 0 (CTZ - Count Trailing Zeros)
// 比如 8 (1000)，末尾有 3 个 0
int z = __builtin_ctz(8); // 结果 3
// 常用技巧：x 的 lowest set bit (最低位的1) 对应的值是 1 << __builtin_ctz(x)

// 3. 数二进制前面有几个 0 (CLZ - Count Leading Zeros)
// 常用技巧：快速算 log2(x) (向下取整)
// 因为 int 是 32 位，所以 log2(x) = 31 - __builtin_clz(x)
int lg = 31 - __builtin_clz(16); // 结果 4

int tree[N]; // 树状数组
int n; // 元素个数

// 1. lowbit (取最低位的1)
int lowbit(int x) { return x & -x; }

// 2. 单点修改：给第 x 个数加上 v (注意是加，不是变成)
void add(int x, int v) {
    for (; x <= n; x += lowbit(x)) tree[x] += v;
}

// 3. 前缀查询：求 1 到 x 的和
int query(int x) {
    int sum = 0;
    for (; x > 0; x -= lowbit(x)) sum += tree[x];
    return sum;
}
// 求区间 [L, R] 的和: query(R) - query(L - 1)

• 点修改 + 区间求和 (PURQ)

  • 这是最基础、最可能出现的类型。操作： 设数组 $A$。A[x] += v求 $\sum_{i=L}^{R} A[i]$
  • 套用公式：修改： 调用 add(x, v)。查询： 调用 query® - query(L - 1)。

• 套路二：区间修改 + 求单点值 (RUPQ)这是最巧妙的类型，用到了差分思想。

  • 核心： 设 $D$ 是 $A$ 的差分数组 ($D[i] = A[i] - A[i-1]$)。对 $A$ 数组求前缀和 $\sum_{i=1}^{x} D[i]$ 就能还原 $A[x]$ 的值。
  • 操作：给 $A$ 数组的区间 $[L, R]$ 上的所有数都加上 $v$。求 $A[x]$ 的值。
  • 套用公式：修改： 对 $D$ 数组进行单点修改：add(L, v); // L 位置增加 vadd(R + 1, -v); // R+1 位置减少 v (抵消后续影响)
  • 查询 $A[x]$ 的值：对 $D$ 数组求前缀和：A[x] = query(x);