常见结论
题意：（区间移位问题）要求将整个序列左移/右移若干个位置，例如，原序列为 \(A=(a_1, a_2, \dots, a_n)\) ，右移 \(x\) 位后变为 \(A=(a_{x+1}, a_{x+2}, \dots, a_n,a_1,a_2,\dots, a_x)\) 。
区间的端点只是一个数字，即使被改变了，通过一定的转换也能够还原，所以我们可以 \(\mathcal O(1)\) 解决这一问题。为了方便计算，我们规定下标从 \(0\) 开始，即整个线段的区间为 \([0, n)\) ，随后，使用一个偏移量 shift 记录。使用 shift = (shift + x) % n; 更新偏移量；此后的区间查询/修改前，再将坐标偏移回去即可，下方代码使用区间修改作为示例。
cin >> l >> r >> x;
l--; // 坐标修改为 0 开始
r--;
l = (l + shift) % n; // 偏移
r = (r + shift) % n;
if (l > r) { // 区间分离则分别操作segt.modify(l, n - 1, x);segt.modify(0, r, x);
} else {segt.modify(l, r, x);
}
常见例题
题意：（带修莫队 - 维护队列）要求能够处理以下操作：
'Q' l r：询问区间 \([l,r]\) 有几个颜色；'R' idx w：将下标 \(\tt idx\) 的颜色修改为 \(\tt w\) 。
输入格式为：第一行 \(n\) 和 \(q\ (1\le n, q\le 133333)\) 分别代表区间长度和操作数量；第二行 \(n\) 个整数 \(a_1,a_2\dots,a_n\ (1\le a_i\le 10^6)\) 代表初始颜色；随后 \(q\) 行为具体操作。
const int N = 1e6 + 7;
signed main() {int n, q;cin >> n >> q;vector<int> w(n + 1);for (int i = 1; i <= n; i++) {cin >> w[i];}vector<array<int, 4>> query = {{}}; // {左区间, 右区间, 累计修改次数, 下标}vector<array<int, 2>> modify = {{}}; // {修改的值, 修改的元素下标}for (int i = 1; i <= q; i++) {char op;cin >> op;if (op == 'Q') {int l, r;cin >> l >> r;query.push_back({l, r, (int)modify.size() - 1, (int)query.size()});} else {int idx, w;cin >> idx >> w;modify.push_back({w, idx});}}int Knum = 2154; // 计算块长vector<int> K(n + 1);for (int i = 1; i <= n; i++) { // 固定块长K[i] = (i - 1) / Knum + 1;}sort(query.begin() + 1, query.end(), [&](auto x, auto y) {if (K[x[0]] != K[y[0]]) return x[0] < y[0];if (K[x[1]] != K[y[1]]) return x[1] < y[1];return x[3] < y[3];});int l = 1, r = 0, val = 0;int t = 0; // 累计修改次数vector<int> ans(query.size()), cnt(N);for (int i = 1; i < query.size(); i++) {auto [ql, qr, qt, id] = query[i];auto add = [&](int x) -> void {if (cnt[x] == 0) ++ val;++ cnt[x];};auto del = [&](int x) -> void {-- cnt[x];if (cnt[x] == 0) -- val;};auto time = [&](int x, int l, int r) -> void {if (l <= modify[x][1] && modify[x][1] <= r) { //当修改的位置在询问期间内部时才会改变num的值del(w[modify[x][1]]);add(modify[x][0]);}swap(w[modify[x][1]], modify[x][0]); //直接交换修改数组的值与原始值，减少额外的数组开销，且方便复原};while (l > ql) add(w[--l]);while (r < qr) add(w[++r]);while (l < ql) del(w[l++]);while (r > qr) del(w[r--]);while (t < qt) time(++t, ql, qr);while (t > qt) time(t--, ql, qr);ans[id] = val;}for (int i = 1; i < ans.size(); i++) {cout << ans[i] << endl;}
}