#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
#define task "btd"
#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define forw(i, l, r) for( ll i = (l) ; i < (r) ; i++ )
#define forb(i, r, l) for( ll i = (r) ; i >= (l) ; i-- )
#define sz(x) (int)x.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define numBit(x) __builtin_popcount(x)
#define lb lower_bound
#define ub upper_bound
#define ar array
#define endl '\n'
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
const int N = 5e5 + 7;
const ll inf = 0x3f3f3f3f;
const int block = 600;
int n, q, a[N], l[N], r[N], ans[N];
void sub1() {
map<int, int> cnt;
forw(i, 1, q + 1) {
int ans = 0;
cnt.clear();
forw(j, l[i], r[i] + 1) {
cnt[a[j]]++;
if (cnt[a[j]] == 2) ++ans;
if (cnt[a[j]] == 3) ans = max(0, ans - 1);
}
cout << ans << endl;
}
}
struct query{
int l, r, idx;
} queries[N];
bool cmp(query a, query b){
if (a.l / block != b.l/block)
return a.l / block < b.l / block;
return a.r < b.r;
}
int cur, cnt[N];
void add(ll idx){
ll tmp = ++ cnt[a[idx]];
if (tmp == 2) cur ++;
if (tmp == 3) cur --;
}
void sub(ll idx){
int tmp = -- cnt[a[idx]];
if (tmp == 2) cur ++;
if (tmp == 1) cur --;
}
void sub2() {
sort(queries + 1, queries + 1 + q, cmp);
ll l = 1, r = 0;
bool inc = false, dec = false;
for (int i = 1; i <= q; i ++){
while (r < queries[i].r) add(++r);
while (r > queries[i].r) sub(r--);
while (l < queries[i].l) sub(l++);
while (l > queries[i].l) add(--l);
ans[queries[i].idx] = cur;
}
for (int i = 1; i <= q; i ++)
cout << ans[i] << '\n';
}
ii cmpres[N];
int main() {
// fastIO;
scanf("%d %d", &n, &q);
forw(i, 1, n + 1) {
scanf("%d", &a[i]);
cmpres[i] = ii(a[i], i);
}
sort(cmpres + 1, cmpres + 1 + n);
for (int i = 1, v = 0; i <= n; i ++){
if (cmpres[i].fi != cmpres[i - 1].fi) v ++;
a[cmpres[i].se] = v;
}
forw(i, 1, q + 1) {
scanf("%d %d", &l[i], &r[i]);
queries[i].l = l[i], queries[i].r = r[i];
queries[i].idx = i;
}
// sub2();
if (n <= 5000 && q <= 5000) sub1();
else sub2();
}
Compilation message
poklon.cpp: In function 'void sub2()':
poklon.cpp:78:8: warning: unused variable 'inc' [-Wunused-variable]
78 | bool inc = false, dec = false;
| ^~~
poklon.cpp:78:21: warning: unused variable 'dec' [-Wunused-variable]
78 | bool inc = false, dec = false;
| ^~~
poklon.cpp: In function 'int main()':
poklon.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | scanf("%d %d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~
poklon.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
poklon.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | scanf("%d %d", &l[i], &r[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
7 ms |
332 KB |
Output is correct |
| 3 |
Correct |
44 ms |
332 KB |
Output is correct |
| 4 |
Correct |
575 ms |
524 KB |
Output is correct |
| 5 |
Correct |
191 ms |
4812 KB |
Output is correct |
| 6 |
Correct |
196 ms |
4860 KB |
Output is correct |
| 7 |
Correct |
522 ms |
9332 KB |
Output is correct |
| 8 |
Correct |
964 ms |
13752 KB |
Output is correct |
| 9 |
Correct |
1496 ms |
18308 KB |
Output is correct |
| 10 |
Correct |
2158 ms |
22712 KB |
Output is correct |
