题目
题目描述: 给定一个序列,有多次询问,每次查询区间里小于等于某个数的元素的个数。
即对于询问 (l,r,x),你需要输出 的值。
其中 [exp] 是一个函数,它返回 1 当且仅当 exp 成立,其中 exp 表示某个表达式
第一行两个整数n,m。
第二行n个整数表示序列a的元素,序列下标从1开始标号,保证1 ≤ ai ≤ 105。
之后有m行,每行三个整数(l,r,k),保证1 ≤ l ≤ r ≤ n,且1 ≤ k ≤ 105。
对于每一个询问,输出一个整数表示答案后回车。
我不
我是个菜鸡,我决定输入+遍历查找。
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); } //函数区