Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <iostream>
- #include <vector>
- #include <string>
- #include <cmath>
- #include <iomanip>
- #include <algorithm>
- #include <map>
- #include <set>
- #include <deque>
- #include <unordered_map>
- #include <stack>
- #include <queue>
- #include <random>
- #define ll int
- #define ld long double
- #define mp make_pair
- #define all(v) (v).begin(), (v).end()
- using namespace std;
- #include <cstdio>
- /** Interface */
- inline int readChar();
- template <class T = int> inline T readInt();
- template <class T> inline void writeInt(T x, char end = 0);
- inline void writeChar(int x);
- inline void writeWord(const char* s);
- /** Read */
- static const int buf_size = 4096;
- inline int getChar() {
- static char buf[buf_size];
- static int len = 0, pos = 0;
- if (pos == len)
- pos = 0, len = fread(buf, 1, buf_size, stdin);
- if (pos == len)
- return -1;
- return buf[pos++];
- }
- inline int readChar() {
- int c = getChar();
- while (c <= 32)
- c = getChar();
- return c;
- }
- template <class T>
- inline T readInt() {
- int s = 1, c = readChar();
- T x = 0;
- if (c == '-')
- s = -1, c = getChar();
- while ('0' <= c && c <= '9')
- x = x * 10 + c - '0', c = getChar();
- return s == 1 ? x : -x;
- }
- /** Write */
- static int write_pos = 0;
- static char write_buf[buf_size];
- inline void writeChar(int x) {
- if (write_pos == buf_size)
- fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
- write_buf[write_pos++] = x;
- }
- template <class T>
- inline void writeInt(T x, char end) {
- if (x < 0)
- writeChar('-'), x = -x;
- char s[24];
- int n = 0;
- while (x || !n)
- s[n++] = '0' + x % 10, x /= 10;
- while (n--)
- writeChar(s[n]);
- if (end)
- writeChar(end);
- }
- inline void writeWord(const char* s) {
- while (*s)
- writeChar(*s++);
- }
- struct Flusher {
- ~Flusher() {
- if (write_pos)
- fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
- }
- } flusher;
- const ll inf = 1e18, siz = 350; // 350
- ll n, m;
- vector<vector<ll>> b1;
- ll get_res(vector<ll>& a, ll b, ll c) {
- ll l1 = -1, r1 = (ll)a.size() - 1;
- while (r1 - l1 > 1) {
- ll mid = (l1 + r1) / 2;
- if (a[mid] < b) l1 = mid;
- else r1 = mid;
- }
- if (a[r1] < b || a[r1] > c) return 0;
- ll l2 = 0, r2 = (ll)a.size();
- while (r2 - l2 > 1) {
- ll mid = (l2 + r2) / 2;
- if (a[mid] <= c) l2 = mid;
- else r2 = mid;
- }
- if (a[l2] < b || a[l2] > c) return 0;
- return l2 - l1;
- }
- void run() {
- // cin >> n >> m;
- n = readInt(), m = readInt();
- vector<ll> v(n);
- for (ll i = 0; i < n / siz; i++) {
- vector<ll> cur;
- for (ll j = 0; j < siz; j++) {
- // cin >> v[i * siz + j];
- v[i * siz + j] = readInt();
- cur.push_back(v[i * siz + j]);
- }
- b1.push_back(cur);
- }
- vector<ll> cur;
- for (ll i = 0; i < n % siz; i++) {
- cin >> v[(n / siz) * siz + i];
- v.push_back(v[(n / siz) * siz + i]);
- cur.push_back(v[(n / siz) * siz + i]);
- }
- if (!cur.empty()) b1.push_back(cur);
- for (auto& to : b1) {
- sort(all(to));
- }
- while (m--) {
- ll x, y, k, l;
- cin >> x >> y >> k >> l;
- x--, y--;
- ll ans = 0;
- if (y - x + 1 <= siz) {
- for (ll i = x; i <= y; i++) {
- if (k <= v[i] && v[i] <= l) ans++;
- }
- writeInt(ans);
- writeWord("\n");
- //cout << ans << "\n";
- continue;
- }
- ll ind = 0;
- for (ll i = 0; i < (ll)b1.size(); i++) {
- ll lb = ind, rb = ind + (ll)b1[i].size() - 1;
- if (x <= lb && rb <= y) {
- ans += get_res(b1[i], k, l);
- }
- else if (lb <= x && x <= rb) {
- for (ll j = x; j <= rb; j++) {
- if (k <= v[j] && v[j] <= l) ans++;
- }
- }
- else if (lb <= y && y <= rb) {
- for (ll j = lb; j <= y; j++) {
- if (k <= v[j] && v[j] <= l) ans++;
- }
- }
- ind += (ll)b1[i].size();
- }
- writeInt(ans);
- writeWord("\n");
- //cout << ans << "\n";
- }
- }
- int main() {
- // ios::sync_with_stdio(false);
- // cin.tie(nullptr);
- ll t = 1;
- //cin >> t;
- while (t--) {
- run();
- writeWord("\n");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement