• 莫队

    莫队

    我非常喜欢暴力算法

    莫队最先由队长莫涛整理提出。是一种离线算法，处理区间询问。运用了分块的思想

    适用性广。各种大佬扩展出了一系列的莫队算法。

    复杂度分析玄学。在一些题正解难想、难写时，可考虑用莫队骗分，往往有意想不到的结果。

    普通莫队

    有两个指针 L,RL,R 表示当前维护 [L,R][L,R] 内的答案

    要求在 O(1) 转移到 [L,R−1],[L,R+1],[L+1,R],[L−1,R]

    通过离线、对查询排序，使得暴力转移的复杂度可以接受。

    采用分块 。以 l 所在块为第一关键字， r 为第二关键子排序。

    复杂度：设块大小为 B ，则有 nB 个块

    • 对于每一个块， r 是递增的，最坏移动 n 次，总共 n2B 次
    • l 在同一块内单次移动是 O(B) 的，总共 O(mB)
    • 跨块移动， r 最多跳 n 次 ，l 最多跳 2B 次，最多跨块 O(nB) 次，总共 O(n2B+2n)

    三部分加起来，大致是 O(n2B+mB) 这个级别。由均值不等式，当 B=n√m 时取最优 O(n√m)

    根据题目详情，设置块长，能得到更优的复杂度。

    大致的实现：

    1. struct qry {
    2.     int l, r, id;
    3. } q[N];
    4. inline bool cmp(qry A, qry B) {
    5. }
    6.  
    7. // update current ans
    8. inline void add(int x) {
    9.     
    10. }
    11. inline void del(int x) {
    12. }
    13.  
    14. inline void solve() {
    15.     sort(q + 1, q + T + 1, cmp);
    16.     L = 1, R = 0;
    17.     for (int i = 1, ql, qr, le; i <= T; i++) {
    18.         ql = q[i].l, qr = q[i].r;
    19.         while (L > ql) add(--L);
    20.         while (L < ql) del(L++);
    21.         while (R > qr) del(R--);
    22.         while (R < qr) add(++R);
    23.         ans[q[i].id] = now;
    24.     }
    25. }

    注意！

    这四句话，由于 del 操作的存在，顺序需要注意

    1. while (L > ql) add(--L);
    2.         while (L < ql) del(L++);
    3.         while (R > qr) del(R--);
    4.         while (R < qr) add(++R);

    在一些题里，这种写法会有问题：移动中可能出现 L>R+1 的情况，相当于是多删除了一些数

    而如果用 set 维护某些东西，会出现 “删除一个不存在的数” 的问题。

    正确的顺序是：先进行 add ，再 del ，这样保证始终 L≤R+1 ，修改后代码如下：

    1. while (L > ql) add(--L);
    2.         while (R < qr) add(++R);
    3.         while (L < ql) del(L++);
    4.         while (R > qr) del(R--);

    根据题目，大部分情况，顺序任意。

    奇偶排序

    奇数块按 r 递增排序、偶数块按 r 递减排序。

    优化了 R 指针跳的次数。

    例

    [国家集训队] 小 Z 的袜子

    对于 n=m 的情况，块长取 √n 即可。

    用一个桶 t 存，要求 ∑c12tc(tc−1)

    1. #include 
    2. using namespace std;
    3. typedef unsigned long long uLL;
    4. typedef long double LD;
    5. typedef long long LL;
    6. typedef double db;
    7. const int N = 50005;
    8. int n, T, a[N], pos[N], bz[N];
    9. int size, L, R, tot[N];
    10. LL ans[N], now, all[N], G;
    11. struct qry {
    12.     int l, r, id;
    13. } q[N];
    14. inline bool cmp(qry A, qry B) {
    15.     if (pos[A.l] ^ pos[B.l]) return pos[A.l] < pos[B.l];
    16.     if (pos[A.l] & 1) return A.r < B.r;
    17.     return A.r > B.r;
    18. }
    19. inline void add(int x) {
    20.     now -= tot[a[x]] * (tot[a[x]] - 1) / 2;
    21.     ++tot[a[x]];
    22.     now += tot[a[x]] * (tot[a[x]] - 1) / 2;
    23. }
    24. inline void del(int x) {
    25.     now -= tot[a[x]] * (tot[a[x]] - 1) / 2;
    26.     --tot[a[x]];
    27.     now += tot[a[x]] * (tot[a[x]] - 1) / 2;
    28. }
    29. int main() {
    30.     scanf("%d%d", &n, &T);
    31.     size = sqrt(n);
    32.     for (int i = 1; i <= n; i++) pos[i] = (i - 1) / size + 1;
    33.     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    34.     for (int i = 1; i <= T; i++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
    35.     sort(q + 1, q + T + 1, cmp);
    36.     L = 1, R = 0;
    37.     for (int i = 1, ql, qr, le; i <= T; i++) {
    38.         ql = q[i].l, qr = q[i].r;
    39.         le = qr - ql + 1;
    40.         while (L > ql) add(--L);
    41.         while (L < ql) del(L++);
    42.         while (R > qr) del(R--);
    43.         while (R < qr) add(++R);
    44.         if (le == 1) bz[q[i].id] = 1;
    45.         ans[q[i].id] = now;
    46.         all[q[i].id] = 1ll * le * (le - 1) / 2;
    47.     }
    48.     for (int i = 1; i <= T; i++) {
    49.         if (bz[i]) puts("0/1");
    50.         else G = __gcd(ans[i], all[i]), printf("%lld/%lld\n", ans[i] / G, all[i] / G);
    51.     }
    52. }
    技巧

    这部分

    1. inline void add(int x) {
    2.     now -= tot[a[x]] * (tot[a[x]] - 1) / 2;
    3.     ++tot[a[x]];
    4.     now += tot[a[x]] * (tot[a[x]] - 1) / 2;
    5. }
    6. inline void del(int x) {
    7.     now -= tot[a[x]] * (tot[a[x]] - 1) / 2;
    8.     --tot[a[x]];
    9.     now += tot[a[x]] * (tot[a[x]] - 1) / 2;
    10. }

    会略显繁琐。实际可以化简

    add 操作就是 now 要加上 12(tc+1)tc−12tc(tc−1) ，就是加上 tc

    del 操作就是 now 要减上 12tc(tc−1)−12(tc−1)(tc−2) ，就是减去 tc−1

    1. inline void add(int x) {
    2.     now += tot[a[x]], tot[a[x]]++;
    3. }
    4. inline void del(int x) {
    5.     tot[a[x]]--, now -= tot[a[x]];
    6. }

    实际上，这种化简是很常见的。也能优化常数，减小实现难度

    带修莫队

    国家集训队]数颜色 / 维护队列

    带修改，查询颜色种数。

    把修改当成第三维，记录当前是到第几次修改。

    其实就是弄一个指针，再操作上移动，当前修改多了就改回来，修改少了就改过去。直到次数恰当。

    (L,R,T) 到 (L,R,T+1) 和 (L,R,T−1) 是 O(1) 的。

    具体就是修改后将修改值和原值 swap 一下，改回来也只需要 swap 一下，具体见代码

    排序以 l 所在块、 r 所在块、 t 的值排序。

    复杂度分析：设块长为 B ，修改 c 个，查询 q 个

    • l ：同一块移动 B ，换块移动 2B ，所有询问加起来就是 qB

    • r ：

      1. l 同块时，同块移动 B ，换块移动 2B ，所有询问就是 qB
      2. l 换块，最多 n ，换 nB 次，共 n2B

    • t ：

      1. l,r 同块，移动 c ，有 (nB)2 次 l,r 同块，共 n2cB2
      2. l 或 r 换块，移动 c ，共 (nB)2 次换块，共 n2cB2

    • 一般题目中不会明确 c,q 的个数，统一用 m 代替

    总和： O(mB+n2B+n2mB2)

    B 的最优取值是一个非常复杂的式子。无须纠结。

    看作 n=m ，得到 O(nB+n2B+n3B2)

    设 B=nx ，得到 O(n1+x+n2−x+n3−2x) ，要 max(1+x,2−x,3−2x) 最小

    当 x=23 时取得，此时 B=n23 。复杂度为 O(n53)

    1. #include 
    2. using namespace std;
    3. typedef unsigned long long uLL;
    4. typedef long double LD;
    5. typedef long long LL;
    6. typedef double db;
    7. const int N = 133335;
    8. int n, m, size, pos[N], a[N];
    9. int tq, clk, now, ans[N];
    10. int cnt[1000005];
    11. int L = 1, R = 0, T = 0;
    12. char op[5];
    13. struct qry {
    14.     int l, r, t, id;
    15. } q[N];
    16. struct mdy {
    17.     int p, c;
    18. } C[N];
    19. inline bool cmp(qry A, qry B) {
    20.     if (pos[A.l] ^ pos[B.l]) return pos[A.l] < pos[B.l];
    21.     if (pos[A.r] ^ pos[B.r]) return pos[A.r] < pos[B.r];
    22.     return A.t < B.t;
    23. }
    24. inline void add(int x) { now += !cnt[a[x]]++; }
    25. inline void del(int x) { now -= !--cnt[a[x]]; }
    26. inline void chan(int t) {
    27.     if (L <= C[t].p && C[t].p <= R) del(C[t].p);
    28.     swap(a[C[t].p], C[t].c);
    29.     if (L <= C[t].p && C[t].p <= R) add(C[t].p);
    30. }
    31. int main() {
    32.     scanf("%d%d", &n, &m);
    33.     size = pow(n, 2.0 / 3.0);
    34.     for (int i = 1; i <= n; i++) pos[i] = (i - 1) / size + 1;
    35.     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    36.     for (int i = 1, a, b; i <= m; i++) {
    37.         scanf("%s%d%d", op, &a, &b);
    38.         if (op[0] == 'Q') {
    39.             ++tq, q[tq] = (qry){ a, b, clk, tq };
    40.         } else {
    41.             ++clk, C[clk] = (mdy){ a, b };
    42.         }
    43.     }
    44.     sort(q + 1, q + tq + 1, cmp);
    45.     for (int i = 1, ql, qr, qt; i <= tq; i++) {
    46.         ql = q[i].l, qr = q[i].r, qt = q[i].t;
    47.         while (L < ql) del(L++);
    48.         while (L > ql) add(--L);
    49.         while (R < qr) add(++R);
    50.         while (R > qr) del(R--);
    51.         while (T < qt) chan(++T);
    52.         while (T > qt) chan(T--);
    53.         ans[q[i].id] = now;
    54.     }
    55.     for (int i = 1; i <= tq; i++) printf("%d\n", ans[i]);
    56. }

    回滚莫队

    在一些题目中，往往出现删除(或增加)非常容易。但是另一个操作却难以实现。

    回滚莫队应运而生，解决这种情况

    只增不减

    1. 数列分块，按 l 所在块、 r 的值升序排序。

    2. l,r 再同一块，暴力处理。

    3. 对于同在块 T 的询问，将莫队左指针设为 RT+1 ，右指针设为 RT ，这是空区间

    4. 由于 r 升序排序，莫队右指针可以一直加，一个块最多 n

      l 可能乱序，此时左指针从 RT+1 出发，加点到达询问位置。

      回答完询问，撤销本次移动的影响，注意是撤销，使左端点回到 RT+1

      每一个询问最多 √n

    5. 相同方式处理下一个块

    复杂度依然是 O(n√n)

    歴史の研究

    求 maxctc×c ，其中 tc 为出现次数。

    用桶统计出现次数。加点时更新答案，撤销具体就是在桶中减去出现次数，而不修改答案。

    1. #include 
    2. using namespace std;
    3. typedef unsigned long long uLL;
    4. typedef long double LD;
    5. typedef long long LL;
    6. typedef double db;
    7. const int N = 100005, SQ = 320;
    8. int n, m, a[N], tt[N], b[N], tl, Bsz, Btot, pr[SQ], po[N];
    9. int L = 1, R = 0, cnt[N], cur, tc[N];
    10. LL ans[N], tmp, now;
    11. struct qry { int l, r, id; } q[N];
    12. inline bool cmp(qry A, qry B) {
    13.     if (po[A.l] ^ po[B.l]) return po[A.l] < po[B.l];
    14.     return A.r < B.r;
    15. }
    16. inline void add(int x) {
    17.     ++cnt[b[x]];
    18.     now = max(now, 1ll * cnt[b[x]] * a[x]);
    19. }
    20. inline void cancel(int x) {
    21.     --cnt[b[x]];
    22. }
    23. int main() {
    24.     scanf("%d%d", &n, &m), Bsz = sqrt(n), Btot = n / Bsz;
    25.     for (int i = 1; i <= n; i++) scanf("%d", &a[i]), tt[i] = a[i];
    26.     sort(tt + 1, tt + n + 1), tl = unique(tt + 1, tt + n + 1) - tt - 1;
    27.     for (int i = 1; i <= n; i++) b[i] = lower_bound(tt + 1, tt + tl + 1, a[i]) - tt;
    28.     for (int i = 1; i <= Btot; i++) pr[i] = i * Bsz;
    29.     if (pr[Btot] < n) pr[++Btot] = n;
    30.     for (int i = 1; i <= n; i++) po[i] = (i - 1) / Bsz + 1;
    31.     for (int i = 1; i <= m; i++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
    32.     sort(q + 1, q + m + 1, cmp);
    33.  
    34.     for (int i = 1, ql, qr; i <= m; i++) {
    35.         ql = q[i].l, qr = q[i].r;
    36.         if (po[ql] == po[qr]) {
    37.             for (int j = ql; j <= qr; j++) ++tc[b[j]];
    38.             tmp = 0;
    39.             for (int j = ql; j <= qr; j++) tmp = max(tmp, 1ll * tc[b[j]] * a[j]);
    40.             for (int j = ql; j <= qr; j++) --tc[b[j]];
    41.             ans[q[i].id] = tmp;
    42.             continue;
    43.         }
    44.         if (cur ^ po[ql]) {
    45.             cur = po[ql];
    46.             while (R > pr[cur]) cancel(R--);
    47.             while (L < pr[cur] + 1) cancel(L++);
    48.             now = 0;
    49.         }
    50.         while (R < qr) add(++R);
    51.         tmp = now;
    52.         while (L > ql) add(--L);
    53.         while (L < pr[cur] + 1) cancel(L++);
    54.         ans[q[i].id] = now, now = tmp;
    55.     }
    56.     for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
    57. }

    只减不增

    同理。区别如下：

    1. 右端点降序排序
    2. 左端点初始为 LT ，右端点为 n

    树上莫队

    树上莫队一般是用于处理链的问题，子树的可以用 dfs 序解决。

    COT2 - Count on a tree II

    链上数颜色。用欧拉序(括号序)转换。求

    法是 dfs 得到一个点入栈、出栈顺序。分别记为 firstx,lastx

    性质是：欧拉序上 [firstx,lastx] 之间的点都在子树 x 中，且都出现两次。

    考虑将链转为欧拉序上区间问题。对于一条链 (u,v) ，假设 firstu≤firstv 即 u 比 v 先出现。

    1. lca(u,v)=u ，说明 v 在子树 u 内，直接转为 [firstu,firstv]

      同时区间内出现 2 次的点都不要。因为链不会经过一个点两次，经过了两次一定不在链上

    2. lca(u,v)≠u ，用 [lastx,firstx] ，同时 lca(u,v) 没有算，需要单独考虑。

    实现时：注意序列长度是 2n ，用一个数组记录是否出现即可实现取重。

    1. #include 
    2. using namespace std;
    3. typedef unsigned long long uLL;
    4. typedef long double LD;
    5. typedef long long LL;
    6. typedef double db;
    7. const int N = 100005;
    8. int n, T, tt[N], a[N], lt, lst[N], Ecnt, pos[N], size, vis[N];
    9. int fr[N], la[N], clk, fa[N][20], dep[N], ord[N], ans[N], cnt[N];
    10. int L = 1, R = 0, now;
    11. struct qry {
    12.     int l, r, x, id;
    13. } q[N];
    14. inline bool cmp(qry A, qry B) {
    15.     if (pos[A.l] ^ pos[B.l]) return pos[A.l] < pos[B.l];
    16.     if (pos[A.l] & 1) return A.r < B.r;
    17.     return A.r > B.r;
    18. }
    19. struct Ed { int to, nxt; } e[N];
    20. inline void Ae(int fr, int go) {
    21.     e[++Ecnt] = (Ed){ go, lst[fr] }, lst[fr] = Ecnt;
    22. }
    23. void dfs(int u, int ff) {
    24.     fa[u][0] = ff, dep[u] = dep[ff] + 1;
    25.     for (int i = 1; i <= 16; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    26.     ord[++clk] = u, fr[u] = clk;
    27.     for (int i = lst[u], v; i; i = e[i].nxt)
    28.         if ((v = e[i].to) ^ ff) dfs(v, u);
    29.     ord[++clk] = u, la[u] = clk;
    30. }
    31. inline int LCA(int x, int y) {
    32.     if (dep[x] < dep[y]) x ^= y ^= x ^= y;
    33.     for (int i = 16; ~i; i--)
    34.         if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
    35.     if (x == y) return x;
    36.     for (int i = 16; ~i; i--)
    37.         if (fa[x][i] ^ fa[y][i]) x = fa[x][i], y = fa[y][i];
    38.     return fa[x][0];
    39. }
    40. inline void work(int x) {
    41.     if (vis[x]) now -= !--cnt[a[x]];
    42.     else now += !cnt[a[x]]++;
    43.     vis[x] ^= 1;
    44. }
    45. int main() {
    46.     scanf("%d%d", &n, &T);
    47.     for (int i = 1; i <= n; i++) scanf("%d", &tt[i]), a[i] = tt[i];
    48.     sort(tt + 1, tt + n + 1);
    49.     lt = unique(tt + 1, tt + n + 1) - tt - 1;
    50.     for (int i = 1; i <= n; i++)
    51.         a[i] = lower_bound(tt + 1, tt + lt + 1, a[i]) - tt;
    52.     for (int i = 1, u, v; i < n; i++) {
    53.         scanf("%d%d", &u, &v);
    54.         Ae(u, v), Ae(v, u);
    55.     }
    56.     dfs(1, 0);
    57.     size = sqrt(clk);
    58.     for (int i = 1; i <= clk; i++) pos[i] = (i - 1) / size + 1;
    59.     for (int i = 1, u, v, ll; i <= T; i++) {
    60.         scanf("%d%d", &u, &v);
    61.         ll = LCA(u, v);
    62.         if (fr[u] > fr[v]) u ^= v ^= u ^= v;
    63.         if (u == ll) q[i] = (qry){ fr[u], fr[v], 0, i };
    64.         else q[i] = (qry){ la[u], fr[v], ll, i };
    65.     }
    66.     sort(q + 1, q + T + 1, cmp);
    67.     for (int i = 1, ql, qr, qx; i <= T; i++) {
    68.         ql = q[i].l, qr = q[i].r, qx = q[i].x;
    69.         while (L < ql) work(ord[L++]);
    70.         while (L > ql) work(ord[--L]);
    71.         while (R < qr) work(ord[++R]);
    72.         while (R > qr) work(ord[R--]);
    73.         if (qx) work(qx);
    74.         ans[q[i].id] = now;
    75.         if (qx) work(qx);
    76.     }
    77.     for (int i = 1; i <= T; i++) printf("%d\n", ans[i]);
    78. }

    二维莫队

    YALI 往年集训题处的做法。

    D2T2 蔬菜

    求矩阵中颜色出现次数的平方和。

    查询放到了矩阵中。按照四个端点所在块排序。

    不同于普通莫队，这里一次修改为 O(n) 的。

    块长随缘了，分析累了。

    但是码量、速度碾标算的四维偏序

    #include using namespace std;typedef unsigned long long uLL;typedef long double LD;typedef long long LL;typedef double db;const int N = 205;int n, m, Ti, a[N][N], b[N * N], le, t[N * N], now, Bsz;struct qry {    int xx, yy, x2, y2, id;} q[100005];int ans[100005];inline bool cmp(qry A, qry B) {    if (A.xx / Bsz != B.xx / Bsz)        return A.xx / Bsz < B.xx / Bsz;    if (A.yy / Bsz != B.yy / Bsz)        return A.yy / Bsz < B.yy / Bsz;    if (A.x2 / Bsz != B.x2 / Bsz)        return A.x2 / Bsz < B.x2 / Bsz;    return A.y2 < B.y2;}inline void add(int x) { now += 1 + 2 * t[x], ++t[x]; }inline void del(int x) { now += 1 - 2 * t[x], --t[x]; }inline void pls(int i, int l, int r, int op) {    for (int j = l; j <= r; j++) add(op ? a[i][j] : a[j][i]);}inline void rmv(int i, int l, int r, int op) {    for (int j = l; j <= r; j++) del(op ? a[i][j] : a[j][i]);}int main() {    // freopen("vegetable.in", "r", stdin);    // freopen("vegetable.out", "w", stdout);    scanf("%d%d%d", &n, &m, &Ti);    for (int i = 1; i <= n; i++)        for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]), b[++le] = a[i][j];    Bsz = sqrt(max(n, m));    sort(b + 1, b + le + 1), le = unique(b + 1, b + le + 1) - b - 1;    for (int i = 1; i <= n; i++)        for (int j = 1; j <= m; j++) a[i][j] = lower_bound(b + 1, b + le + 1, a[i][j]) - b;    for (int i = 1; i <= Ti; i++) scanf("%d%d%d%d", &q[i].xx, &q[i].yy, &q[i].x2, &q[i].y2), q[i].id = i;    sort(q + 1, q + Ti + 1, cmp);    int li = 1, ri = 0, lj = 1, rj = 0;    for (int i = 1, ql, qr; i <= Ti; i++) {        while (li < q[i].xx) rmv(li++, lj, rj, 1);        while (li > q[i].xx) pls(--li, lj, rj, 1);        while (ri < q[i].x2) pls(++ri, lj, rj, 1);        while (ri > q[i].x2) rmv(ri--, lj, rj, 1);        while (lj < q[i].yy) rmv(lj++, li, ri, 0);        while (lj > q[i].yy) pls(--lj, li, ri, 0);        while (rj < q[i].y2) pls(++rj, li, ri, 0);        while (rj > q[i].y2) rmv(rj--, li, ri, 0);        ans[q[i].id] = now;    }    for (int i = 1; i <= Ti; i++) printf("%d\n", ans[i]);}

    莫队二次离线

    先 % 提出者 lxl ，用于解决莫队转移复杂度高的情况

    【模板】莫队二次离线

    求区间内满足条件数对个数，普通莫队是 O(n√n(14k)) ，难以接受，但是注意到可以差分

    设 f(x,l,r) 表示 x 与 [l,r] 中的点形成的合法数对个数，莫队的指针有四种移动方法，讨论一波。

    设莫队指针为 L,R ，询问区间为 ql,qr

    • L<ql ，从 [L,R] 到 [L+1,R] ，减去 f(L,L+1,R)=f(L,1,R)−f(L,1,L)
    • L>ql ，从 [L,R] 到 [L−1,R] ，加上 f(L−1,L,R)=f(L−1,1,R)−f(L−1,1,L−1)
    • R<qr ，从 [L,R] 到 [L,R+1] ，加上 f(R+1,L,R)=f(R+1,1,R)−f(R+1,1,L−1)
    • R>qr ，从 [L,R] 到 [L,R−1] ，减去 f(R,L,R−1)=f(R,1,R−1)−f(R,1,L−1)

    发现如果与处理出 f(x,1,x) 和 f(x,1,x−1) ，就解决了一半。

    移动指针时加(或减)即可。前缀和优化减小常数

    剩下的一部分的贡献和：形如 ∑rx=lf(x,1,pos) ，二次离线，在 pos 处挂一个 (l,r,id,op)

    其中 id 是询问编号， op 是 1 或 -1 的系数。枚举每一个位置，暴力求解即可。

    由于考虑的是变化量，所以答案应该求前缀和。

    复杂度是 O(n√n+n(14k))

    1. #include 
    2. #define pb push_back
    3. using namespace std;
    4. typedef unsigned long long uLL;
    5. typedef long double LD;
    6. typedef long long LL;
    7. typedef double db;
    8. const int N = 100005;
    9. int n, m, K, a[N], b[N], Tb, cnt[N], pos[N], Bsz;
    10. LL pre1[N], pre2[N], ans[N], out[N];
    11. struct qry { int l, r, id; } q[N];
    12. struct add { int l, r, id, op; } nw;
    13. vector cf[N];
    14. inline bool cmp(qry A, qry B) {
    15.     if (pos[A.l] ^ pos[B.l]) return pos[A.l] < pos[B.l];
    16.     return A.r < B.r;
    17. }
    18. int main() {
    19.     scanf("%d%d%d", &n, &m, &K);
    20.     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    21.     if (K > 14) {
    22.         for (int i = 1; i <= m; i++) puts("0");
    23.         return 0;
    24.     }
    25.     for (int i = 0, j, t; i < 16384; i++) {
    26.         j = i, t = 0; while (j) j -= j & -j, ++t;
    27.         if (t == K) b[++Tb] = i;
    28.     }
    29.     // pre1 : f(i, 1, i - 1)
    30.     // pre2 : f(i, 1, i)
    31.     for (int i = 1; i <= n; i++) {
    32.         pre1[i] = pre1[i - 1] + cnt[a[i]];
    33.         for (int j = 1; j <= Tb; j++) ++cnt[a[i] ^ b[j]];
    34.         pre2[i] = pre2[i - 1] + cnt[a[i]];
    35.     }
    36.     Bsz = sqrt(n);
    37.     for (int i = 1; i <= n; i++) pos[i] = (i - 1) / Bsz + 1;
    38.     for (int i = 1; i <= m; i++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
    39.     sort(q + 1, q + m + 1, cmp);
    40.     for (int i = 1, L = 1, R = 0, ql, qr; i <= m; i++) {
    41.         ql = q[i].l, qr = q[i].r;
    42.         ans[i] = pre2[ql - 1] - pre2[L - 1] + pre1[qr] - pre1[R];
    43.         if (L < ql) cf[R].pb((add){ L, ql - 1, i,-1 });
    44.         if (L > ql) cf[R].pb((add){ ql, L - 1, i, 1 });
    45.         L = ql;
    46.         // attention : pointer L moves to ql first
    47.         if (R < qr) cf[L - 1].pb((add){ R + 1, qr, i,-1 });
    48.         if (R > qr) cf[L - 1].pb((add){ qr + 1, R, i, 1 });
    49.         R = qr;
    50.         // -= f(L, L + 1, R) = -f(L, 1, R) + f(L, 1, L);
    51.         // += f(L - 1, L, R) = +f(L - 1, 1, R) - f(L - 1, 1, L - 1)
    52.         // += f(R + 1, L, R) = +f(R + 1, 1, R) - f(R + 1, 1, L - 1);
    53.         // -= f(R, L, R - 1) = -f(R, 1, R - 1) + f(R, 1, L - 1);
    54.     }
    55.     memset(cnt, 0, sizeof(cnt));
    56.     for (int i = 1; i <= n; i++) {
    57.         for (int j = 1; j <= Tb; j++) cnt[a[i] ^ b[j]]++;
    58.         for (int j = 0, Lj = cf[i].size(); j < Lj; j++) {
    59.             nw = cf[i][j];
    60.             register LL tmp = 0;
    61.             for (int k = nw.l; k <= nw.r; k++) tmp += cnt[a[k]];
    62.             ans[nw.id] += nw.op * tmp;
    63.         }
    64.     }
    65.     for (int i = 1; i <= m; i++) ans[i] += ans[i - 1], out[q[i].id] = ans[i];
    66.     for (int i = 1; i <= m; i++) printf("%lld\n", out[i]);
    67. }

    莫队加 bitset

    bitset 有 n64 的复杂度

    往往解决区间内和/差/积/max等值域相关问题

    小清新人渣的本愿

    [Ynoi2017] 由乃的玉米田 (比上一题多了除法)

    查询是否存在 a,b 满足相加/减/乘/除等于 x

    和/差用 bitset 解决，乘积直接暴力。

    • 减法：相当于存在 (a−x,a) 用一个 bitset s1 ，第 i 位记录是否存在 i 。

      如果 s1 & (s1 << x) 有任意一位是 1 ，说明可行。

    • 加法：相当于存在 (x−a,a) ，需要一个反的 bitset s2 ，记录是否存在 max−i

      那么 s2 >> (max - k) 得到是否存在 (max−i)−(max−k)=k−i 了。

      s1 & (s2 >> (max - k)) 存在 1 说明可行

    • 乘法：分解质因数。根号级别。

    根号分治

    解决除法操作：

    1. x≤√max ，将所有满足情况的 x 存下来单独处理。

      对于同一个 x ，枚举所有数，维护 lstv 表示 v 最后出现位置，

      还有 mli 表示以 i 为右端点最大的左端点，使得 [mli,i] 内存在满足条件的数对。

    2. 否则，暴力枚举 x 的倍数

    code

    时间复杂度：O(n√n+T×max64+T√max) ，十分的鬼畜。。

    给出 由乃的玉米田 的代码

    1. #include 
    2. using namespace std;
    3. typedef unsigned long long uLL;
    4. typedef long double LD;
    5. typedef long long LL;
    6. typedef double db;
    7. const int N = 100005;
    8. int n, T, a[N], pos[N], unit, ans[N], cnt[N], L = 1, R = 0, mx, lim, lst[N], ml[N], Qtot;
    9. bitset s1, s2;
    10. struct qry { int l, r, x, op, id; } q[N];
    11. vector q2[320];
    12. inline bool cmp(qry A, qry B) {
    13.     if (pos[A.l] ^ pos[B.l]) return pos[A.l] < pos[B.l];
    14.     return A.r < B.r;
    15. }
    16. inline void add(int x) {
    17.     ++cnt[x = a[x]];
    18.     if (cnt[x] == 1) s1[x] = s2[100000 - x] = 1;
    19. }
    20. inline void del(int x) {
    21.     --cnt[x = a[x]];
    22.     if (!cnt[x]) s1[x] = s2[100000 - x] = 0;
    23. }
    24. int main() {
    25.     scanf("%d%d", &n, &T);
    26.     unit = sqrt(n);
    27.     for (int i = 1; i <= n; i++) pos[i] = (i - 1) / unit + 1;
    28.     for (int i = 1; i <= n; i++) scanf("%d", &a[i]), mx = max(mx, a[i]);
    29.     lim = sqrt(mx);
    30.     for (int i = 1, op, l, r, x; i <= T; i++) {
    31.         scanf("%d%d%d%d", &op, &l, &r, &x);
    32.         if (op == 4 && x <= lim) q2[x].push_back((qry){ l, r, x, op, i });
    33.         else q[++Qtot] = (qry){ l, r, x, op, i };
    34.     }
    35.     for (int w = 1; w <= lim; w++) {
    36.         memset(lst, 0, sizeof(lst));
    37.         memset(ml, 0, sizeof(ml));
    38.         if (q2[w].empty()) continue;
    39.         for (int i = 1, p = 0; i <= n; i++) {
    40.             lst[a[i]] = i;
    41.             if (w * a[i] <= mx) p = max(p, lst[w * a[i]]);
    42.             if (a[i] % w == 0) p = max(p, lst[a[i] / w]);
    43.             ml[i] = p;
    44.         }
    45.         for (qry qq : q2[w]) ans[qq.id] = (qq.l <= ml[qq.r]);
    46.     }
    47.     sort(q + 1, q + Qtot + 1, cmp);
    48.     for (int i = 1, ql, qr, qx; i <= Qtot; i++) {
    49.         ql = q[i].l, qr = q[i].r, qx = q[i].x;
    50.         while (L < ql) del(L++);
    51.         while (L > ql) add(--L);
    52.         while (R < qr) add(++R);
    53.         while (R > qr) del(R--);
    54.         if (q[i].op == 1) ans[q[i].id] = (s1 & (s1 >> qx)).any();
    55.         else if (q[i].op == 2) ans[q[i].id] = (s1 & (s2 >> (n - qx))).any();
    56.         else if (q[i].op == 3) {
    57.             for (int j = 1; j * j <= qx; j++)
    58.                 if (qx % j == 0)
    59.                     if (s1[j] && s1[qx / j]) {
    60.                         ans[q[i].id] = 1; break;
    61.                     }
    62.         } else {
    63.             for (int j = 1; j * qx <= mx; j++)
    64.                 if (s1[j] && s1[j * qx]) { ans[q[i].id] = 1; break; }
    65.         }
    66.     }
    67.     for (int i = 1; i <= T; i++) puts(ans[i] ? "yuno" : "yumi");
    68. }

    应用

    [WC2013] 糖果公园

    [WC2013] 糖果公园

    树上询问路径，求 ∑cvalc∑cntci=1wi ，带修改。

    树上带修莫队，弄出欧拉序后写带修莫队，板子题，锻炼代码实现。。

    1. #include 
    2. #define ri register int
    3. using namespace std;
    4. char buf[100000], *Sf = buf, *Tf = buf;
    5. inline char G() {
    6. 	return Sf == Tf && (Tf = (Sf = buf) + fread(buf, 1, 100000, stdin), Sf == Tf) ? EOF : *Sf++;
    7. }
    8. inline int Rd() {
    9. 	ri x = 0;
    10. 	static char C = G();
    11. 	for (; C < '0' || C > '9'; C = G()) ;
    12. 	for (; C > '/' && C < ':'; C = G()) x = (x << 1) + (x << 3) + (C ^ 48);
    13. 	return x;
    14. }
    15. typedef long long LL;
    16. const int N = 200005;
    17. int n, m, Ti, v[N], w[N], a[N], lst[N], Ecnt;
    18. int fr[N], la[N], ord[N], clk, Tc, Tq, sz[N], top[N];
    19. int fa[N], dep[N], Bs, pos[N], vis[N], sn[N];
    20. int L, R, T, cnt[N];
    21. LL ans[N], now;
    22. struct qry { int l, r, t, x, id; } q[N];
    23. struct chg { int p, x; } C[N];
    24. struct Ed { int to, nxt; } e[N << 1];
    25. inline void Ae(ri fr, ri go) {
    26.     e[++Ecnt] = (Ed){ go, lst[fr] }, lst[fr] = Ecnt;
    27. }
    28. void dfs(ri u, ri ff) {
    29.     fr[u] = ++clk, ord[clk] = u;
    30. 	dep[u] = dep[fa[u] = ff] + 1, sz[u] = 1;
    31.     for (ri i = lst[u], v; i; i = e[i].nxt)
    32. 		if ((v = e[i].to) ^ ff) {
    33. 			dfs(v, u), sz[u] += sz[v];
    34. 			if (sz[v] > sz[sn[u]]) sn[u] = v;
    35. 		}
    36.     la[u] = ++clk, ord[clk] = u;
    37. }
    38. void dfs2(ri u, ri nw) {
    39. 	top[u] = nw; if (!sn[u]) return; dfs2(sn[u], nw);
    40. 	for (ri i = lst[u], v; i; i = e[i].nxt)
    41. 	if ((v = e[i].to) ^ fa[u] && v ^ sn[u]) dfs2(v, v);
    42. }
    43. inline int LCA(ri x, ri y) {
    44. 	for (;top[x] ^ top[y]; x = fa[top[x]])
    45. 		if (dep[top[x]] < dep[top[y]]) x ^= y ^= x ^= y;
    46. 	return dep[x] < dep[y] ? x : y;
    47. }
    48. inline bool cmp(qry A, qry B) {
    49.     if (pos[A.l] ^ pos[B.l]) return pos[A.l] < pos[B.l];
    50.     if (pos[A.r] ^ pos[B.r]) return pos[A.r] < pos[B.r];
    51.     return A.t < B.t;
    52. }
    53. inline void add(ri x) { now += 1ll * w[++cnt[x]] * v[x]; }
    54. inline void del(ri x) { now -= 1ll * w[cnt[x]--] * v[x]; }
    55. inline void work(ri x) { (vis[x] ^= 1) ? add(a[x]) : del(a[x]); }
    56. inline void chan(ri t) {
    57.     if (vis[C[t].p]) del(a[C[t].p]), add(C[t].x);
    58.     swap(a[C[t].p], C[t].x);
    59. }
    60. int main() {
    61.     n = Rd(), m = Rd(), Ti = Rd();
    62.     for (ri i = 1; i <= m; i++) v[i] = Rd();
    63.     for (ri i = 1; i <= n; i++) w[i] = Rd();
    64.     for (ri i = 1, u, v; i < n; i++) {
    65.         u = Rd(), v = Rd(), Ae(u, v), Ae(v, u);
    66.     }
    67.     for (ri i = 1; i <= n; i++) a[i] = Rd();
    68.     dfs(1, 0), dfs2(1, 1);
    69.     for (ri op, x, y, ff; Ti--; ) {
    70.     	op = Rd(), x = Rd(), y = Rd();
    71.         if (!op) ++Tc, C[Tc] = (chg){ x, y };
    72.         else {
    73.             ff = LCA(x, y), ++Tq;
    74.             if (fr[x] > fr[y]) x ^= y ^= x ^= y;
    75.             if (x == ff) q[Tq] = (qry){ fr[x], fr[y], Tc, 0, Tq };
    76.             else q[Tq] = (qry){ la[x], fr[y], Tc, ff, Tq };
    77.         }
    78.     }
    79.     Bs = pow(clk, 2.0 / 3.0);
    80.     for (ri i = 1; i <= clk; i++) pos[i] = (i - 1) / Bs + 1;
    81.     sort(q + 1, q + Tq + 1, cmp);
    82.     L = 1, R = 0, T = 0;
    83.     for (ri i = 1, ql, qr, qt; i <= Tq; i++) {
    84.         ql = q[i].l, qr = q[i].r, qt = q[i].t;
    85.         while (L < ql) work(ord[L++]);
    86.         while (L > ql) work(ord[--L]);
    87.         while (R < qr) work(ord[++R]);
    88.         while (R > qr) work(ord[R--]);
    89.         while (T < qt) chan(++T);
    90.         while (T > qt) chan(T--);
    91.         if (q[i].x) work(q[i].x);
    92.         ans[q[i].id] = now;
    93.         if (q[i].x) work(q[i].x);
    94.     }
    95.     for (ri i = 1; i <= Tq; i++) printf("%lld\n", ans[i]);
    96. }

    [SNOI2017]一个简单的询问

    [SNOI2017]一个简单的询问

    求 ∑xget(l1,r1,x)×get(l2,r2,x) ，其中 get(l,r,x) 表示 [l,r] 中 x 的个数

    差分，得 ∑x(get(1,r1,x)−get(1,l1−1,x))(get(1,r2,x)−get(1,l2−1,x))

    令 g(p,x)=get(1,p,x) ，

    得 ∑xg(r1,x)g(r2,x)−g(r1,x)g(l2−1,x)−g(l1−1,x)g(r2,x)+g(l1−1,x)g(l2−1,x)

    拆成四个询问。用两个数组维护。

    这道题其实是运用了莫队的思想，并不是经典的莫队。

    1. #include 
    2. using namespace std;
    3. typedef unsigned long long uLL;
    4. typedef long double LD;
    5. typedef long long LL;
    6. typedef double db;
    7. const int N = 50005;
    8. int n, a[N], tq, T, sz, pos[N], cnt[N][2];
    9. LL ans[N], now;
    10. int L = 0, R = 0;
    11. struct qry {
    12.     int a, b, op, id;
    13. } q[N << 2];
    14. inline bool cmp(qry A, qry B) {
    15.     if (pos[A.a] != pos[B.a]) return pos[A.a] < pos[B.a];
    16.     return A.b < B.b;
    17. }
    18. inline void add(int x, int w) {
    19. 	now += 1ll * cnt[a[x]][w];
    20.     ++cnt[a[x]][w ^ 1];
    21. }
    22. inline void del(int x, int w) {
    23. 	now -= 1ll * cnt[a[x]][w];
    24.     --cnt[a[x]][w ^ 1];
    25. }
    26. int main() {
    27.     scanf("%d", &n);
    28.     sz = sqrt(n);
    29.     for (int i = 1; i <= n; i++) pos[i] = (i - 1) / sz + 1;
    30.     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    31.     scanf("%d", &T);
    32.     for (int i = 1, a, b, c, d; i <= T; i++) {
    33.         scanf("%d%d%d%d", &a, &b, &c, &d);
    34.         q[++tq] = (qry){ a - 1, c - 1, 1, i };
    35.         q[++tq] = (qry){ a - 1, d, -1, i };
    36.         q[++tq] = (qry){ b, d, 1, i };
    37.         q[++tq] = (qry){ b, c - 1, -1, i };
    38.     }
    39.     for (int i = 1; i <= tq; i++)
    40.         if (q[i].a > q[i].b) swap(q[i].a, q[i].b);
    41.     sort(q + 1, q + tq + 1, cmp);
    42.     for (int i = 1, ql, qr; i <= tq; i++) {
    43.         ql = q[i].a, qr = q[i].b;
    44.         while (L < ql) add(++L, 0);
    45.         while (L > ql) del(L--, 0);
    46.         while (R < qr) add(++R, 1);
    47.         while (R > qr) del(R--, 1);
    48.         ans[q[i].id] += now * q[i].op;
    49.     }
    50.     for (int i = 1; i <= T; i++) printf("%lld\n", ans[i]);
    51. }

    [Ynoi2016] 这是我自己的发明

    [Ynoi2016] 这是我自己的发明

    前置知识：上一题。将询问放到了子树上，用 dfs 序转换。

    换根对于一个 x 只有两种情况：根在不在子树 x 中(当根为 1 时)

    对于根在子树 x 的情况其实就是整一棵树挖掉 x 的某一个儿子所在子树。

    这个儿子所在子树是包含根的，开 map 按 dfn 挂上所有儿子，用新的根的 dfn 一次 lower_bound 即可。

    询问要么是一个区间，要么是 [1,n] 挖掉一个区间

    设 f([a,b],[c,d]) 表示区间 [a,b] 和 [c,d] 的答案，prei=f([1,i],[1,n]) 有两种情况较特殊

    f([l,r],[1,L)∪(R,n])=f([l,r],[1,n])−f([l,r],[L,R])=prer−prel−f([l,r],[L,R])

    和

    f([1,l)∪(r,n],[1,L)∪(R,n])=f([1,n],[1,n])−f([l,r],[1,n])−f([1,n],[L,R])+f([l,r],[L,R])=⋯

    发现其实只用求 f([l,r],[L,R]) ，只拆成四个询问即可

    1. #include 
    2. using namespace std;
    3. typedef unsigned long long uLL;
    4. typedef long double LD;
    5. typedef long long LL;
    6. typedef double db;
    7. const int N = 100005, M = 500005;
    8. int n, T, a[N], b[N], lst[N], ecnt, clk, st[N], ed[N], Rt;
    9. int tq, pos[N], sz, cnt[N][2], L = 0, R = 0, tc[N];
    10. LL now, ans[M], pre[N];
    11. struct qry {
    12.     int a, b, op, id;
    13. } q[M << 2];
    14. struct Ed { int to, nxt; } e[N << 1];
    15. inline void Ae(int fr, int go) {
    16.     e[++ecnt] = (Ed){ go, lst[fr] }, lst[fr] = ecnt;
    17. }
    18. map<int, int> ch[N];
    19. void dfs(int u, int ff) {
    20.     st[u] = ++clk;
    21.     for (int i = lst[u], v; i; i = e[i].nxt)
    22.         if ((v = e[i].to) ^ ff) dfs(v, u), ch[u][ed[v]] = v;
    23.     ed[u] = clk;
    24. }
    25. inline bool cmp(qry A, qry B) {
    26.     if (pos[A.a] ^ pos[B.a]) return pos[A.a] < pos[B.a];
    27.     return A.b < B.b;
    28. }
    29. inline void add(int x, int w) {
    30.     ++cnt[a[x]][w];
    31.     now += cnt[a[x]][w ^ 1];
    32. }
    33. inline void del(int x, int w) {
    34.     --cnt[a[x]][w];
    35.     now -= cnt[a[x]][w ^ 1];
    36. }
    37. int main() {
    38.     scanf("%d%d", &n, &T);
    39.     sz = n / sqrt(T);
    40.     for (int i = 1; i <= n; i++) pos[i] = (i - 1) / sz + 1;
    41.     for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
    42.     sort(a + 1, a + n + 1);
    43.     tq = unique(a + 1, a + n + 1) - a - 1;
    44.     for (int i = 1; i <= n; i++)
    45.         b[i] = lower_bound(a + 1, a + tq + 1, b[i]) - a;
    46.     for (int i = 1, u, v; i < n; i++) {
    47.         scanf("%d%d", &u, &v);
    48.         Ae(u, v), Ae(v, u);
    49.     }
    50.     Rt = 1;
    51.     dfs(1, 0);
    52.     tq = 0;
    53.     for (int i = 1; i <= n; i++) ++tc[a[st[i]] = b[i]];
    54.     for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + tc[a[i]];
    55.     for (int i = 1, op, x, y, tx, ty, a, b, c, d; i <= T; i++) {
    56.         scanf("%d%d", &op, &x);
    57.         if (op == 1) Rt = x, --i, --T;
    58.         else {
    59.             scanf("%d", &y);
    60.             tx = (st[x] <= st[Rt] && ed[Rt] <= ed[x]); if (x == Rt) x = 1, tx = 0;
    61.             ty = (st[y] <= st[Rt] && ed[Rt] <= ed[y]); if (y == Rt) y = 1, ty = 0;
    62.             if (tx) x = ch[x].lower_bound(st[Rt])->second;
    63.             if (ty) y = ch[y].lower_bound(st[Rt])->second;
    64.             a = st[x] - 1, b = ed[x], c = st[y] - 1, d = ed[y];
    65.             if (tx && ty) ans[i] += pre[n];
    66.             op = (tx == ty ? -1 : 1);
    67.             if (tx) ans[i] += (pre[d] - pre[c]) * op;
    68.             if (ty) ans[i] += (pre[b] - pre[a]) * op;
    69.             q[++tq] = (qry){ a, c, -op, i };
    70.             q[++tq] = (qry){ a, d, op, i };
    71.             q[++tq] = (qry){ b, d, -op, i };
    72.             q[++tq] = (qry){ b, c, op, i };
    73.         }
    74.     }
    75.     sort(q + 1, q + tq + 1, cmp);
    76.     for (int i = 1, ql, qr; i <= tq; i++) {
    77.         ql = q[i].a, qr = q[i].b;
    78.         while (L < ql) add(++L, 0);
    79.         while (L > ql) del(L--, 0);
    80.         while (R < qr) add(++R, 1);
    81.         while (R > qr) del(R--, 1);
    82.         ans[q[i].id] += now * q[i].op;
    83.     }
    84.     for (int i = 1; i <= T; i++) printf("%lld\n", ans[i]);
    85. }

    Gty的二逼妹子序列

    Gty的二逼妹子序列

    求区间内值在 [a,b] 范围内的数的个数。

    我会树状数组！

    O(n√nlogn) ，会超时。

    根号平衡

    运用分块的优越性质：分块可以实现 O(1) 插入， O(√n) 查询。或者 O(√n) 插入 O(1) 查询。

    莫队需要大量的插入操作，这使得复杂度均匀为 O(logn) 的 bit 难以承受。

    这到题，对值域分块，实现 O(1) 插入 O(√n) 查询，总共 O((n+m)√n)

    1. #include 
    2. using namespace std;
    3. typedef unsigned long long uLL;
    4. typedef long double LD;
    5. typedef long long LL;
    6. typedef double db;
    7. const int N = 100005, M = 1000005, SQ = 1005;
    8. int n, m, a[N], Bsz, Btot, pos[N], pl[SQ], pr[SQ];
    9. int L, R, ans[M], cnt[N], sm[SQ];
    10. struct qry { int l, r, a, b, id; } q[M];
    11. inline bool cmp(qry A, qry B) {
    12.     if (pos[A.l] ^ pos[B.l]) return pos[A.l] < pos[B.l];
    13.     return A.r < B.r;
    14. }
    15. inline void add(int x) {
    16.     if (!cnt[x]++) ++sm[pos[x]];
    17. }
    18. inline void del(int x) {
    19.     if (!--cnt[x]) --sm[pos[x]];
    20. }
    21. inline int ask(int l, int r) {
    22.     register int p = pos[l], q = pos[r], re = 0;
    23.     if (p == q) {
    24.         for (int i = l; i <= r; i++) re += (cnt[i] > 0);
    25.         return re;
    26.     }
    27.     for (int i = l; i <= pr[p]; i++) re += (cnt[i] > 0);
    28.     for (int i = pl[q]; i <= r; i++) re += (cnt[i] > 0);
    29.     for (int i = p + 1; i < q; i++) re += sm[i];
    30.     return re;
    31. }
    32. int main() {
    33.     scanf("%d%d", &n, &m);
    34.     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    35.     for (int i = 1; i <= m; i++) scanf("%d%d%d%d", &q[i].l, &q[i].r, &q[i].a, &q[i].b), q[i].id = i;
    36.     Bsz = sqrt(n), Btot = (n - 1) / Bsz + 1;
    37.     for (int i = 1; i <= n; i++) pos[i] = (i - 1) / Bsz + 1;
    38.     for (int i = 1; i <= Btot; i++) pl[i] = pr[i - 1] + 1, pr[i] = min(n, i * Bsz);
    39.     sort(q + 1, q + m + 1, cmp);
    40.     L = 1, R = 0;
    41.     for (int i = 1, ql, qr; i <= m; i++) {
    42.         ql = q[i].l, qr = q[i].r;
    43.         while (L < ql) del(a[L++]);
    44.         while (L > ql) add(a[--L]);
    45.         while (R < qr) add(a[++R]);
    46.         while (R > qr) del(a[R--]);
    47.         ans[q[i].id] = ask(q[i].a, q[i].b);
    48.     }
    49.     for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    50. }

    [Ynoi2019] Yuno loves sqrt technology II

    [Ynoi2019 模拟赛] Yuno loves sqrt technology II

    先 % 出题人 lxl

    求区间逆序对个数。

    暴力：树状数组转移，O(n√nlogn) ，在神仙数据下只有。。20 pts

    转移复杂度神仙，考虑二次离线。

    剩下的就比较模板了，但是如果还用 bit 的话，大量的查询导致超时。

    需要记录一个向前形成的逆序对和一个向后形成的逆序对

    还记得根号平衡？用 O(√n) 插入 O(1) 查询的分块就可以了。

    1. #include 
    2. #define pb push_back
    3. using namespace std;
    4. typedef unsigned long long uLL;
    5. typedef long double LD;
    6. typedef long long LL;
    7. typedef double db;
    8. const int N = 100005, SQ = 325;
    9. int n, m, a[N], b[N], Tb, pl[SQ], pr[SQ], po[N], Bsz, Btot;
    10. int s1[SQ], s2[SQ], t1[N], t2[N];
    11. LL pre1[N], pre2[N], ans[N], out[N];
    12. // 1 : front
    13. // 2 : back
    14. struct qry { int l, r, id; } q[N];
    15. struct mdy { int l, r, id, op, vl; } nw;
    16. vector d[N];
    17. inline bool cmp(qry A, qry B) {
    18.     if (po[A.l] ^ po[B.l]) return po[A.l] < po[B.l];
    19.     if (po[A.l] & 1) return A.r < B.r;
    20.     return A.r > B.r;
    21. }
    22. inline void clear() {
    23.     memset(s1, 0, sizeof(s1)), memset(t1, 0, sizeof(t1));
    24.     memset(s2, 0, sizeof(s2)), memset(t2, 0, sizeof(t2));
    25. }
    26. inline void add(int x) {
    27.     register int p = po[x];
    28.     for (int i = 1; i < p; i++) ++s1[i];
    29.     for (int i = p + 1; i <= Btot; i++) ++s2[i];
    30.     for (int i = pl[p]; i < x; i++) ++t1[i];
    31.     for (int i = x + 1; i <= pr[p]; i++) ++t2[i];
    32. }
    33. inline int ask1(int x) { return s1[po[x]] + t1[x]; }
    34. inline int ask2(int x) { return s2[po[x]] + t2[x]; }
    35. int main() {
    36.     scanf("%d%d", &n, &m);
    37.     for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
    38.     sort(b + 1, b + n + 1), Tb = unique(b + 1, b + n + 1) - b - 1;
    39.     for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + Tb + 1, a[i]) - b;
    40.     Bsz = sqrt(n);
    41.     for (int i = 1; i <= n; i++) po[i] = (i - 1) / Bsz + 1;
    42.     Btot = po[n];
    43.     for (int i = 1; i <= Btot; i++) pl[i] = pr[i - 1] + 1, pr[i] = i * Bsz;
    44.     pr[Btot] = n;
    45.     for (int i = 1; i <= m; i++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
    46.     sort(q + 1, q + m + 1, cmp);
    47.     for (int i = 1; i <= n; i++) {
    48.         pre1[i] = pre1[i - 1] + ask1(a[i]);
    49.         pre2[i] = pre2[i - 1] + ask2(a[i]);
    50.         add(a[i]);
    51.     }
    52.     for (int i = 1, ql, qr, L = 1, R = 0; i <= m; i++) {
    53.         ql = q[i].l, qr = q[i].r;
    54.         ans[i] = pre2[ql - 1] - pre2[L - 1] + pre1[qr] - pre1[R];
    55.         if (L < ql) d[qr].pb((mdy){ L, ql - 1, i, 1,-1 });
    56.         if (L > ql) d[qr].pb((mdy){ ql, L - 1, i, 1, 1 });
    57.         if (R < qr) d[L - 1].pb((mdy){ R + 1, qr, i, 0,-1 });
    58.         if (R > qr) d[L - 1].pb((mdy){ qr + 1, R, i, 0, 1 });
    59.         L = ql, R = qr;
    60.     }
    61.     clear();
    62.     for (int i = 1; i <= n; i++) {
    63.         add(a[i]);
    64.         for (int j = 0, Lj = d[i].size(); j < Lj; j++) {
    65.             nw = d[i][j];
    66.             register LL tmp = 0;
    67.             for (int k = nw.l; k <= nw.r; k++) {
    68.                 if (nw.op) tmp += ask2(a[k]);
    69.                 else tmp += ask1(a[k]);
    70.             }
    71.             ans[nw.id] += tmp * nw.vl;
    72.         }
    73.     }
    74.     for (int i = 1; i <= m; i++) ans[i] += ans[i - 1], out[q[i].id] = ans[i];
    75.     for (int i = 1; i <= m; i++) printf("%lld\n", out[i]);
    76. }

    [Ynoi2015] 此时此刻的光辉

    [Ynoi2015] 此时此刻的光辉

    求区间内所有数乘积的约数个数 (mod19260817)

    n≤105,ai≤109

    用约数个数定理计算，Pollard-Rho 分解质因数后莫队可以直接算贡献。

    却发现： 109 级别的质数个数，难以保证复杂度。

    想到一个定理：一个数 v 只会有最多一个 ≥√v 的质因子。

    预处理出 ≤√v 的质数，然后求前缀和？

    又发现：√109 约等于 31622 ，大约有 3401 个质数，查询和预处理都是 O(3401n) ，难以接受。

    扩展一下那个定理：一个数 v 最多只会有两个 ≥3√v 的质因子。

    而 3√109=1000 ，大约只有 168 个质数， O(168n) 的预处理是可行的。

    剩下的两个因子，用调用一次 PR 就可以了，不要写 dfs ，否则被卡常。

    将大于 1000 的因子存下来，离散化是必然的

    由于一个数剩下最多两个因子，保证莫队更新的复杂度为 O(1) ， ≤1000 的因子用前缀和查询即可

    卡常难度在 PR ，主要是我的 MR 是 O(log2) 的。。。

    注意预处理逆元需要预处理到 2n ，每个数会有两个 ≥1000 的质因子

    1. #include 
    2. using namespace std;
    3. typedef unsigned long long uLL;
    4. typedef long double LD;
    5. typedef long long LL;
    6. typedef double db;
    7. char buf[100000], *S = buf, *T = buf;
    8. inline char Gc() {
    9.     return S == T && (T = (S = buf) + fread(buf, 1, 100000, stdin), S == T) ? EOF : *S++;
    10. }
    11. inline int Rd() {
    12.     register int x = 0, C = Gc();
    13.     for (; C < '0' || C > '9'; C = Gc()) ;
    14.     for (; C > '/' && C < ':'; C = Gc()) x = (x << 1) + (x << 3) + (C ^ 48);
    15.     return x;
    16. }
    17. inline int Pow(int x, int y, int p) {
    18.     register int res = 1;
    19.     for (; y; y >>= 1, x = 1ll * x * x % p)
    20.         if (y & 1) res = 1ll * res * x % p;
    21.     return res;
    22. }
    23. inline bool Mr(LL n, LL p) {
    24.     if (Pow(p, n - 1, n) != 1) return 0;
    25.     register LL q = n - 1, o;
    26.     while (!(q & 1)) {
    27.         q >>= 1, o = Pow(p, q, n);
    28.         if (o != 1 && o != n - 1) return 0;
    29.         if (o == n - 1) return 1;
    30.     }
    31.     return 1;
    32. }
    33. inline bool Prime(int n) {
    34.     if (n < 2) return false;
    35.     if (n == 2 || n == 3 || n == 5 || n == 7 || n == 43) return true;
    36.     return Mr(n, 2) && Mr(n, 3) && Mr(n, 5) && Mr(n, 7) && Mr(n, 43);
    37. }
    38. int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
    39. inline int Rho(int n) {
    40.     register int p, q, x, y, z, c, g;
    41.     for (;;) {
    42.         x = y = rand() % n, c = rand() % n;
    43.         p = 0, q = z = 1;
    44.         while (++p) {
    45.             x = (1ll * x * x % n + c) % n;
    46.             z = 1ll * z * abs(y - x) % n;
    47.             if (x == y || !z) break;
    48.             if (!(p % 127) || p == q) {
    49.                 g = gcd(z, n);
    50.                 if (g > 1) return g;
    51.                 if (p == q) q <<= 1, y = x;
    52.             }
    53.         }
    54.     }
    55. }
    56. const int P = 19260817, N = 2e5 + 5;
    57. int n, m, id[1005], Pcnt, pr[1005], s[N][1005], a[N], b[N], Bsz, ans[N], now, inv[N], tt[N], pp[N], Pl;
    58. struct qry { int l, r, id; } q[N];
    59. inline bool cmp(qry A, qry B) {
    60.     if (A.l / Bsz != B.l / Bsz) return A.l < B.l;
    61.     return (A.l / Bsz) & 1 ? A.r > B.r : A.r < B.r;
    62. }
    63. inline void ad(int v) { now = 1ll * now * inv[tt[v]] % P * (tt[v] + 1) % P, tt[v]++; }
    64. inline void dl(int v) { now = 1ll * now * inv[tt[v]] % P * (tt[v] - 1) % P, tt[v]--; }
    65. inline void add(int p) { if (a[p]) ad(a[p]); if (b[p]) ad(b[p]); }
    66. inline void del(int p) { if (a[p]) dl(a[p]); if (b[p]) dl(b[p]); }
    67. int main() {
    68.     for (int i = 1; i <= 1000; i++) id[i] = 1;
    69.     for (int i = 2; i <= 1000; i++) {
    70.         if (!id[i]) continue; pr[id[i] = ++Pcnt] = i;
    71.         for (int j = i + i; j <= 1000; j += i) id[j] = 0;
    72.     }
    73.     inv[1] = 1;
    74.     for (int i = 2; i <= 200000; i++)
    75.         inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
    76.     n = Rd(), m = Rd();
    77.     for (int i = 1, x, y; i <= n; i++) {
    78.         x = Rd();
    79.         memcpy(s[i], s[i - 1], sizeof(s[i]));
    80.         for (int j = 1; j <= Pcnt && pr[j] * pr[j] <= x; j++)
    81.             while (x % pr[j] == 0) x /= pr[j], s[i][j]++;
    82.         if (x > 1) {
    83.             if (x <= pr[Pcnt]) ++s[i][id[x]];
    84.             else {
    85.                 if (!Prime(x))
    86.                     b[i] = pp[++Pl] = y = Rho(x), x /= y;
    87.                 if (x > 1) a[i] = x, pp[++Pl] = x;
    88.             }
    89.         }
    90.     }
    91.     sort(pp + 1, pp + Pl + 1);
    92.     Pl = unique(pp + 1, pp + Pl + 1) - pp - 1;
    93.     for (int i = 1; i <= n; i++) {
    94.         if (a[i]) a[i] = lower_bound(pp + 1, pp + Pl + 1, a[i]) - pp;
    95.         if (b[i]) b[i] = lower_bound(pp + 1, pp + Pl + 1, b[i]) - pp;
    96.     }
    97.     Bsz = sqrt(n);
    98.     for (int i = 1; i <= m; i++) q[i].l = Rd(), q[i].r = Rd(), q[i].id = i;
    99.     sort(q + 1, q + m + 1, cmp);
    100.     for (int i = 1; i <= n * 2; i++) tt[i] = 1;
    101.     int L = 1, R = 0;
    102.     now = 1;
    103.     for (int i = 1, ql, qr; i <= m; i++) {
    104.         ql = q[i].l, qr = q[i].r;
    105.         while (L > ql) add(--L);
    106.         while (R < qr) add(++R);
    107.         while (L < ql) del(L++);
    108.         while (R > qr) del(R--);
    109.         ans[q[i].id] = now;
    110.         for (int j = 1; j <= Pcnt; j++)
    111.             ans[q[i].id] = 1ll * ans[q[i].id] * (s[qr][j] - s[ql - 1][j] + 1) % P;
    112.     }
    113.     for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    114. }

    [Ynoi2015] 盼君勿忘

    [Ynoi2015] 盼君勿忘

    莫队只是工具，以思维难度为主。

    求区间内子序列分别取重后的和 (modp)

    假设数 x 在区间 [l,r] 内出现 k 次，那么包含 x 的子序列有 2r−l+1−2r−l+1−k 个

    所以 x 的贡献就是 x×(2r−l+1−2r−l+1−k)

    设 si 为出现次数为 i 的和， cnti 为数 i 出现次数。

    双向链表维护出现次数为 i 的数的和，不同的 i 值最多 √n 个。遍历一次链表可以算出答案。

    复杂度为 O((n+m)√n)

    光速幂

    每一个询问模数不同，快速幂？平白多处一个 log ？预处理？直接 O(n) ？

    引出黑科技：光速幂。

    对于每一个询问，预处理 20,21,⋯,2√n−1 和 2√n,22√n,⋯,2n

    求一个 2p ，用 p=k√n+l(0≤l<√n) 计算即可。

    预处理 O(√n) ，查询 O(1)

    1. #include 
    2. #define pb push_back
    3. using namespace std;
    4. typedef unsigned long long uLL;
    5. typedef long double LD;
    6. typedef long long LL;
    7. typedef double db;
    8. char buf[100000], *S = buf, *T = buf;
    9. inline char Gc() {
    10.     return S == T && (T = (S = buf) + fread(buf, 1, 100000, stdin), S == T) ? EOF : *S++;
    11. }
    12. inline int rd() {
    13.     register int x = 0;
    14.     static char C = Gc();
    15.     for (; C < '0' || x > '9'; C = Gc()) ;
    16.     for (; C > '/' && C < ':'; C = Gc()) x = (x << 1) + (x << 3) + (C ^ 48);
    17.     return x;
    18. }
    19. const int N = 100005;
    20. int n, m, a[N], Bsz, Btot, po[N], L = 1, R = 0;
    21. int pre[N], nxt[N], Ed;
    22. LL sm[N], ans[N], cnt[N], p1[N], p2[N], v1, v2;
    23. struct qry { int l, r, p, id; } q[N];
    24. inline bool cmp(qry A, qry B) {
    25.     if (po[A.l] ^ po[B.l]) return po[A.l] < po[B.l];
    26.     if (po[A.l] & 1) return A.r < B.r;
    27.     return A.r > B.r;
    28. }
    29. inline void ins(int x) {
    30.     nxt[Ed] = x, pre[x] = Ed, Ed = x;
    31. }
    32. inline void dlt(int x) {
    33.     if (x != Ed) nxt[pre[x]] = nxt[x], pre[nxt[x]] = pre[x];
    34.     else nxt[pre[x]] = 0, Ed = pre[x];
    35.     pre[x] = nxt[x] = 0;
    36. }
    37. inline int pow2(int x, int P) {
    38.     return p2[x / Bsz] * p1[x % Bsz] % P;
    39. }
    40. inline void add(int x) {
    41.     sm[cnt[x]] -= x;
    42.     if (!sm[cnt[x]]) dlt(cnt[x]);
    43.     ++cnt[x];
    44.     if (!sm[cnt[x]]) ins(cnt[x]);
    45.     sm[cnt[x]] += x;
    46. }
    47. inline void del(int x) {
    48.     sm[cnt[x]] -= x;
    49.     if (!sm[cnt[x]]) dlt(cnt[x]);
    50.     --cnt[x];
    51.     if (!sm[cnt[x]]) ins(cnt[x]);
    52.     sm[cnt[x]] += x;
    53. }
    54. inline void init(int P) {
    55.     p1[0] = p2[0] = 1;
    56.     for (int i = 1; i <= Bsz; i++)
    57.         p1[i] = 2 * p1[i - 1] % P;
    58.     for (int i = 1; i <= Btot; i++)
    59.         p2[i] = p2[i - 1] * p1[Bsz] % P;
    60. }
    61. int main() {
    62.     n = rd(), m = rd(), Bsz = sqrt(n);
    63.     for (int i = 1; i <= n; i++) a[i] = rd(), po[i] = (i - 1) / Bsz + 1;
    64.     Btot = po[n];
    65.     for (int i = 1; i <= m; i++) q[i] = (qry){ rd(), rd(), rd(), i };
    66.     sort(q + 1, q + m + 1, cmp);
    67.     for (int i = 1, ql, qr, P; i <= m; i++) {
    68.         ql = q[i].l, qr = q[i].r, P = q[i].p;
    69.         init(P);
    70.         while (L < ql) del(a[L++]);
    71.         while (L > ql) add(a[--L]);
    72.         while (R < qr) add(a[++R]);
    73.         while (R > qr) del(a[R--]);
    74.         for (int j = nxt[0]; j; j = nxt[j]) {
    75.             v1 = pow2(qr - ql + 1, P);
    76.             v2 = pow2(qr - ql + 1 - j, P);
    77.             (ans[q[i].id] += sm[j] * (v1 - v2 + P) % P) %= P;
    78.         }
    79.     }
    80.     for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
    81. }

    『MdOI R1』Path

    『MdOI R1』Path

    trie 显然。

    结论：对于两条不相交的路径，存在一点 u 使得一条路径在子树 u 内，一条在子树外。

    转为 dfs 序，将数组复制一份，对于每一个 u ，相当于两个询问。

    由于是求 max ，用只增不减的回滚莫队即可。

    O(n√nlogw)

    1. #include 
    2. using namespace std;
    3. typedef unsigned long long uLL;
    4. typedef long double LD;
    5. typedef long long LL;
    6. typedef double db;
    7. const int N = 100005;
    8. int n, lst[N], Ecnt, xo[N], dfn[N], clk, sz[N], unit, pos[N], Btot, pr[N], tq, dis[N];
    9. int ch[N * 30][2], tg[N * 30], Ttot, L, R, now, tmp, ans[N], out, cur, ed[N], rk[N];
    10. struct Ed { int to, nxt, qz; } e[N << 1];
    11. inline void Ae(int fr, int go, int vl) {
    12.     e[++Ecnt] = (Ed){ go, lst[fr], vl }, lst[fr] = Ecnt;
    13. }
    14. struct qry {
    15.     int l, r, id;
    16. } q[N];
    17. inline bool cmp(qry A, qry B) {
    18.     if (pos[A.l] ^ pos[B.l]) return pos[A.l] < pos[B.l];
    19.     return A.r < B.r;
    20. }
    21. void dfs(int u, int ff) {
    22.     dfn[u] = ++clk, rk[clk] = u, sz[u] = 1;
    23.     for (int i = lst[u], v; i; i = e[i].nxt)
    24.         if ((v = e[i].to) ^ ff)
    25.             dis[v] = dis[u] ^ e[i].qz, dfs(v, u), sz[u] += sz[v];
    26. 	ed[u] = clk;
    27. }
    28. inline void ins(int x) {
    29.     register int u = 0;
    30.     for (int i = 30, s; ~i; i--) {
    31.         s = (x >> i) & 1;
    32.         if (!ch[u][s]) ch[u][s] = ++Ttot;
    33.         u = ch[u][s], ++tg[u];
    34.     }
    35. }
    36. inline int ask(int x) {
    37.     register int u = 0, re = 0;
    38.     for (int i = 30, s; ~i; i--) {
    39.         s = (x >> i) & 1;
    40.         if (!tg[ch[u][s ^ 1]]) u = ch[u][s];
    41.         else u = ch[u][s ^ 1], re |= 1 << i;
    42.     }
    43.     return re;
    44. }
    45. inline void cancel(int x) {
    46.     register int u = 0;
    47.     for (int i = 30, s; ~i; i--) {
    48.         s = (x >> i) & 1;
    49.         u = ch[u][s], --tg[u];
    50.     }
    51. }
    52. int main() {
    53.     scanf("%d", &n);
    54.     for (int i = 1, u, v, w; i < n; i++) {
    55.         scanf("%d%d%d", &u, &v, &w);
    56.         Ae(u, v, w), Ae(v, u, w);
    57.     }
    58.     dfs(1, 0);
    59.     for (int i = 2; i <= n; i++) {
    60.         q[++tq] = (qry){ dfn[i], ed[i], i };
    61.         q[++tq] = (qry){ ed[i] + 1, dfn[i] + n - 1, i };
    62.     }
    63.     for (int i = 1; i <= n; i++) xo[i] = xo[i + n] = dis[rk[i]];
    64.     n <<= 1, unit = sqrt(n), Btot = n / unit;
    65.     for (int i = 1; i <= n; i++) pos[i] = (i - 1) / unit + 1;
    66.     for (int i = 1; i <= Btot; i++) pr[i] = i * unit;
    67.     if (pr[Btot] < n) pr[++Btot] = n;
    68.     sort(q + 1, q + tq + 1, cmp);
    69.     // init
    70. 	L = 1, R = 0;
    71.     for (int i = 1, ql, qr; i <= tq; i++) {
    72.         ql = q[i].l, qr = q[i].r;
    73.         if (cur ^ pos[ql]) {
    74.             cur = pos[ql], now = 0;
    75.             while (L <= R) cancel(xo[L++]);
    76.             L = pr[cur] + 1, R = pr[cur];
    77.         }
    78.         if (pos[ql] == pos[qr]) {
    79.             tmp = 0;
    80.             for (int j = ql; j <= qr; j++) ins(xo[j]);
    81. 			for (int j = ql; j <= qr; j++) tmp = max(tmp, ask(xo[j]));
    82.             for (int j = ql; j <= qr; j++) cancel(xo[j]);
    83.             ans[q[i].id] += tmp;
    84.             continue;
    85.         }
    86.         while (R < qr) ins(xo[++R]), now = max(now, ask(xo[R]));
    87.         tmp = now;
    88.         while (L > ql) ins(xo[--L]), now = max(now, ask(xo[L]));
    89.         while (L < pr[cur] + 1) cancel(xo[L++]);
    90.         ans[q[i].id] += now, now = tmp;
    91.     }
    92.     for (int i = 2; i <= n; i++) out = max(out, ans[i]);
    93.     printf("%d\n", out);
    94. }
  • 相关阅读:
    两步将 CentOS 6.0 原地升级并迁移至 RHEL 7.9
    性能优化--string 字符串拼接（超详细）
    主动人机交互与被动人机交互
    .net对接阿里云CSB服务
    java毕业设计云端存储的待办清单的设计Mybatis+系统+数据库+调试部署
    C++ 的int*p[]和int(*p)[]的区别
    青少年软件编程C++一级题库(31-40)
    算法分析与设计CH8：线性时间的排序——计数排序、基数排序、桶排序
    eBay买家号注册下单容易死号？是什么原因导致？
    NVIDIA CUDA Toolkit
  • 原文地址：https://blog.csdn.net/KonjakuLAF/article/details/126387244