【模板】分块

【模板】分块

两个操作，1是询问[l,r]颜色的数量，2是交换p,p+1位置的颜色. #include #include #include #include #include using namespace std; int n, m, a[600][50010], b[300010], block, l[600], r[600], pos[300010], cnt, vis[300010]; bool flag = true; void update(int cur) { int t = b[cur], t2 = b[cur + 1]; swap(b[cur], b[cur + 1]); int p1 = pos[cur], p2 = pos[cur + 1]; a[p1][t]--; a[p2][t]++; a[p1][t2]++; a[p2][t2]--; } int query(int ll, int rr, int c) { int L = pos[ll], R = pos[rr], res = 0; if (L >= R - 1) { for (int i = ll; i <= rr; i++) if (b[i] == c) res++; return res; } for (int i = L + 1; i <= R - 1; i++) res += a[i][c]; for (int i = ll; i <= r[L]; i++) if (b[i] == c) res++; for (int i = l[R]; i <= rr; i++) if (b[i] == c) res++; return res; } int main() { scanf("%d%d", &n, &m); block = sqrt(n); for (int i = 1; i <= n; i++) pos[i] = (i - 1) / block + 1; cnt = (n - 1) / block + 1; for (int i = 1; i <= cnt; i++) l[i] = r[i - 1] + 1, r[i] = min(block * i, n); for (int i = 1; i <= n; i++) { int t; scanf("%d", &t); a[pos[i]][t]++; b[i] = t; } while (m--) { int op, l, r, c; scanf("%d", &op); if (op == 1) { scanf("%d%d%d", &l, &r, &c); printf("%d\n", query(l, r, c)); } else { scanf("%d", &c); update(c); } } return 0; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。