C++ – 分块

题目链接：https://vjudge.net/problem/HDU-4027

主要题意：区间开方，区间求和

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 100;
int n, m;
int bl[N];
long long blo;
long long sum[N], s[N];
bool flag[N];
void solve(int x) {
    if(flag[x]) return;
    flag[x] = 1;
    sum[x] = 0;
    for(long long i = (x - 1) * blo + 1; i <= x * blo; i++) {
        s[i] = sqrt(s[i]);                    //数字处理[开方]
        sum[x] += s[i];
        if(s[i] > 1) flag[x] = 0;          //终止点[不等于1]
    }
}
void add(long long l,long long r) {
    for(long long i = l; i <= min(bl[l] * blo, r); i++) {//左端点所属的半块
        sum[bl[l]] -= s[i];
        s[i] = sqrt(s[i]);                  //数字处理[开方]
        sum[bl[l]] += s[i];
    }
    if(bl[l] != bl[r])                    //右端点所属的半块
        for(long long i = (bl[r] - 1) * blo + 1; i <= r; i++) {
            sum[bl[r]] -= s[i];
            s[i] = sqrt(s[i]);          //数字处理[开方]
            sum[bl[r]] += s[i];
        }
    for(long long i = bl[l] + 1; i <= bl[r] - 1; i++) solve(i);  //整块
}
long long query(long long l,long long r) {
    long long ans = 0;
    for(long long i = l; i <= min(bl[l] * blo, r); i++) ans += s[i];
    if(bl[l] != bl[r])
        for(long long i = (bl[r] - 1) * blo + 1; i <= r; i++) ans += s[i];
    for(long long i = bl[l] + 1; i <= bl[r] - 1; i++) ans += sum[i];
    return ans;
}
int main() {
    int cnt = 0;
    while(~scanf("%d", &n)) {
        printf("Case #%d:\n", ++cnt);
        memset(sum, 0, sizeof sum);
        memset(flag, 0, sizeof flag);
        blo = sqrt(n);
        for(long long i = 1; i <= n; i++) scanf("%d", &s[i]);
        for(long long i = 1; i <= n; i++) {
            bl[i] = (i - 1) / blo + 1;
            sum[bl[i]] += s[i];
        }
        scanf("%d", &m);
        for(long long i = 1; i <= m; i++) {
            int oper, l, r;
            scanf("%d %d %d", &oper, &l, &r);
            if(l > r) swap(l, r);
            if(oper == 1) printf("%d\n", query(l, r));
            else add(l, r);
        }
        printf("\n");
    }
    return 0;
}

修改方式

1. 数字操作：一共3个点，表示对数字的操作，原题是sqrt()[开方]。
2. 终止项：一个点，降低时间复杂度关键点，可以打表得到，意思是一个数字经过多次[常数级]操作后都会转化到的一个数。

例子

题目链接：https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/4524.html

数字操作代码：

long long getdf(long long x) {
    int len;
    int arr[19];
    for(len = 0; x != 0; len++) {
        arr[len] = x % 10;
        x /= 10;
    }
    long long sum = 0;
    for(int i = 0; i < len; i++) sum += arr[i];
    return 3 * sum + 1;
}

于是，数字操作处 sqrt() 改为 getdf() ，同时打表得到终止项为13。

PS：坑点是变量别忘了long long。