首页 > 代码库 > BZOJ2743 [HEOI2012]采花

BZOJ2743 [HEOI2012]采花

2024-08-07 21:18:27   217人阅读

本来想做这道题的。。。后来发现根本搞不懂

于是又滚回了BZOJ 1878搞了搞。。。

发现这道题和1878差不多，只是要注意update的时候要加个next

其实我们可以推广到3个、4个、5个（貌似可以用倍增？感觉可以出一道题呢、、、）

然后就没有然后啦~，不要问我为什么用了fread。。。只是无聊了≥v≤~

 

 1 /************************************************************** 2     Problem: 2743 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:3940 ms 7     Memory:56472 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <algorithm>12  13 #define lowbit(x) x & -x14 using namespace std;15 const int N = 1000005;16 const int Maxlen = 25 * N;17 struct data{18     int l, r, w;19     inline bool operator < (const data &x) const {20         return l == x.l ? r < x.r : l < x.l;21     }22 } q[N];23  24 int n, m, c;25 int a[N], next[N], first[N];26 int BIT[N];27 int ans[N];28  29 char buf[Maxlen], *C = buf;30 int Len;31 inline int read() {32     int x = 0;33     while (*C < ‘0‘ || ‘9‘ < *C) ++C;34     while (‘0‘ <= *C && *C <= ‘9‘)35         x = x * 10 + *C - ‘0‘, ++C;36     return x;37 }38  39 int L, pr[10];40 void print(int x) {41     if (!x) {42         puts("0");43         return;44     }45     while (x)46         pr[++L] = x % 10, x /= 10;47     while (L)48         putchar(pr[L--] + ‘0‘);49     putchar(‘\n‘);50 }51  52 void update(int x, int v) {53     if (!x) return;54     while (x <= n)55         BIT[x] += v, x += lowbit(x);56 }57   58 int query(int x) {59     int res = 0;60     while (x)61         res += BIT[x], x -= lowbit(x);62     return res;63 }64  65 int main() {66     int i, l;67     Len = fread(C, 1, Maxlen, stdin);68     buf[Len] = ‘\0‘;69     n = read(), c = read(), m = read();70     for (i = 1; i <= n; ++i)71         a[i] = read();72     for (i = n; i; --i)73         next[i] = first[a[i]], first[a[i]] = i;74     for (i = 1; i <= c; ++i)75         update(next[first[i]], 1);76  77     for (i = 1; i <= m; ++i)78         q[i].l = read(), q[i].r = read(), q[i].w = i;79     sort(q + 1, q + m + 1);80     for (i = l = 1; i <= m; ++i) {81         for (; l < q[i].l; ++l)82             update(next[l], -1), update(next[next[l]], 1);83         ans[q[i].w] = query(q[i].r) - query(q[i].l - 1);84     }85     for (i = 1; i <= m; ++i)86         print(ans[i]);87     return 0;88 }
View Code

 

BZOJ2743 [HEOI2012]采花


联系
我们