注:本帖下禁止讨论码风相关
by QAQ__ @ 2023-02-19 10:00:41
造福后人
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int a[2000005], nxt[2000005], pref[2000005], TLEWA[2000005], cnt[2000005], ans[2000005];
struct seele {
int l, r, id;
} sing[2000005];
void addd(int x, int v) {
while (x <= 2000000) {
pref[x] += v;
x += x & -x;
}
}
int query(int x) {
int summ = 0;
while (x) {
summ += pref[x];
x -= x & -x;
}
return summ;
}
int main() {
int n, c, m, ll = 1;
cin >> n >> c >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
TLEWA[a[i]] = nxt[TLEWA[a[i]]] = i;
if (++cnt[a[i]] == 2) addd(i, 1);
}
for (int i = 1; i <= m; i++) {
sing[i].id = i;
cin >> sing[i].l >> sing[i].r;
}
sort(sing + 1, sing + 1 + m, [](seele x, seele y) {
return x.l < y.l;
});
for (int i = 1; i <= m; i++) {
while (ll < sing[i].l) {
if (nxt[ll]) {
addd(nxt[ll], -1);
if (nxt[nxt[ll]]) addd(nxt[nxt[ll]], 1);
}
ll++;
}
ans[sing[i].id] = query(sing[i].r);
}
for (int i = 1; i <= m; i++) cout << ans[i] << endl;
}
```
by SqRt_FiSh @ 2023-02-19 10:01:15
@[QAQ__](/user/627636)
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int a[2000005], nxt[2000005], pref[2000005], TLEWA[2000005], cnt[2000005], ans[2000005];
struct seele {
int l, r, id;
} sing[2000005];
void addd(int x, int v) {
while (x <= 2000000) {
pref[x] += v;
x += x & -x;
}
}
int query(int x) {
int summ = 0;
while (x) {
summ += pref[x];
x -= x & -x;
}
return summ;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n, c, m, ll = 1;
cin >> n >> c >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
TLEWA[a[i]] = nxt[TLEWA[a[i]]] = i;
if (++cnt[a[i]] == 2) addd(i, 1);
}
for (int i = 1; i <= m; i++) {
sing[i].id = i;
cin >> sing[i].l >> sing[i].r;
}
sort(sing + 1, sing + 1 + m, [](seele x, seele y) {
return x.l < y.l;
});
for (int i = 1; i <= m; i++) {
while (ll < sing[i].l) {
if (nxt[ll]) {
addd(nxt[ll], -1);
if (nxt[nxt[ll]]) addd(nxt[nxt[ll]], 1);
}
ll++;
}
ans[sing[i].id] = query(sing[i].r);
}
for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}
```
by Loser_Syx @ 2023-02-19 10:04:40
推荐使用 小熊猫C++/CLion 代码格式化功能。
by a2lyaXNhbWUgbWFyaXNh @ 2023-02-19 10:21:26
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int a[2000005], nxt[2000005], pref[2000005], TLEWA[2000005], cnt[2000005], ans[2000005];
struct seele {
int l, r, id;
} sing[2000005];
void addd(int x, int v) {
while (x <= 2000000) {
pref[x] += v;
x += x & -x;
}
}
int query(int x) {
int summ = 0;
while (x) {
summ += pref[x];
x -= x & -x;
}
return summ;
}
int main() {
int n, c, m, ll = 1;
cin >> n >> c >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
TLEWA[a[i]] = nxt[TLEWA[a[i]]] = i;
if (++cnt[a[i]] == 2)
addd(i, 1);
}
for (int i = 1; i <= m; i++) {
sing[i].id = i;
cin >> sing[i].l >> sing[i].r;
}
sort(sing + 1, sing + 1 + m, [](seele x, seele y) {
return x.l < y.l;
});
for (int i = 1; i <= m; i++) {
while (ll < sing[i].l) {
if (nxt[ll]) {
addd(nxt[ll], -1);
if (nxt[nxt[ll]])
addd(nxt[nxt[ll]], 1);
}
ll++;
}
ans[sing[i].id] = query(sing[i].r);
}
for (int i = 1; i <= m; i++)
cout << ans[i] << endl;
}
```
by a2lyaXNhbWUgbWFyaXNh @ 2023-02-19 10:22:15
@[QAQ__](/user/627636) 关同步流。
by 5k_sync_closer @ 2023-03-06 20:37:00
@[5k_sync_closer](/user/388651) 其实这个问题已经解决了,上面有人说了(
by QAQ__ @ 2023-03-06 20:38:03
@[5k_sync_closer](/user/388651) 不过还是谢谢蓝勾爷!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
by QAQ__ @ 2023-03-06 20:38:18