#include <bits/stdc++.h>
using namespace std;
#define int long long
int A[500005], ans[500005];
map<int, int> m, m2, m3;
pair<int, pair<int, int> > Q[500005];
struct node{
int s,e,m,val,lazy;
node *l, *r;
node(int _s, int _e){
s = _s, e =_e, m = s + (e-s)/2, lazy = 0;
if(s != e){
l = new node(s, m);
r = new node(m+1, e);
val = l->val + r->val;
}
else val = A[s], l = r = NULL;
}
void propo(){
if(lazy){
val += lazy*(e-s+1);
if(s != e){
l->lazy += lazy;
r->lazy += lazy;
}
lazy = 0;
}
}
void update(int a, int b, int c){
if(a == s && b == e){lazy += c;return;}
else if(b <= m)l->update(a,b,c);
else if(a > m)r->update(a,b,c);
else l->update(a,m,c), r->update(m+1, b,c);
l->propo(), r->propo();
val = l->val + r->val;
}
int query(int a, int b){
propo();
if(a == s && b == e)return val;
if(a > m)return r->query(a,b);
else if(b <= m)return l->query(a,b);
else return l->query(a,m) + r->query(m+1, b);
}
}*root;
main(){
ios::sync_with_stdio(0);cin.tie(0);
int n,q;
cin >> n >> q;
root= new node(1, n);
for(int i=1;i<=n;i++)cin >> A[i];
for(int i=0;i<q;i++)cin >> Q[i].second.first >> Q[i].first, Q[i].second.second = i;
sort(Q, Q+q);
int in = 0 ;
for(int i=1;i<=n;i++){
int x = m[A[i]];
int z = m2[A[i]];
int e = m3[A[i]];
if(x > z)root->update(z+1, x, 1);
if(z > e)root->update(e+1, z, -1);
while(in < q && Q[in].first == i){
int y = root->query(Q[in].second.first, Q[in].second.first);
ans[Q[in].second.second] = y;
in++;
}
m3[A[i]] = m2[A[i]];
m2[A[i]] = m[A[i]];
m[A[i]] = i;
}
for(int i=0;i<q;i++)cout << ans[i] << '\n';
}
Compilation message
poklon.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
45 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1248 KB |
Output is correct |
| 5 |
Correct |
165 ms |
18332 KB |
Output is correct |
| 6 |
Correct |
163 ms |
18348 KB |
Output is correct |
| 7 |
Correct |
439 ms |
36948 KB |
Output is correct |
| 8 |
Correct |
775 ms |
55392 KB |
Output is correct |
| 9 |
Correct |
963 ms |
73732 KB |
Output is correct |
| 10 |
Correct |
1210 ms |
92068 KB |
Output is correct |
