#include<bits/stdc++.h>
// time 10:13, 10:38
using namespace std;
#define NMAX 5000005
int n, q;
int a[NMAX];
vector<vector<int> > ind;
struct segtree{
vector<int> t, l;
int sz;
segtree(int n){
sz = n;
t.resize(4*n); l.resize(4*n);
}
inline void prop(int i, int s, int e){
if(l[i] == 0) return;
if(s != e){
l[i*2] += l[i];
l[i*2+1] += l[i];
}
t[i] += l[i];
l[i] = 0;
}
void upd(int l, int r, int val){
upd(1, 0, sz-1, l, r, val);
}
void upd(int i, int s, int e, int le, int r, int val){
prop(i, s, e);
if(s >= le && e <= r){
l[i] += val;
prop(i, s, e);
return;
}
if(s > r || e < le) return;
int m = (s + e)/2;
upd(i*2, s, m, le, r, val);
upd(i*2+1, m+1, e, le, r, val);
t[i] = t[i*2] + t[i*2+1];
}
int query(int indx){
return query(1, 0, sz-1, indx);
}
int query(int i, int s, int e, int indx){
prop(i, s, e);
if(s == e) return t[i];
int m = (s + e)/2;
if(indx <= m) return query(i*2, s, m, indx);
else return query(i*2+1, m+1, e, indx);
}
};
struct actions{
int x;
int t, b;
int type;
bool operator<(const actions& other){
if(x != other.x) return x < other.x;
return type < other.type;
}
};
int main(){
cin>>n>>q;
map<int, int> mp;
int cnt = 1;
for(int i = 0; i < n; i++){
cin>>a[i];
if(mp[a[i]] == 0){
mp[a[i]] = cnt;
a[i] = cnt++;
}else{
a[i] = mp[a[i]];
}
}
ind = vector<vector<int> > (cnt+1);
for(int i = 0; i < n; i++){
ind[a[i]].push_back(i);
}
mp.clear();
vector<actions> nodes;
for(int i = 0; i < q; i++){
int l, r; cin>>l>>r; l--, r--;
nodes.push_back({l, r, -1, i});
}
for(int i = 1; i < cnt; i++){
if(ind[i].size() <= 1) continue;
for(int j = 0; j < ind[i].size()-1; j++){
// left point is j, right point is j+2
int l = (j == 0?0:(ind[i][j-1]+1));
int r = (j == ind[i].size()-2)?n-1:(ind[i][j+2]-1);
nodes.push_back({l, r, ind[i][j+1], -1});
nodes.push_back({ind[i][j]+1, r, ind[i][j+1], -2});
}
}
sort(nodes.begin(), nodes.end());
int ans[q];
segtree st(n);
for(actions a: nodes){
if(a.type < 0){
st.upd(a.b, a.t, (a.type==-1)?1:-1);
}else{
ans[a.type] = st.query(a.t);
}
}
for(int i = 0; i < q; i++){
cout<<ans[i]<<endl;
}
}
Compilation message
poklon.cpp: In function 'int main()':
poklon.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < ind[i].size()-1; j++){
~~^~~~~~~~~~~~~~~~~
poklon.cpp:100:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
int r = (j == ind[i].size()-2)?n-1:(ind[i][j+2]-1);
~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
252 KB |
Output is correct |
| 2 |
Correct |
4 ms |
484 KB |
Output is correct |
| 3 |
Correct |
6 ms |
560 KB |
Output is correct |
| 4 |
Correct |
20 ms |
1020 KB |
Output is correct |
| 5 |
Correct |
412 ms |
9888 KB |
Output is correct |
| 6 |
Correct |
423 ms |
9936 KB |
Output is correct |
| 7 |
Correct |
1004 ms |
19448 KB |
Output is correct |
| 8 |
Correct |
1572 ms |
29432 KB |
Output is correct |
| 9 |
Correct |
1909 ms |
38716 KB |
Output is correct |
| 10 |
Correct |
2612 ms |
47452 KB |
Output is correct |
