P4396-[AHOI2013]作业

2021-02-10 约 1228 字预计阅读 3 分钟次阅读

P4396-[AHOI2013]作业

题目:

题目描述:

此时己是凌晨两点，刚刚做了 Codeforces 的小 A 掏出了英语试卷。英语作业其实不算多，一个小时刚好可以做完。然后是一个小时可以做完的数学作业，接下来是分别都是一个小时可以做完的化学，物理，语文……小 A 压力巨大。

这时小 A 碰见了一道非常恶心的数学题，给定了一个长度为 $n$ 的数列和若干个询问，每个询问是关于数列的区间表示数列的第 $l$ 个数到第 $r$ 个数)，首先你要统计该区间内大于等于 $a$，小于等于 $b$ 的数的个数，其次是所有大于等于 $a$，小于等于 $b$ 的，且在该区间中出现过的数值的个数。

小 A 望着那数万的数据规模几乎绝望，只能向大神您求救，请您帮帮他吧。

输入格式:

第一行两个整数 $n, m$

接下来 $n$ 个不超过 $10^5$ 的正整数表示数列

接下来 $m$ 行，每行四个整数 $l, r, a, b$，具体含义参见题意。

输出格式:

输出 $m$ 行，分别对应每个询问，输出两个数，分别为在 $l$ 到 $r$ 这段区间中大小在 $[a, b]$ 中的数的个数，以及大于等于 $a$，小于等于 $b$ 的，且在该区间中出现过的数值的个数（具体可以参考样例）。

样例:

样例输入1:

样例输出1:

思路:

建立一棵权值线段树, 在权值线段树上进行分治, 于是问题就转化为统计区间内$l\to r$的数和不同的数, 两问均可以使用树状数组实现.

实现:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
// Problem: P4396 [AHOI2013]作业
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4396
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)

#include "ybwhead/ios.h"
int n, m;
const int maxm = 1e5 + 10;
const int maxn = 1e5 + 10;
struct node
{
    int l, r, a, b, id;
} q[maxm];
int ans[maxm], ans2[maxm];
struct tree
{
    int d[maxn];
#define lowbit(x) x & -x
    void add(int p, int c)
    {
        for (; p <= n; p += lowbit(p))
            d[p] += c;
    }
    int q(int p)
    {
        int ans = 0;
        for (; p; p -= lowbit(p))
            ans += d[p];
        return ans;
    }
} c1, c2;
int rt, cnt;
struct nd2
{
    int ls, rs;
    vector<node> qu;
    vector<pair<int, int>> c;
} c[maxn << 1];
void build(int &p, int l, int r)
{
    if (!p)
        p = ++cnt;
    if (l == r)
        return;
    if (!c[p].ls)
        c[p].ls = ++cnt;
    if (!c[p].rs)
        c[p].rs = ++cnt;
    int mid = l + r >> 1;
    for (auto x : c[p].c)
        if (x.second <= mid)
            c[c[p].ls].c.push_back(x);
        else
            c[c[p].rs].c.push_back(x);
    build(c[p].ls, l, mid);
    build(c[p].rs, mid + 1, r);
}
void add(int &p, node t, int l, int r)
{
    // cerr << p << " " << c[p].l << " " << c[p].r << " " << t.a << ' ' << t.b << endl;
    if (t.a <= l && r <= t.b)
    {
        c[p].qu.push_back(t);
        return;
    }
    int mid = l + r >> 1;
    if (t.a <= mid)
    {
        add(c[p].ls, t, l, mid);
    }
    if (t.b > mid)
        add(c[p].rs, t, mid + 1, r);
}
int cmp(node a, node b)
{
    return a.r < b.r;
}
int e[maxn];
int lst[maxn];
int main()
{
    yin >> n >> m;
    int mx = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        yin >> x;
        c[1].c.push_back(make_pair(i, x)), mx = max(mx, x);
    }
    build(rt, 1, n);
    for (int i = 1; i <= m; i++)
    {
        int l, r, a, b;
        yin >> l >> r >> a >> b;
        node tmp = (node){l, r, a, b, i};
        add(rt, tmp, 1, n);
    }
    // cerr << "!!!" << endl;
    for (int i = 1; i <= cnt; i++)
    {
        if (c[i].qu.empty() || c[i].c.empty())
            continue;
        sort(c[i].qu.begin(), c[i].qu.end(), cmp);
        int j = 1, k = 0;
        while (k < c[i].qu.size() && c[i].qu[k].r < c[i].c[0].first)
            ++k;
        for (auto x : c[i].c)
        {
            if (lst[x.second])
                c1.add(lst[x.second], -1);
            lst[x.second] = j;
            c1.add(j, 1);
            c2.add(j, 1);
            // cerr << j << endl;
            while (k < c[i].qu.size() && (j == c[i].c.size() || c[i].qu[k].r < c[i].c[j].first))
            {
                int l = lower_bound(c[i].c.begin(), c[i].c.end(), make_pair(c[i].qu[k].l, 0)) - c[i].c.begin() + 1;
                // yout << l << endl;
                ans[c[i].qu[k].id] += c2.q(j) - c2.q(l - 1);
                ans2[c[i].qu[k].id] += c1.q(j) - c1.q(l - 1);
                ++k;
            }
            ++j;
        }
        j = 1;
        for (auto x : c[i].c)
        {
            if (lst[x.second])
                c1.add(lst[x.second], -1);
            lst[x.second] = 0;
            c2.add(j, -1);
            ++j;
        }
    }
    for (int i = 1; i <= m; i++)
    {
        yout << ans[i] << " " << ans2[i] << endl;
    }
    return 0;
}

目录

P4396-[AHOI2013]作业

P4396-[AHOI2013]作业

题目:

题目描述:

输入格式:

输出格式:

样例:

样例输入1:

样例输出1:

思路:

实现: