CDQ分治（或许叫这个名字吧

CDQ分治（或许叫这个名字吧

CDQ分治+RMQ+异或线段树+01带权字典树
看了一手CDQ分治，大受震撼，想到某场牛客练习赛中一道没写出来的题，就花时间写了一下。

题目链接

#include <bits/stdc++.h>
#define FOR(i, beg, n) for (int i = (beg); i <= n; ++ i)using namespace std;const int N = 2e5 + 5;int tr[N * 14][2], n, tot; // 01 dictionary tree
int gs[N * 14][13], sz[N * 12];
int arr[N], Log2[N], mi[N][18];int xr[524288];//XOR line tree
#define lson u << 1, L, mid
#define rson u << 1 | 1, mid + 1, R
#define LS u << 1
#define RS u << 1 | 1
int build(int u, int L = 1, int R = n) {if (L == R) return xr[u] = arr[L];int mid = L + R >> 1;return xr[u] = build(lson) ^ build(rson);
}
long long answer;
int RMQ(const int &L, const int &R) {int L2_ = Log2[R - L + 1];return min(mi[L][L2_], mi[R + 1 - (1 << L2_)][L2_]);
}
void add(const int &Xor, int now = 0) {for (int i = 12; ~i; -- i) {int v = (1 << i & Xor) > 0;if (!tr[now][v]) tr[now][v] = ++ tot;now = tr[now][v];++ sz[now];// count ++for (int j = 0; j <= i; ++ j) if (1 << j & Xor) ++ gs[now][j];}
}
int ges(const int &Xor, const int &minn, int now = 0) {int ans = 0, fan = 0;for (int i = 12; ~i; -- i) {int mmm = (1 << i & minn), v = ((1 << i & Xor) > 0) ^ (mmm > 0);if (mmm > 0) ans += sz[tr[now][!v]];else {int to = tr[now][!v], Size = sz[to];answer += Size * fan;for (int j = 0; j <= i; ++ j) {if (1 << j & Xor) answer += (1 << j) * (Size - gs[to][j]);else answer += (1 << j) * gs[to][j];}}if (!tr[now][v]) break;else if (!i) ans += sz[tr[now][v]];now = tr[now][v];fan += mmm;}return ans;
}
int ql, qr;
int queryxor(int u = 1, int L = 1, int R = n) {if (ql <= L && R <= qr) return xr[u];int mid = L + R >> 1, a = 0;if (ql <= mid) a = queryxor(lson);if (qr > mid) a = a ^ queryxor(rson);return a;
}
void solve(int L, int R) {if (L == R) return ;int mid = L + R >> 1, lsz = mid - L + 1, rsz = R - mid;solve(L, mid), solve(mid + 1, R);memset(sz, 0, (tot + 1) * 4), memset(tr, 0, (tot + 1) * 8), memset(gs, 0, (tot + 1) * 52);tot = 0;int pus = mid;FOR(i, mid + 1, R) {int v = RMQ(mid + 1, i);while (pus >= L && RMQ(pus, mid) >= v)ql = pus--, qr = mid, add(queryxor());ql = mid + 1, qr = i;answer += ges(queryxor(), v) * v;}memset(sz, 0, (tot + 1) * 4), memset(tr, 0, (tot + 1) * 8), memset(gs, 0, (tot + 1) * 52);tot = 0;pus = mid + 1;for (int i = mid; i >= L; -- i) {int v = RMQ(i, mid);while (pus <= R && RMQ(mid + 1, pus) > v)ql = mid + 1, qr = pus++, add(queryxor());ql = i, qr = mid;answer += ges(queryxor(), v) * v;}
}
signed main() {cin.tie(0), cout.tie(0)->sync_with_stdio(false);cin >> n;FOR(i, 1, n) cin >> arr[i];FOR(i, 2, n) Log2[i] = Log2[i >> 1] + 1;
{// RMQ#define Len nfor (int i = 2; i <= Len; ++ i) Log2[i] = Log2[i >> 1] + 1;for (int i = 1; i <= Len; ++ i) mi[i][0] = arr[i], answer += arr[i];int Len_1 = Len + 1;for (int i = 1, k = 0; i <= Log2[Len]; ++ i, ++ k) {int Mlie = Len_1 - (1 << i), Mlke = 1 << k; for (int j = 0; j <= Mlie; ++ j) mi[j][i] = min(mi[j][k], mi[j + Mlke][k]);}	
}build(1);solve(1, n);return cout << answer << endl, system("pause"), 0;
}