[BZOJ2120] 数颜色 && [bzoj2453] 维护队列（莫队 || 分块）

传送门

只有第一个，第二个权限题。

分块，然而wa，没看出来错在哪里，有时间再看。

1 #include <cmath> 2 #include <cstdio> 3 #include <iostream> 4 #include <algorithm> 5 6 const int N = 10001, M = 1000001; 7 8 int n, m, S, C; 9 int a[N], st[N], ed[N], belong[N], pre[N], last[M], c[N]; 10 11 inline int read() 12 19 20 inline int min(int x, int y) 21 24 25 inline int find(int x, int y, int z) 26 34 return x l; 35 } 36 37 inline void reset(int x) 38 43 44 inline void init() 45 56 for(i = 1; i <= n; i += S) 57 st[++C] = i, ed[C] = min(i + S 1, n); 58 for(i = 1; i <= C; i++) 59 } 64 65 inline int query(int x, int y) 66 74 //ans += std::lower_bound(c + x, c + ed[l] + 1, x) c x; 75 for(i = x; i <= ed[l]; i++) if(c[i] < x) ans++; 76 for(i = l + 1; i <= r 1; i++) ans += find(st[i], ed[i] + 1, x); 77 //ans += std::lower_bound(c + st[r], c + y + 1, x) c st[r]; 78 for(i = st[r]; i <= y; i++) if(c[i] < x) ans++; 79 return ans; 80 } 81 82 inline void update(int x, int d) 83 94 } 95 96 inline void work() 97 108 } 109 110 int main() 111
View Code

莫队

比分块不知道高到哪里去了。

带修改之后真是。。。。

1 #include <cmath> 2 #include <cstdio> 3 #include <iostream> 4 #include <algorithm> 5 6 const int N = 10001, M = 1e6 + 5; 7 int n, Q, S, cnt1, cnt2, cur, l = 1, r, now; 8 int a[N], t[N], belong[N], ans[N], c[M]; 9 10 struct ovo 11 14 }q[N]; 15 struct qwq 16 19 }cq[N]; 20 21 inline int read() 22 29 30 inline bool cmp(ovo x, ovo y) 31 34 35 inline void add(int x) 36 39 40 inline void del(int x) 41 44 45 inline void update(int x, int d) 46 50 51 int main() 52 67 std::sort(q + 1, q + cnt1 + 1, cmp); 68 for(i = 1; i <= cnt1; i++) 69 78 for(i = 1; i <= cnt1; i++) printf("%d\n", ans[i]); 79 return 0; 80 }
View Code

上一篇：[luoguP1433] 吃奶酪（DP || Dfs）

下一篇：[luoguP2758] 编辑距离（DP）

---

分块 莫队