ZJ8. 用户喜好
描述
为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为k。因为一些特殊的原因，不会出现一个查询的用户区间完全覆盖另一个查询的用户区间(不存在L1<=L2<=R2<=R1)。
输入描述
输入： 第1行为n代表用户的个数 第2行为n个整数，第i个代表用户标号为i的用户对某类文章的喜好度 第3行为一个正整数q代表查询的组数 第4行到第（3+q）行，每行包含3个整数l,r,k代表一组查询，即标号为l<=i<=r的用户中对这类文章喜好值为k的用户的个数。 数据范围n <= 300000,q<=300000 k是整型输出描述
输出：一共q行，每行一个整数代表喜好值为k的用户的个数示例1
输入:
5 1 2 3 3 5 3 1 2 1 2 4 5 3 5 3
输出:
1 0 2
说明:
样例解释: 有5个用户，喜好值为分别为1、2、3、3、5， 第一组询问对于标号[1,2]的用户喜好值为1的用户的个数是1 第二组询问对于标号[2,4]的用户喜好值为5的用户的个数是0 第三组询问对于标号[3,5]的用户喜好值为3的用户的个数是2C++ 解法, 执行用时: 46ms, 内存消耗: 3632KB, 提交时间: 2020-10-29
#include <bits/stdc++.h>
using namespace std;
namespace IO { const int ___ = []() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }( ), L = 1 << 17; streambuf *isb = cin.rdbuf(), *osb = cout.rdbuf(); char ob[L], *oh = ob, *ot = ob + L, ib[L], *ih, *it, nb[32], c; inline char gc() { ih == it && ( it = ih = ib, it += isb->sgetn(ib, L) ); return it - ih ? *ih++ : EOF; }inline int input(char&c) { while (c = gc(), ~c && !isgraph(c)); return ~c; }int input(char*s) { int l = 0; for (input(c); isgraph(c); c = gc()) s[l++] = c; s[l] = 0; return l; }template<class I>int input(I&x) { for (input(c); c != '-' && !isdigit(c); c = gc())if (c == EOF)return 0; int f = x = 0; c == '-' && ( f = 1, c = gc() ); do x = ( x << 3 ) + ( x << 1 ) + ( c & 15 ); while (isdigit(c = gc())); f && ( x = -x ); return 1; }inline void print(char c) { ( *oh = c, ++oh == ot ) && ( osb->sputn(ob, L), oh = ob ); }void print(const char*s) { while (*s)print(*s++); }template <class T>void print(T x) { x < 0 && ( print('-'), x = -x ); char*p = nb; do*p++ = x % 10 | 48; while (x /= 10); do print(*--p); while (p - nb); }void flush() { osb->sputn(ob, oh - ob); }struct _ { ~_() { flush(); } } __; }
using IO::input;
using IO::print;
struct Node {
int val, i;
bool operator<(const Node &b)const { return val < b.val; }
};
int main() {
int n; input(n);
vector<Node> nodes(n); n = 0;
for (auto&x : nodes)input(x.val), x.i = ++n;
sort(nodes.begin(), nodes.end());
int q; input(q);
while (q--) {
int l, r, k, ans = 0; input(l), input(r), input(k);
for (auto it = lower_bound(nodes.begin(), nodes.end(), Node{ k,0 }); it->val == k; ++it)
if (l <= it->i && it->i <= r)
++ans;
print(ans), print('\n');
}
return 0;
}
C++ 解法, 执行用时: 46ms, 内存消耗: 5176KB, 提交时间: 2020-07-23
#include <bits/stdc++.h>
using namespace std;
namespace IO { const int ___ = []() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }( ), L = 1 << 17; streambuf *isb = cin.rdbuf(), *osb = cout.rdbuf(); char ob[L], *oh = ob, *ot = ob + L, ib[L], *ih, *it, nb[32], c; inline char gc() { ih == it && ( it = ih = ib, it += isb->sgetn(ib, L) ); return it - ih ? *ih++ : EOF; }inline int input(char&c) { while (c = gc(), ~c && !isgraph(c)); return ~c; }int input(char*s) { int l = 0; for (input(c); isgraph(c); c = gc()) s[l++] = c; s[l] = 0; return l; }template<class I>int input(I&x) { for (input(c); c != '-' && !isdigit(c); c = gc())if (c == EOF)return 0; int f = x = 0; c == '-' && ( f = 1, c = gc() ); do x = ( x << 3 ) + ( x << 1 ) + ( c & 15 ); while (isdigit(c = gc())); f && ( x = -x ); return 1; }inline void print(char c) { ( *oh = c, ++oh == ot ) && ( osb->sputn(ob, L), oh = ob ); }void print(const char*s) { while (*s)print(*s++); }template <class T>void print(T x) { x < 0 && ( print('-'), x = -x ); char*p = nb; do*p++ = x % 10 | 48; while (x /= 10); do print(*--p); while (p - nb); }void flush() { osb->sputn(ob, oh - ob); }struct _ { ~_() { flush(); } } __; }
using IO::input;
using IO::print;
struct Node {
int val, i;
bool operator<(const Node &b)const { return val < b.val; }
};
int main() {
int n; input(n);
vector<Node> nodes(n); n = 0;
for (auto&x : nodes)input(x.val), x.i = ++n;
sort(nodes.begin(), nodes.end());
int q; input(q);
while (q--) {
int l, r, k, ans = 0; input(l), input(r), input(k);
for (auto it = lower_bound(nodes.begin(), nodes.end(), Node{ k,0 }); it->val == k; ++it)
if (l <= it->i && it->i <= r)
++ans;
print(ans), print('\n');
}
return 0;
}
C++ 解法, 执行用时: 52ms, 内存消耗: 5148KB, 提交时间: 2020-08-26
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
using namespace std;
namespace IO { const int ___ = []() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }(), L = 1 << 17; streambuf* isb = cin.rdbuf(), * osb = cout.rdbuf(); char ob[L], * oh = ob, * ot = ob + L, ib[L], * ih, * it, nb[32], c; inline char gc() { ih == it && (it = ih = ib, it += isb->sgetn(ib, L)); return it - ih ? *ih++ : EOF; }inline int input(char& c) { while (c = gc(), ~c && !isgraph(c)); return ~c; }int input(char* s) { int l = 0; for (input(c); isgraph(c); c = gc()) s[l++] = c; s[l] = 0; return l; }template<class I>int input(I& x) { for (input(c); c != '-' && !isdigit(c); c = gc())if (c == EOF)return 0; int f = x = 0; c == '-' && (f = 1, c = gc()); do x = (x << 3) + (x << 1) + (c & 15); while (isdigit(c = gc())); f && (x = -x); return 1; }inline void print(char c) { (*oh = c, ++oh == ot) && (osb->sputn(ob, L), oh = ob); }void print(const char* s) { while (*s)print(*s++); }template <class T>void print(T x) { x < 0 && (print('-'), x = -x); char* p = nb; do*p++ = x % 10 | 48; while (x /= 10); do print(*--p); while (p - nb); }void flush() { osb->sputn(ob, oh - ob); }struct _ { ~_() { flush(); } } __; }
using IO::input;
using IO::print;
struct Node {
int val, i;
bool operator<(const Node& b)const { return val < b.val; }
};
int main() {
int n; input(n);
vector<Node> nodes(n); n = 0;
for (auto& x : nodes)input(x.val), x.i = ++n;
sort(nodes.begin(), nodes.end());
int q; input(q);
while (q--) {
int l, r, k, ans = 0; input(l), input(r), input(k);
for (auto it = lower_bound(nodes.begin(), nodes.end(), Node{ k,0 }); it->val == k; ++it)
if (l <= it->i && it->i <= r)
++ans;
printf("%d\n",ans);
}
return 0;
}
C++ 解法, 执行用时: 52ms, 内存消耗: 5224KB, 提交时间: 2020-10-29
#include <bits/stdc++.h>
using namespace std;
namespace IO { const int ___ = []() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }( ), L = 1 << 17; streambuf *isb = cin.rdbuf(), *osb = cout.rdbuf(); char ob[L], *oh = ob, *ot = ob + L, ib[L], *ih, *it, nb[32], c; inline char gc() { ih == it && ( it = ih = ib, it += isb->sgetn(ib, L) ); return it - ih ? *ih++ : EOF; }inline int input(char&c) { while (c = gc(), ~c && !isgraph(c)); return ~c; }int input(char*s) { int l = 0; for (input(c); isgraph(c); c = gc()) s[l++] = c; s[l] = 0; return l; }template<class I>int input(I&x) { for (input(c); c != '-' && !isdigit(c); c = gc())if (c == EOF)return 0; int f = x = 0; c == '-' && ( f = 1, c = gc() ); do x = ( x << 3 ) + ( x << 1 ) + ( c & 15 ); while (isdigit(c = gc())); f && ( x = -x ); return 1; }inline void print(char c) { ( *oh = c, ++oh == ot ) && ( osb->sputn(ob, L), oh = ob ); }void print(const char*s) { while (*s)print(*s++); }template <class T>void print(T x) { x < 0 && ( print('-'), x = -x ); char*p = nb; do*p++ = x % 10 | 48; while (x /= 10); do print(*--p); while (p - nb); }void flush() { osb->sputn(ob, oh - ob); }struct _ { ~_() { flush(); } } __; }
using IO::input;
using IO::print;
struct Node {
int val, i;
bool operator<(const Node &b)const { return val < b.val; }
};
int main() {
int n; input(n);
vector<Node> nodes(n); n = 0;
for (auto&x : nodes)input(x.val), x.i = ++n;
sort(nodes.begin(), nodes.end());
int q; input(q);
while (q--) {
int l, r, k, ans = 0; input(l), input(r), input(k);
for (auto it = lower_bound(nodes.begin(), nodes.end(), Node{ k,0 }); it->val == k; ++it)
if (l <= it->i && it->i <= r)
++ans;
print(ans), print('\n');
}
return 0;
}
C++ 解法, 执行用时: 52ms, 内存消耗: 5348KB, 提交时间: 2019-04-14
#include <bits/stdc++.h>
using namespace std;
namespace IO { const int ___ = []() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }( ), L = 1 << 17; streambuf *isb = cin.rdbuf(), *osb = cout.rdbuf(); char ob[L], *oh = ob, *ot = ob + L, ib[L], *ih, *it, nb[32], c; inline char gc() { ih == it && ( it = ih = ib, it += isb->sgetn(ib, L) ); return it - ih ? *ih++ : EOF; }inline int input(char&c) { while (c = gc(), ~c && !isgraph(c)); return ~c; }int input(char*s) { int l = 0; for (input(c); isgraph(c); c = gc()) s[l++] = c; s[l] = 0; return l; }template<class I>int input(I&x) { for (input(c); c != '-' && !isdigit(c); c = gc())if (c == EOF)return 0; int f = x = 0; c == '-' && ( f = 1, c = gc() ); do x = ( x << 3 ) + ( x << 1 ) + ( c & 15 ); while (isdigit(c = gc())); f && ( x = -x ); return 1; }inline void print(char c) { ( *oh = c, ++oh == ot ) && ( osb->sputn(ob, L), oh = ob ); }void print(const char*s) { while (*s)print(*s++); }template <class T>void print(T x) { x < 0 && ( print('-'), x = -x ); char*p = nb; do*p++ = x % 10 | 48; while (x /= 10); do print(*--p); while (p - nb); }void flush() { osb->sputn(ob, oh - ob); }struct _ { ~_() { flush(); } } __; }
using IO::input;
using IO::print;
struct Node {
int val, i;
bool operator<(const Node &b)const { return val < b.val; }
};
int main() {
int n; input(n);
vector<Node> nodes(n); n = 0;
for (auto&x : nodes)input(x.val), x.i = ++n;
sort(nodes.begin(), nodes.end());
int q; input(q);
while (q--) {
int l, r, k, ans = 0; input(l), input(r), input(k);
for (auto it = lower_bound(nodes.begin(), nodes.end(), Node{ k,0 }); it->val == k; ++it)
if (l <= it->i && it->i <= r)
++ans;
print(ans), print('\n');
}
return 0;
}