更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19434487

大意

在 $i$ 的地方会向后跳 $a[i]$ 次，然后带修询问你最少需要跳几次能跳出这个长度为 $n$ 的地方

思路

首先我们发现每个点的弹出，会影响下一个点 $i + a[i]$，也就是说我们如果暴力的考虑的话，就只需修改的时候向后一直跳。

但是这样很劣啊，我们可以考虑用分块处理这个问题，我们可以考虑倒序处理，当后面的点处理过后，你就可以把前面的点从后面转移。

于是我们只需要记录 $cnt[i]$ 次才能跳出第 $i$ 块，以及 $nxt[i]$ 弹出块后落到的第一个位置。

那么我们就可以分块直接处理这个玩意，当一个点被修改的时候，只会影响这个点所在的块，直接重新对这个块建一遍即可。

代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

const int MAXN = 2 * 1e5 + 5;
int n, m, B, sz = 0;
int a[MAXN], cnt[MAXN], nxt[MAXN];

inline void build(int x){
    int l = x * B + 1;
    int r = min(n, (x + 1) * B);
    for(int i = r; i >= l; i--){
        int nx = i + a[i];
        if(nx > n){
            cnt[i] = 1;
            nxt[i] = -1;
        }
        else if(nx > r){
            cnt[i] = 1;
            nxt[i] = nx;
        }
        else{
            cnt[i] = 1 + cnt[nx];
            nxt[i] = nxt[nx];
        }
    }
}

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

	cin >> n;

    B = sqrt(n);
    sz = (n - 1) / B + 1;

    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    for(int i = 0; i < sz; i++){
        build(i);
    }

    cin >> m;
    while(m --){
        int op; cin >> op;
        if(op == 1){
            int x; cin >> x;
            x ++;
            int res = 0;
            while(x != -1){
                res += cnt[x];
                x = nxt[x];
            }
            cout << res << '\n';
        }
        else{
            int x, y; cin >> x >> y;
            x ++;
            a[x] = y;
            int p = (x - 1) / B;
            build(p);
        }
    }

    return 0;
}

更好的阅读体验:https://www.cnblogs.com/To-Carpe-Diem/p/19434503

大意

给出一段区间的颜色，区间询问，求某段区间两个点颜色相同的概率(用分数表示)

思路

发现询问和查询隔离，考虑莫队。

然后我们的修改是不是只需要考虑多一个或者少一个点，那么这个很好办啊。

如果记当前答案(分子)是 $\text{ans}$，则在加入点的时候，$\text{ans}$ 先加上原来这个新加入点颜色的贡献，如果是删点的花就先把删掉的这个点的贡献减去，$\text{ans}$ 的贡献就减去减掉后的这个贡献。

然后注意 long long 即可。

代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

#define int long long
const int MAXN = 50005;
int B = 0;
struct node{
    int l, r, id;
    bool operator < (const node &t) const{
        if(l / B == t.l / B) return r < t.r;
        return l / B < t.l / B;
    }
} q[MAXN];
int cnt[MAXN], col[MAXN];
int n, m, ans1[MAXN], ans2[MAXN], A, BB;

int gcd(int a, int b){
    return (b == 0) ? a : gcd(b, a % b);
}

void add(int x){
    A += cnt[x];
    cnt[x] ++;
}

void del(int x){
    cnt[x] --;
    A -= cnt[x];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    
    B = sqrt(n);
    
    for(int i = 1;i <= n;i ++){
        cin >> col[i];
    }
    
    for(int i = 1;i <= m;i ++){
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    
    sort(q + 1, q + m + 1);
    
    for(int l = 1, r = 0, i = 1;i <= m;i ++){
        if(q[i].l == q[i].r){
            ans1[q[i].id] = 0;
            ans2[q[i].id] = 1;
            continue;
        }
        while(l > q[i].l) add(col[-- l]);
        while(l < q[i].l) del(col[l ++]);
        while(r < q[i].r) add(col[++ r]);
        while(r > q[i].r) del(col[r --]);
        BB = (r - l + 1) * (r - l) / 2;
        int g = gcd(A, BB);
        ans1[q[i].id] = A / g;
        ans2[q[i].id] = BB / g;
    }
    
    for(int i = 1;i <= m;i ++){
        cout << ans1[i] << '/' << ans2[i] << '\n';
    }
    return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19555785

大意

求 $[l, r]$ 内有多少数，满足 $本身 \mod 数位和 = 0$ ，则记一次贡献。

思路

不难发现最大为 $10 ^ 9$，发挥人类智慧！

分块打表，以 $10 ^ 6$ 为块的大小，分出 $1000$ 个块。

于是你只需要计算 $f(x) = [1, x]$ 内合法的，答案为：

$$f(r) - f(l - 1)$$

完结。

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19555727

大意

求一段区间 $[l, r]$ 里面的 $(i, j)$ 二元组，满足 $s[i] \oplus s[i + 1] \cdots \oplus s[j] = k$。

思路

首先，我们不难想到这个异或的性质可以扩展，然后，我们可以考虑用莫队求解此题。

对于询问分块，那我们只需要考虑加入一个点与删除一个点对 $ans$ 的贡献。

由于异或具有前缀和的性质，即为异或和，那么我们的 $s[i] \oplus s[i + 1] \cdots \oplus s[j] = s[j] \oplus s[i - 1] = k$，也就是说，我们的点 $s[j] = s[i - 1] \oplus k$，于是我们对于点 $i$ 来说，加入这个点就会对 $s[i - 1] \oplus k$ 的位置的值产生贡献，使得 $s[i - 1] \oplus s[j] = k$,那么这个题就和 P1494 [国家集训队] 小 Z 的袜子(https://www.cnblogs.com/To-Carpe-Diem/p/19434503) 一样了。

代码

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

const int MAXN = 1e5 + 5;
const int MAXV = (1 << 20) + 5;
int n, m, k, b;
long long sum = 0;
int s[MAXN], a[MAXN];
int cnt[MAXV];
long long ans[MAXN];

struct node{
	int l, r, id;
}q[MAXN];

bool cmp(node x, node y){
	if(x.l / b != y.l / b){
		return x.l < y.l;
	}
	return (x.l / b) % 2 == 1 ? x.r < y.r : x.r > y.r;
}

void add(int x){
	sum += cnt[x ^ k];
	cnt[x] ++;
}

void del(int x){
	cnt[x] --;
	sum -= cnt[x ^ k];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k;

	b = sqrt(n);

	for(int i = 1;i <= n;i ++){
		cin >> a[i];
		s[i] = s[i - 1] ^ a[i];
	}

	for(int i = 1;i <= m;i ++){
		int l, r; cin >> l >> r;
		q[i] = {l, r, i};
	}

	sort(q + 1, q + m + 1, cmp);

	int l = 1, r = 0;

	cnt[0] = 1;

	for(int i = 1;i <= m;i ++){
		while(l > q[i].l) add(s[-- l - 1]);
		while(l < q[i].l) del(s[l ++ - 1]);
		while(r < q[i].r) add(s[++ r]);
		while(r > q[i].r) del(s[r --]);
		ans[q[i].id] = sum;
	}

	for(int i = 1;i <= m;i ++){
		cout << ans[i] << '\n';
	}

	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19527165

大意

求最小值的石子合并，$n \le 40000$。

思路

利用 GarsiaWachs 算法。

在序列中找到第一个满足 $a_{i-1} \le a_{i+1}$ 的三元组 $(a_{i-1}, a_i, a_{i+1})$。

合并 $a_{i-1}$ 和 $a_i$，得分增加 $W = a_{i-1} + a_i$。

从当前位置向左寻找第一个大于 $W$ 的位置，将 $W$ 插入到其后面。

重复上述过程，直到只剩下一堆石子。

代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#define int long long
int n;
int ans = 0;
vector<int> a;

void merge(int k){
	int tmp = a[k - 1] + a[k];
	ans += tmp;
	a.erase(a.begin() + k - 1);
	a.erase(a.begin() + k - 1);
	int pos = -1;
	for(int i = k - 2;i >= 0;i --){
		if(a[i] >= tmp){
			pos = i;
			break;
		}
	}
	a.insert(a.begin() + pos + 1, tmp);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i ++){
		int val; cin >> val;
		a.push_back(val);
	}
	while(a.size() > 1){
		int k = a.size() - 1;
		for(int i = 1;i < (int)a.size() - 1;i ++){
			if(a[i - 1] <= a[i + 1]){
				k = i;
				break;
			}
		}
		merge(k);
	}
	cout << ans << '\n';
	return 0;
}

更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19527051

大意

石子合并，$n = 1000$，求最小值。

思路

首先 $\mathcal{O}(n ^ 3)$ 的复杂度肯定是不可以的。

我们考虑优化，不难发现，对于 $w(i, j)$ 满足：

$$w(i, j - 1) + w(i + 1, j) \le w(i, j) + w(i - 1,j - 1)$$

所以这个 $w$ 满足四边形不等式，故 $f$ 也满足。

然后我们定义这个 $G(k) = f(i, k) + f(k + 1, j)$，所以 $G(k)$ 为凹函数，则最小值在一个区间内取得，我们可以记录 $[i, j]$ 区间的决策点，这样你在算第 $[i, j]$ 的时候，区间 DP 的点 $k$ 就可以在 $s[i][j - 1]$ 和 $s[i + 1][j]$ 之间取得。

代码

#include<iostream>
using namespace std;

#define int long long
const int MAXN = 2005;
int n;
int a[MAXN];
int dp[MAXN][MAXN];
int sum[MAXN];
int s[MAXN][MAXN];

signed main(){

	cin >> n;

	for(int i = 1;i <= n;i ++){
		cin >> a[i];
		a[i + n] = a[i];
		sum[i] = sum[i - 1] + a[i];
	}

	for(int i = n + 1;i <= (n << 1);i ++){
		sum[i] = sum[i - 1] + a[i];
	}

	for(int i = 1;i <= (n << 1);i ++){
		s[i][i] = i;
	}

	for(int len = 2;len <= n;len ++){
		for(int i = 1;i + len - 1 <= (n << 1);i ++){
			int j = i + len - 1;
			dp[i][j] = 1e9;
			int L = s[i][j - 1];
			int R = s[i + 1][j];
			for(int k = L;k <= R;k ++){
				int cnt = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
				if(cnt < dp[i][j]){
					dp[i][j] = cnt;
					s[i][j] = k;
				}
			}
		}
	}

	int ans = 1e9;

	for(int i = 1;i <= n;i ++){
		ans = min(ans, dp[i][i + n - 1]);
	}

	cout << ans << '\n';
	return 0;
}