【每日一题】换个角度思考

换个角度思考

https://ac.nowcoder.com/acm/problem/19427

题目

题目描述：
给定一个序列，有多次询问，每次查询区间里小于等于某个数的元素的个数。
即对于询问 (l,r,x)，你需要输出 $\sum_{i=l}^{r}[a_i \le x]$ 的值。

其中 [exp] 是一个函数，它返回 1 当且仅当 exp 成立，其中 exp 表示某个表达式

输入描述：
第一行两个整数n,m。
第二行n个整数表示序列a的元素，序列下标从1开始标号，保证1 ≤ ai ≤ 10⁵。

之后有m行，每行三个整数(l,r,k)，保证1 ≤ l ≤ r ≤ n，且1 ≤ k ≤ 10⁵。

输出描述：
对于每一个询问，输出一个整数表示答案后回车。

我不

我是个菜鸡，我决定输入+遍历查找。

AC代码

#include <iostream>
using namespace std;
//代码预处理区

const int MAX = 1e5 + 7;
int a[MAX];
//全局变量区

template<class T>inline void read(T& res);//整型快读函数
//函数预定义区

int main() {
    int n, m; read(n); read(m);
    for (int i = 1; i <= n; i++)
        read(a[i]);
    while (m--) {
        int l, r, k; read(l); read(r); read(k);
        int ans = 0;
        for (int i = l; i <= r; i++)
            if (a[i] <= k) ans++;
        printf("%d\n", ans);
    }
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
//函数区

换个角度思考

迫于自己憨憨本憨的压力，还是要换个角度思考。

虽然还是不熟，但是这道题可以就是可持续化线段树的方法来写。就是板子。

之后我补个专栏写这玩意儿~

AC代码

#include <iostream>
using namespace std;
#define mid (l + r >> 1)
//代码预处理区

const int N = 1e5 + 7;
int n, m, rt[N], lc[N << 5], rc[N << 5], sum[N << 5], tot;
//全局变量区

template<class T>inline void read(T& res);//整型快读函数
void build(int l, int r, int& x, int y, int k);
int ask(int l, int r, int x, int y, int ql, int qr);
//函数预定义区

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) {
        int x; read(x);
        build(1, 1e5, rt[i], rt[i - 1], x);
    }
    for (int i = 1; i <= m; ++i) {
        int l, r, k; read(l); read(r); read(k);
        printf("%d\n", ask(1, 1e5, rt[l - 1], rt[r], 1, k));
    }
    return 0;
}
template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
void build(int l, int r, int& x, int y, int k) {
    x = ++tot;
    lc[x] = lc[y], rc[x] = rc[y], sum[x] = sum[y] + 1;
    if (l == r)    return;
    if (k <= mid)    build(l, mid, lc[x], lc[y], k);
    else    build(mid + 1, r, rc[x], rc[y], k);
}
int ask(int l, int r, int x, int y, int ql, int qr) {
    if (l == ql && r == qr)    return sum[y] - sum[x];
    if (qr <= mid)    return ask(l, mid, lc[x], lc[y], ql, qr);
    else if (ql > mid)    return ask(mid + 1, r, rc[x], rc[y], mid + 1, qr);
    else    return ask(l, mid, lc[x], lc[y], ql, mid) + ask(mid + 1, r, rc[x], rc[y], mid + 1, qr);
}
//函数区

每日一题文章被收录于专栏

憨憨的专栏