网站开发使用哪些开发语言,WordPress朗读,网站规划建设与管理维护的论文,外贸网站开发 河南P4887 【模板】莫队二次离线#xff08;第十四分块(前体)#xff09;
Solution
简单学习了一下二次离线莫队#xff0c;写了个板子题。
这题直接莫队时间复杂度为O(Cnn)O(Cn\sqrt n)O(Cnn)#xff0c;其中C(14k)C\binom{14}{k}C(k14)#xff0c;显然不太行。
我们…P4887 【模板】莫队二次离线第十四分块(前体)
Solution
简单学习了一下二次离线莫队写了个板子题。
这题直接莫队时间复杂度为O(Cnn)O(Cn\sqrt n)O(Cnn)其中C(14k)C\binom{14}{k}C(k14)显然不太行。
我们考虑当前区间为[l,r][l,r][l,r]右端点增加kkk变为[l,rk][l,rk][l,rk]产生的贡献
令f(x,[l,r])[∑ilrpopcount(xxorai)k]f(x,[l,r])[\sum_{il}^rpopcount(x\;xor\;a_i)k]f(x,[l,r])[∑ilrpopcount(xxorai)k]
则有 Δans\Delta ansΔans
∑ir1rkf(i,[l,i−1])\sum_{ir1}^{rk}f(i,[l,i-1])∑ir1rkf(i,[l,i−1])
∑ir1rkf(i,[1,i−1])−f(i,[1,l−1])\sum_{ir1}^{rk} f(i,[1,i-1])-f(i,[1,l-1])∑ir1rkf(i,[1,i−1])−f(i,[1,l−1])
于是我们可以预处理f(i,[1,i−1])f(i,[1,i-1])f(i,[1,i−1])并且离线求出∑ir1rkf(i,[1,l−1])\sum_{ir1}^{rk}f(i,[1,l-1])∑ir1rkf(i,[1,l−1])。这个可以在O(Cnmn)O(Cnm\sqrt n)O(Cnmn)的时间内完成。
其他端点的移动同理。
总时间复杂度为O(Cnmn)O(Cnm\sqrt n)O(Cnmn)。
Code
const int MX 1 14;
int b[MX], sum[MX], a[MAXN], sz, bnum 0, Cnum 0, n, m, K;
ll s0[MAXN], s1[MAXN], Ans[MAXN];
struct Cnode{ int l, r, x, id; ll ans; } C[MAXN 1];
struct Qnode{ int l, r, id; } Q[MAXN];void Init() {for (int i 0; i MX ; i) if (__builtin_popcount(i) K) b[ bnum] i;sort(Q 1, Q m 1, [](Qnode a, Qnode b){ return ((a.l - 1) / sz (b.l - 1) / sz) || ((a.l - 1) / sz (b.l - 1) / sz a.r b.r); });for (int i 1, l 1, r 0; i m ; i) {if (r Q[i].r) Cnum, C[Cnum] (Cnode){r 1, Q[i].r, l - 1, Cnum, 0}, r Q[i].r;if (r Q[i].r) Cnum, C[Cnum] (Cnode){Q[i].r 1, r, l - 1, Cnum, 0}, r Q[i].r;if (l Q[i].l) Cnum, C[Cnum] (Cnode){l, Q[i].l - 1, r, Cnum, 0}, l Q[i].l;if (l Q[i].l) Cnum, C[Cnum] (Cnode){Q[i].l, l - 1, r, Cnum, 0}, l Q[i].l;}
}
void Work() {sort(C 1, C Cnum 1, [](Cnode a, Cnode b){ return a.x b.x; });for (int i 0; i MX ; i) sum[i] 0;for (int i 1, nw 0; i Cnum ; i) {while (nw C[i].x) { nw;for (int j 1; j bnum ; j) sum[a[nw] ^ b[j]];}int Sum 0;for (int j C[i].l; j C[i].r ; j) Sum sum[a[j]];C[i].ans Sum;} for (int i 0; i MX ; i) sum[i] 0;for (int i 1; i n ; i) {s0[i] s0[i - 1] sum[a[i]];for (int j 1; j bnum ; j) sum[a[i] ^ b[j]];s1[i] s1[i - 1] sum[a[i]];}
}
void Solve() {sort(C 1, C Cnum 1, [](Cnode a, Cnode b){ return a.id b.id; });for (int i 1, l 1, r 0, nw 0; i m ; i) {Ans[Q[i].id] Ans[Q[i - 1].id];if (r Q[i].r) nw, Ans[Q[i].id] (s0[Q[i].r] - s0[r]) - C[nw].ans, r Q[i].r;if (r Q[i].r) nw, Ans[Q[i].id] - (s0[r] - s0[Q[i].r]) - C[nw].ans, r Q[i].r;if (l Q[i].l) nw, Ans[Q[i].id] (s1[Q[i].l - 1] - s1[l - 1]) - C[nw].ans, l Q[i].l;if (l Q[i].l) nw, Ans[Q[i].id] - (s1[l - 1] - s1[Q[i].l - 1]) - C[nw].ans, l Q[i].l;}
}
signed main() {
#ifndef ONLINE_JUDGEfreopen(a.in, r, stdin);
#endifread(n), read(m), read(K), sz (int)sqrt(n);for (int i 1; i n ; i) read(a[i]);for (int i 1; i m ; i) read(Q[i].l), read(Q[i].r), Q[i].id i;Init();Work();Solve();for (int i 1; i m ; i) print(Ans[i]), putc(\n);return 0;
}
