#include <bits/stdc++.h>
#define ff first
#define int long long int
#define ss second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define pqb priority_queue<int>
#define max_size 100000000
#define pqs priority_queue<int,vi,greater<int> >
#define setbits(x) __builtin_popcountll(x)
#define w(t) int t; cin >> t; while(t--)
#define inf 1e18
#define MOD (int)1e9+7
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];
#define range(a,b) substr(a,b-a+1)
#define mina(a,b,c) min(a, min(b, c))
#define maxa(a,b,c) max(a, max(b, c))
#define sz(a) (int)a.size()
#define endl '\n'
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl;
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FOR(x,y) for(int i = x; i < y; i++)
// #define f(t) int t; cin >> t; for(int i = 1; i <= t; i++)
using namespace std;
bool sortbysec(const pair<int,int> &a, const pair<int,int> &b){ return (a.ff > b.ff); }
int64_t ceil_div(int64_t a, int64_t b) {if(a%b != 0){ return ((a/b)+1);} else{ return (a/b);}}
double max(double a, double b){ if(a >= b){ return a; } else{ return b; } }
double min(double a, double b){if(a <= b){return a;} else{return b; }}
struct segtree{
vi seg;
int n;
segtree(int m) : seg(4*m) { n = m; }
int query(int l, int r, int ql, int qr, int pos){
if(l > qr || r < ql){
return 0;
}
if(l >= ql && r <= qr) return seg[pos];
int mid = (l+r)/2;
int m1 = query(l, mid, ql, qr, pos*2);
int m2 = query(mid+1, r, ql, qr, pos*2+1);
return m1+m2;
}
int query(int l, int r){
return query(1,n,l,r,1);
}
void update(int l, int r, int qidx, int qval, int pos){
if(l == r){
seg[pos] = qval;
return;
}
int mid = (l+r)/2;
if(qidx <= mid) update(l, mid, qidx, qval, pos*2);
else update(mid+1, r, qidx, qval, pos*2+1);
seg[pos] = seg[pos*2] + seg[pos*2+1];
}
void update(int idx, int val){
update(1,n, idx, val, 1);
}
void print(int l, int r, int pos) {
cout << l << " " << r << ": " << seg[pos] << endl;
if(l == r) return;
int mid = (l+r)/2;
print(l, mid, pos*2);
print(mid+1, r, pos*2+1);
}
void print(){
print(1,n,1);
}
};
void solve(){
int n, q;
cin >> n >> q;
vi a(n);
segtree st(n);
FOR(0,n) cin >> a[i];
unordered_map<int, array<int,3>> fq;
unordered_map<int, int> cn;
vector<array<int,3>> queries;
FOR(0,q){
int l,r;
cin >> l >> r;
queries.pb({r,l,i});
}
sort(queries.begin(), queries.end());
vi ans(q);
int id = 0;
for(auto i : queries){
auto [r,l,idx] = i;
while(id < r){
int curr = a[id];
if(cn[curr] == 0){
fq[curr][0] = id+1;
}
else if(cn[curr] == 1){
st.update(fq[curr][0], 1);
fq[curr][1] = fq[curr][0];
fq[curr][0] = id+1;
}
else if(cn[curr] == 2){
st.update(fq[curr][1], -1);
st.update(fq[curr][0], 1);
fq[curr][2] = fq[curr][1];
fq[curr][1] = fq[curr][0];
fq[curr][0] = id+1;
}
else if(cn[curr] > 2){
st.update(fq[curr][2], 0);
st.update(fq[curr][1], -1);
st.update(fq[curr][0], 1);
fq[curr][2] = fq[curr][1];
fq[curr][1] = fq[curr][0];
fq[curr][0] = id+1;
}
cn[curr]++;
id++;
}
ans[idx] = st.query(l,r);
}
for(auto i : ans) cout << i << endl;
}
int32_t main(){
FIO;
//~ w(t){solve();}
solve();
//f(t){cout << "Case #" << i << ": "; solve();}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
328 KB |
Output is correct |
| 4 |
Correct |
5 ms |
852 KB |
Output is correct |
| 5 |
Correct |
103 ms |
8936 KB |
Output is correct |
| 6 |
Correct |
101 ms |
8948 KB |
Output is correct |
| 7 |
Correct |
229 ms |
18092 KB |
Output is correct |
| 8 |
Correct |
348 ms |
29280 KB |
Output is correct |
| 9 |
Correct |
490 ms |
36280 KB |
Output is correct |
| 10 |
Correct |
605 ms |
45032 KB |
Output is correct |
