首页 > 代码库 > BZOJ3809 Gty的二逼妹子序列
BZOJ3809 Gty的二逼妹子序列
终于做到了BZ上最新的题2333
这题一看就是。。。莫队，然后查询的时候树状数组。
结果T了，诶诶诶诶%>_<%，怎么可以这样！
另寻他法：hzwer的分块
恩恩，就是把颜色分成n块，然后单词修改O(1)，单词查询O(n / sz + 2 * sz)
sz = sqrt(n / 2)的时候最好（理论上），实际上sz = sqrt(n)一点都不慢。。。。要不要下次试试sz = log(n)
1 /************************************************************** 2 Problem: 3809 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:26248 ms 7 Memory:25428 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13 14 using namespace std;15 const int N = 100005;16 const int M = 1000005;17 const int sqrt_N = 500;18 19 int n, Q, sz;20 int a[N];21 int B[sqrt_N], w[N], cnt[N];22 int ans[M];23 24 struct data {25 int l, r, a, b, W;26 27 inline bool operator < (const data &x) const {28 return w[l] == w[x.l] ? r < x.r : w[l] < w[x.l];29 }30 } q[M];31 32 inline int read() {33 int x = 0;34 char ch = getchar();35 while (ch < ‘0‘ || ‘9‘ < ch)36 ch = getchar();37 while (‘0‘ <= ch && ch <= ‘9‘) {38 x = x * 10 + ch - ‘0‘;39 ch = getchar();40 }41 return x;42 }43 44 int query(int x, int y) {45 int res = 0, i;46 if (w[x] == w[y]) {47 for (i = x; i <= y; ++i)48 if (cnt[i]) ++res;49 } else {50 for (i = w[x] + 1; i < w[y]; ++i)51 res += B[i];52 for (i = w[x] * sz; i >= x; --i)53 if (cnt[i]) ++res;54 for (i = (w[y] - 1) * sz + 1; i <= y; ++i)55 if (cnt[i]) ++res;56 }57 return res;58 }59 60 inline void add(int c, int del) {61 if (!cnt[c]) ++B[w[c]];62 cnt[c] += del;63 if (!cnt[c]) --B[w[c]];64 }65 66 int main() {67 int i, l, r;68 n = read(), Q = read(), sz = (int) sqrt(n / 2);69 for (i = 1; i <= n; ++i)70 a[i] = read(), w[i] = (int) (i - 1) / sz + 1;71 for (i = 1; i <= Q; ++i) {72 q[i].l = read(), q[i].r = read(), q[i].a = read(), q[i].b = read();73 q[i].W = i;74 }75 sort(q + 1, q + Q + 1);76 77 for (i = l = 1, r = 0; i <= Q; ++i) {78 for (; l < q[i].l; ) add(a[l++], -1);79 for (; l > q[i].l; ) add(a[--l], 1);80 for (; r < q[i].r; ) add(a[++r], 1);81 for (; r > q[i].r; ) add(a[r--], -1);82 ans[q[i].W] = query(q[i].a, q[i].b);83 }84 for (i = 1; i <= Q; ++i)85 printf("%d\n", ans[i]);86 return 0;87 }
（p.s. rank 2还不错恩，Orz rank 1写的应该不是莫队吧。。。）
update@ 2014/12/21 23:13
哇，rank 1神犇wangyisong1996主动来找蒟蒻玩耍~好开心啊
神犇说他用了卡！常！数！的莫队，时间竟然只有一半，简直给跪了>_<
另：sz = log(n)是不行了，T惨了
为何写了输出优化反倒更慢了= =不科学
BZOJ3809 Gty的二逼妹子序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。