Luogu 4867 Gty的二逼妹子序列

BZOJ3809，是权限题。

我永远喜欢莫队。

先莫队一下移下左右指针，然后用一个数据结构维护一下区间$[a, b]$中的颜色的值，跟着指针移动一起修改修改，每一次$query$的时候就相当于查询一下$[a, b]$中的和。

其实可以直接对颜色进行分块，维护一下块内的值以及每一个位置的答案，每一次修改是$O(1)$的，每一次查询是$O(\sqrt{n})$的，因为总共要进行$m$次查询，所以总的时间复杂度是$O((n + m)\sqrt{n})$，这样写可以比树状数组以及其他的数据结构少一个$log$。

然而这个$log$在你谷上跑的飞快……

最近真是颓了。

Code：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 1e5 + ;

const int M = 1e6 + ;

int n, qn, a[N], blo, ans[N];

int cnt[N], bel[N], ln[N], rn[N];

struct Querys {

    int l, r, st, ed, id, ans;

} q[M];

bool cmp(const Querys &x, const Querys &y) {

    if(bel[x.l] == bel[y.l]) return x.r < y.r;

    else return x.l < y.l;

}

inline void read(int &X) {

    X = ; char ch = ; int op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

inline int query(int st, int ed) {

    int res = ;

    if(bel[st] == bel[ed]) {

        for(int i = st; i <= ed; i++)

            if(cnt[i]) res++;

    } else {

        for(int i = st; i <= rn[bel[st]]; i++)

            if(cnt[i]) res++;

        for(int i = ln[bel[ed]]; i <= ed; i++)

            if(cnt[i]) res++;

        for(int i = bel[st] + ; i <= bel[ed] - ; i++)

            res += ans[i];

    }

    return res;

}

inline void add(int x) {

    ++cnt[a[x]];

    if(cnt[a[x]] == ) ans[bel[a[x]]]++;

}

inline void del(int x) {

    --cnt[a[x]];

    if(cnt[a[x]] == ) ans[bel[a[x]]]--;

}

inline void solve() {

    sort(q + , q +  + qn, cmp);

    for(int l = , r = , i = ; i <= qn; i++) {

        for(; l < q[i].l; del(l++));

        for(; l > q[i].l; add(--l));

        for(; r < q[i].r; add(++r));

        for(; r > q[i].r; del(r--));

        q[q[i].id].ans = query(q[i].st, q[i].ed);

    }

}

int main() {

    read(n), read(qn);

    for(int i = ; i <= n; i++) read(a[i]);

    blo = sqrt(n);

    for(int i = ; i <= blo; i++) {

        ln[i] = (i - ) * blo + ;

        rn[i] = i * blo;

    }

    if(rn[blo] < n)

        ++blo, ln[blo] = rn[blo - ] + , rn[blo] = n;

    for(int i = ; i <= blo; i++) {

        for(int j = ln[i]; j <= rn[i]; j++)

            bel[j] = i;

    }

    for(int i = ; i <= qn; i++) {

        read(q[i].l), read(q[i].r), read(q[i].st), read(q[i].ed);

        q[i].id = i;

    }

    solve();

    for(int i = ; i <= qn; i++)

        printf("%d\n", q[i].ans);

    return ;

}

巴特西

Luogu 4867 Gty的二逼妹子序列

最新文章

热门文章