# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
const int N = 5e5 + 5;
int a[N],tree[N],l[N],r[N],ans[N];
vector <int> que[N],v[N];
void update(int idx, int val) {
for (int i = idx; i < N; i += i&(-i)) {
tree[i] += val;
}
}
int getans(int idx) {
int pas = 0;
for (int i = idx; i > 0; i-=i&(-i)) {
pas += tree[i];
}
return pas;
}
signed main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n,q;
cin>>n>>q;
for (int i = 1; i <= n; i++) {
cin>>a[i];
}
for (int i = 1; i <= q; i++) {
cin>>l[i]>>r[i];
que[r[i]].pb(i);
}
for (int ri = 1; ri <= n; ri++) {
if (v[a[ri]].size()) {
update(v[a[ri]].back(), 1);
}
if (v[a[ri]].size() >= 2) {
int x = v[a[ri]].size();
update(v[a[ri]][x - 2], -2);
}
if (v[a[ri]].size() >= 3) {
int x = v[a[ri]].size();
update(v[a[ri]][x - 3], 1);
}
v[a[ri]].pb(ri);
for (int j = 0; j < que[ri].size(); j++) {
int idx = que[ri][j];
ans[idx] = getans(ri) - getans(l[idx] - 1);
}
}
for (int i = 1; i <= q; i++) {
cout<<ans[i]<<"\n";
}
}
Compilation message
poklon.cpp: In function 'int main()':
poklon.cpp:46:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int j = 0; j < que[ri].size(); j++) {
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23876 KB |
Output is correct |
| 2 |
Correct |
12 ms |
23800 KB |
Output is correct |
| 3 |
Correct |
15 ms |
23828 KB |
Output is correct |
| 4 |
Correct |
17 ms |
24052 KB |
Output is correct |
| 5 |
Correct |
58 ms |
28308 KB |
Output is correct |
| 6 |
Correct |
63 ms |
28352 KB |
Output is correct |
| 7 |
Correct |
132 ms |
32896 KB |
Output is correct |
| 8 |
Correct |
215 ms |
37864 KB |
Output is correct |
| 9 |
Correct |
268 ms |
42264 KB |
Output is correct |
| 10 |
Correct |
397 ms |
46240 KB |
Output is correct |
