首页 > 代码库 > BZOJ1878 [SDOI2009]HH的项链
BZOJ1878 [SDOI2009]HH的项链
我当时是怎么做的？= = 我去才3个月就忘了额Σ( ° △ °||)
今天又仔细研究了一下，才搞明白←_←
首先在线的话，就只能线段树套平衡树了吧？
我们考虑离线做法：
首先把询问按左端点排序，然后从左往右枚举左端点，并且我们要求在当前的左端点固定的情况下，还剩下的每种不同的贝壳都最靠左。（语文不好不要打我T T）
这样子我们每次到了一个区间的左端点的时候计算区间内最靠左的贝壳的个数即可。
然后讲方法。。。
我们记一个a数组，记录每个贝壳是不是当前最靠左，1表示是，0表示不是。我们发现这样子，每次枚举左端点的时候只会修改两个a值。
这样子query的复杂度太高，于是改用sum表示a的前缀和，用树状数组维护之。
（同时我们发现由于前缀和相减，于是当前左端点左边的a数组就不用管它了，于是每次只要修改一个值即可）
1 /************************************************************** 2 Problem: 1878 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:960 ms 7 Memory:8428 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <algorithm>12 13 #define lowbit(x) x & -x14 using namespace std;15 const int N = 50005;16 const int Color = 1000005;17 const int Q = 200005;18 19 struct data{20 int l, r, w;21 inline bool operator < (const data &x) const {22 return l == x.l ? r < x.r : l < x.l;23 }24 } q[Q];25 26 int n, m, mx;27 int a[N], next[N];28 int BIT[N];29 int ans[Q];30 int now[Color];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 void update(int x, int v) {45 while (x <= n)46 BIT[x] += v, x += lowbit(x);47 }48 49 int query(int x) {50 int res = 0;51 while (x)52 res += BIT[x], x -= lowbit(x);53 return res;54 }55 56 int L, pr[10];57 void print(int x) {58 if (!x) {59 puts("0");60 return;61 }62 while (x)63 pr[++L] = x % 10, x /= 10;64 while (L)65 putchar(pr[L--] + ‘0‘);66 putchar(‘\n‘);67 }68 69 int main() {70 int i, l;71 n = read();72 for (i = 1; i <= n; ++i)73 a[i] = read(), mx = max(mx, a[i]);74 for (i = n; i; --i)75 next[i] = now[a[i]], now[a[i]] = i;76 for (i = 1; i <= mx; ++i)77 if (now[i]) update(now[i], 1);78 79 m = read();80 for (i = 1; i <= m; ++i)81 q[i].l = read(), q[i].r = read(), q[i].w = i;82 sort(q + 1, q + m + 1);83 for (i = l = 1; i <= m; ++i) {84 for (; l < q[i].l; ++l)85 if (next[l]) update(next[l], 1);86 ans[q[i].w] = query(q[i].r) - query(q[i].l - 1);87 }88 for (i = 1; i <= m; ++i)89 print(ans[i]);90 return 0;91 }
BZOJ1878 [SDOI2009]HH的项链
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。