BZOJ3236 [Ahoi2013]作業

昨天晚上做的。。。差錯一直查到今天= =

最后沒辦法問管理員要了數據才知道原來ans數組開小了233，簡直沙茶

?

這道題不就是裸的莫隊嘛= =|||

只要用樹狀數組維護當前的兩種個數即可。

?

/**************************************************************
    Problem: 3236
    User: rausen
    Language: C++
    Result: Accepted
    Time:79318 ms
    Memory:66252 kb
****************************************************************/
 
#include <cstdio>
#include <cmath>
#include <algorithm>
 
#define lowbit(x) x & -x
using namespace std;
const int N = 100005;
const int M = 1000005;
const int Maxlen = 37000005;
 
int n, size, Q;
int BIT[2][N], cnt[N], pos[N], a[N];
int ans1[M], ans2[M];
int Len, Left;
char buf[Maxlen];
 
struct Query {
    int l, r, a, b, w;
} q[M];
inline bool operator < (const Query &a, const Query &b) {
    return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];
}
inline bool cmp_id (const Query &a, const Query &b) {
    return a.w < b.w;
}
 
inline int read() {
    int x = 0;
    while (buf[Left] < '0' || '9' < buf[Left])
        ++Left;
    while ('0' <= buf[Left] && buf[Left] <= '9')
        x = x * 10 + buf[Left++] - '0';
    return x;
}
 
int len = 0, pr[15];
inline void print(int x) {
    while (x)
        pr[++len] = x % 10, x /= 10;
    if (!len) putchar('0');
    while (len)
        putchar(pr[len--] + '0');
}
 
inline void update(int x, int del, int T) {
    while (x <= n)
        BIT[T][x] += del, x += lowbit(x);
}
 
inline int query(int x, int T) {
    int res = 0;
    while (x)
        res += BIT[T][x], x -= lowbit(x);
    return res;
}
 
inline void update(int x, int del) {
    if (!cnt[x])
        update(x, 1, 1);
    cnt[x] += del;
    if (!cnt[x])
        update(x, -1, 1);
    update(x, del, 0);
}
 
int main() {
    int i, l, r;
    Len = fread(buf, 1, Maxlen, stdin);
    buf[Len] = ' ';
    n = read(), Q = read();
    size = (int) sqrt(n);
    for (i = 1; i <= n; ++i)
        a[i] = read(), pos[i] = i / size;
    for (i = 1; i <= Q; ++i) {
        q[i].l = read(), q[i].r = read();
        q[i].a = read(), q[i].b = read();
        q[i].w = i;
    }
     
    sort(q + 1, q + Q + 1);
    for (i = l = 1, r = 0; i <= Q; ++i) {
        for (; r < q[i].r; ) update(a[++r], 1);
        for (; r > q[i].r; ) update(a[r--], -1);
        for (; l < q[i].l; ) update(a[l++], -1);
        for (; l > q[i].l; ) update(a[--l], 1);
        ans1[q[i].w] = query(q[i].b, 0) - query(q[i].a - 1, 0);
        ans2[q[i].w] = query(q[i].b, 1) - query(q[i].a - 1, 1);
    }
    for (i = 1; i <= Q; ++i) {
        print(ans1[i]), putchar(' ');
        print(ans2[i]), putchar('\r'), putchar('\n');
    }
    return 0;
}

（p.s. 這道題Rank 1的5 sec是怎么做到的= =，蒟蒻可是用了80 sec啊！！！）