首页 > 编程语言 > 详细

【洛谷4396/BZOJ3236】[AHOI2013]作业(莫队+分块/树状数组/线段树)

时间:2018-11-14 00:30:31      阅读:208      评论:0      收藏:0      [点我收藏+]

题目:

洛谷4396

BZOJ3236(权限)

这题似乎BZOJ上数据强一些?

分析:

这题真的是……一言难尽

发现题面里没说权值的范围,怕出锅就写了离散化。后来经过面向数据编程(以及膜神犇代码)知道最大权值\(1e5\)(下文用\(M\)表示最大权值。注意如果没有这个限制,把所有数的权值和询问中提到的权值一起离散化后\(M\)也可以达到\(n+2m=2.1e6\)),如果没这个限制我很想知道正解应该怎么写……下面再细说

首先看到这种询问某个区间内在某个区域内值的数量的题,显然能想到把询问离线下来,用个什么数据结构维护莫队。

然后我大概脑补了一下,这个“数据结构”似乎可以用权值线段树?每个区间维护\(sum\)\(num\)对应两种询问。对于叶子节点,若\(sum\)\(0\)\(num\)\(0\),否则\(num\)\(1\)。对于非叶子节点,\(sum\)\(num\)都是分别是两儿子的\(sum\)/\(num\)之和。这样做正确性是显然的,复杂度\(O(m\sqrt n \times log_2M)\),大概是\(1e6\times \sqrt{1e5}\times 21\approx 6.64e9\),过个鬼哦。

树状数组做法类似。维护两个树状数组\(sum\)\(num\),同样对应两个询问。给\(a\)加的时候如果原本\(sum[a]\)\(0\)就给\(num[a]\),给\(a\)减的时候如果原本\(sum[a]\)\(1\)就给\(num[a]\)减。复杂度和线段树是一样的,所以也过不去。

然后没想到竟然分块能过……把权值分块维护,\(blsum\)\(blnum\)表示块内两种询问的答案,\(num[a]\)表示\(a\)的出现次数,维护和查询方式详见代码。

在我僵化的思维里\(log_2n\)的树状数组和线段树比\(\sqrt n\)的分块要优,但是这道题里分块的修改是\(O(1)\),查询是\(O(\sqrt M)\)。而查询不需要乘上莫队的\(O(\sqrt n)\),所以最终复杂度是\(O(m (\sqrt n+\sqrt M))\),大概是\(1e6\times(\sqrt{1e5} +\sqrt{2.1e6})=1.77e9\),还是悬。如果权值最大是\(1e5\)还是能跑过去的。

代码:

(线段树和树状数组没有AC)

线段树:\(161\)行,本地\(83\)s,内存\(100.4\)MB,BZOJ上TLE。下方代码中省略部分和树状数组基本一致

namespace Segment_Tree
{
    struct node
    {
        int sum, num;
    }tree[(N + (M << 1)) << 2];
    pii operator + (const pii &a, const pii &b)
    {
        return make_pair(a.first + b.first, a.second + b.second);
    }
    pii operator += (pii &a, const pii &b)
    {
        return a = a + b;
    }
    void update(const int rot)
    {
        tree[rot].sum = tree[rot << 1].sum + tree[rot << 1 | 1].sum;
        tree[rot].num = tree[rot << 1].num + tree[rot << 1 | 1].num;
    }
    void change(const int rot, const int lt, const int rt, const int pos, const int x)
    {
        if (lt == rt)
        {
            tree[rot].sum += x;
            tree[rot].num = (tree[rot].sum ? 1 : 0);
            return;
        }
        int mid = (lt + rt) >> 1;
        if (pos <= mid)
            change(rot << 1, lt, mid, pos, x);
        else
            change(rot << 1 | 1, mid + 1, rt, pos, x);
        update(rot);
    }
    pii query(const int rot, const int lt, const int rt, const int ls, const int rs)
    {
        if (ls <= lt && rt <= rs)
            return make_pair(tree[rot].sum, tree[rot].num);
        int mid = (lt + rt) >> 1;
        pii ans = make_pair(0, 0);
        if (ls <= mid)
            ans += query(rot << 1, lt, mid, ls, rs);
        if (rs > mid)
            ans += query(rot << 1 | 1, mid + 1, rt, ls, rs);
        return ans;
    }
}

树状数组:\(153\)行,本地\(23\)s(一样的复杂度比线段树快近\(3\)倍,结果BZOJ上还是TLE什么鬼),内存\(37.0\)MB

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

namespace zyt
{
    template<typename T>
    inline void read(T &x)
    {
        char c;
        bool f = false;
        x = 0;
        do
            c = getchar();
        while (c != ‘-‘ && !isdigit(c));
        if (c == ‘-‘)
            f = true, c = getchar();
        do
            x = x * 10 + c - ‘0‘, c = getchar();
        while (isdigit(c));
        if (f)
            x = -x;
    }
    template<typename T>
    inline void write(T x)
    {
        static char buf[20];
        char *pos = buf;
        if (x < 0)
            putchar(‘-‘), x = -x;
        do
            *pos++ = x % 10 + ‘0‘;
        while (x /= 10);
        while (pos > buf)
            putchar(*--pos);
    }
    inline void write(const pair<int, int> &a)
    {
        write(a.first), putchar(‘ ‘), write(a.second);
    }
    const int N = 1e5 + 10, M = 1e6 + 10;
    int n, m, arr[N], belong[N];
    typedef pair<int, int> pii;
    pii ans[M];
    struct _ask
    {
        int l, r, a, b, id;
        bool operator < (const _ask &b) const
        {
            return belong[l] == belong[b.l] ? r < b.r : l < b.l;
        }
    }ask[M];
    int cnt, tmp[N + (M << 1)];
    class Tree_Array
    {
    private:
        int data[N];
        inline int lowbit(const int x)
        {
            return x & (-x);
        }
    public:
        inline void add(int a, const int x)
        {
            while (a <= cnt)
                data[a] += x, a += lowbit(a);
        }
        inline int query(int a)
        {
            int ans = 0;
            while (a)
                ans += data[a], a -= lowbit(a);
            return ans;
        }
        inline int query(const int l, const int r)
        {
            return query(r) - query(l - 1);
        }
    }sum, num;
    void update(const int pos, const int x)
    {
        if (x == 1)
        {
            if (!sum.query(pos, pos))
                num.add(pos, 1);
            sum.add(pos, 1); 
        }
        if (x == -1)
        {
            sum.add(pos, -1);
            if (!sum.query(pos, pos))
                num.add(pos, -1);
        }
    }
    void Mo_Algorithm()
    {
        int l = 1, r = 1;
        update(arr[1], 1);
        for (int i = 1; i <= m; i++)
        {
            while (l < ask[i].l)
                update(arr[l++], -1);
            while (l > ask[i].l)
                update(arr[--l], 1);
            while (r < ask[i].r)
                update(arr[++r], 1);
            while (r > ask[i].r)
                update(arr[r--], -1);
            if (ask[i].a > ask[i].b)
                ans[ask[i].id] = make_pair(0, 0);
            else
                ans[ask[i].id] = make_pair(sum.query(ask[i].a, ask[i].b), num.query(ask[i].a, ask[i].b));
        }
    }
    int work()
    {
        int block;
        read(n), read(m);
        block = sqrt(n);
        for (int i = 1; i <= n; i++)
        {
            read(arr[i]), tmp[cnt++] = arr[i];
            belong[i] = (i - 1) / block + 1;
        }
        for (int i = 1; i <= m; i++)
        {
            read(ask[i].l), read(ask[i].r), read(ask[i].a), read(ask[i].b);
            ask[i].id = i;
            tmp[cnt++] = ask[i].a, tmp[cnt++] = ask[i].b;
        }
        sort(tmp, tmp + cnt);
        cnt = unique(tmp, tmp + cnt) - tmp;
        for (int i = 1; i <= n; i++)
            arr[i] = upper_bound(tmp, tmp + cnt, arr[i]) - tmp;
        for (int i = 1; i <= m; i++)
        {
            ask[i].a = upper_bound(tmp, tmp + cnt, ask[i].a) - tmp;
            ask[i].b = upper_bound(tmp, tmp + cnt, ask[i].b) - tmp;
        }
        sort(ask + 1, ask + m + 1);
        Mo_Algorithm();
        for (int i = 1; i <= m; i++)
            write(ans[i]), putchar(‘\n‘);
        return 0;
    }
}
int main()
{
    return zyt::work();
}

分块:\(136\)行,本地\(8\)s,内存\(28.5\)MB,BZOJ上AC。这份代码是我知道最大权值\(1e5\)后写的,所以没有离散化。

#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

namespace zyt
{
    template<typename T>
    inline void read(T &x)
    {
        char c;
        bool f = false;
        x = 0;
        do
            c = getchar();
        while (c != ‘-‘ && !isdigit(c));
        if (c == ‘-‘)
            f = true, c = getchar();
        do
            x = x * 10 + c - ‘0‘, c = getchar();
        while (isdigit(c));
        if (f)
            x = -x;
    }
    template<typename T>
    inline void write(T x)
    {
        static char buf[20];
        char *pos = buf;
        if (x < 0)
            putchar(‘-‘), x = -x;
        do
            *pos++ = x % 10 + ‘0‘;
        while (x /= 10);
        while (pos > buf)
            putchar(*--pos);
    }
    inline void write(const pair<int, int> &a)
    {
        write(a.first), putchar(‘ ‘), write(a.second);
    }
    const int N = 1e5 + 10, M = 1e6 + 10, BL = 510;
    int n, m, arr[N], belong[N];
    typedef pair<int, int> pii;
    pii ans[M];
    struct _ask
    {
        int l, r, a, b, id;
        bool operator < (const _ask &b) const
        {
            return belong[l] == belong[b.l] ? r < b.r : l < b.l;
        }
    }ask[M];
    int blsum[BL], blnum[BL], num[N], begin[BL];
    inline void update(const int pos, const int x)
    {
        blsum[belong[pos]] += x;
        if (x == -1 && !--num[pos])
            --blnum[belong[pos]];
        if (x == 1 && !num[pos]++)
            ++blnum[belong[pos]];
    }
    inline pii query(const int l, const int r)
    {
        pii ans = make_pair(0, 0);
        if (belong[r] == belong[l])
        {
            for (int i = l; i <= r; i++)
                if (num[i])
                    ans.first += num[i], ++ans.second;
        }
        else
        {
            for (int i = belong[l] + 1; i < belong[r]; i++)
                ans.first += blsum[i], ans.second += blnum[i];
            for (int i = l; i < begin[belong[l] + 1]; i++)
                if (num[i])
                    ans.first += num[i], ++ans.second;
            for (int i = begin[belong[r]]; i <= r; i++)
                if (num[i])
                    ans.first += num[i], ++ans.second;
        }
        return ans;
    }
    void Mo_Algorithm()
    {
        int l = 1, r = 1, block = sqrt(N), blnum = ceil(N / (double)block);
        for (int i = 1; i < N; i++)
            belong[i] = (i - 1) / block + 1;
        for (int i = 1; i <= blnum; i++)
            begin[i] = (i - 1) * block + 1;
        update(arr[1], 1);
        for (int i = 1; i <= m; i++)
        {
            while (l < ask[i].l)
                update(arr[l++], -1);
            while (l > ask[i].l)
                update(arr[--l], 1);
            while (r < ask[i].r)
                update(arr[++r], 1);
            while (r > ask[i].r)
                update(arr[r--], -1);
            if (ask[i].a > ask[i].b)
                ans[ask[i].id] = make_pair(0, 0);
            else
                ans[ask[i].id] = query(ask[i].a, ask[i].b);
        }
    }
    int work()
    {
        int block;
        read(n), read(m);
        block = sqrt(n);
        for (int i = 1; i <= n; i++)
        {
            read(arr[i]);
            belong[i] = (i - 1) / block + 1;
        }
        for (int i = 1; i <= m; i++)
        {
            read(ask[i].l), read(ask[i].r), read(ask[i].a), read(ask[i].b);
            ask[i].id = i;
        }
        sort(ask + 1, ask + m + 1);
        Mo_Algorithm();
        for (int i = 1; i <= m; i++)
            write(ans[i]), putchar(‘\n‘);
        return 0;
    }
}
int main()
{
    return zyt::work();
}

【洛谷4396/BZOJ3236】[AHOI2013]作业(莫队+分块/树状数组/线段树)

原文:https://www.cnblogs.com/zyt1253679098/p/9955610.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!