题解 P1972 【[SDOI2009]HH的项链】
DarkMoon_Dragon
·
·
题解
莫队的思想：按照r端点排序，总之一个思想，对于区间(l,r) 每种颜色贡献X中最右段的X的贡献一定是最优的
记录一个last数组 表示上一个这个数出现在哪里
记录一个l 如果l移动
1. 出现过这个数，删掉之前的，加上当前数字 last[x]=i,add(last[x],-1);
2. 没有出现过这个数，直接加上这种数即可 last[x]=i;vis[i]=1
HDU 3874再次加深了我对这道题的理解,对于重复询问排序方法很重要
然后用树状数组维护前缀和即可，表示(1,r)有几种颜色
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdio>
#define rr register int
using namespace std;
typedef long long ll;
inline int read(){
char i=getchar();
int f=1,res=0;
while(i<'0'||i>'9'){if(i=='-')f=-1;i=getchar();}
while(i>='0'&&i<='9'){res=res*10+i-'0';i=getchar();}
return res*f;
}
const int N=1e6+50;
int sum[N];
inline int lowbit(int x){
return x&-x;
}
void add(int pos,int x){
for(rr i=pos;i<N;i+=lowbit(i)){
sum[i]+=x;
}
}
int query(int pos){
int res=0;
for(rr i=pos;i>0;i-=lowbit(i)){
res+=sum[i];
}
return res;
}
struct zk{
int l,r,id;
bool operator <(const zk&A)const{
return r<A.r;
}
}q[N];
int ans[N],vis[N],last[N],a[N];
int main(){
int n,m;
n=read();
for(rr i=1;i<=n;++i){
a[i]=read();
}
m=read();
for(rr i=1;i<=m;++i){
q[i].l=read();q[i].r=read();
q[i].id=i;
}
sort(q+1,q+1+m);
int r=1;
for(rr i=1;i<=m;++i){
// 直接 放在末尾更新即可
for(;r<=q[i].r;++r){
if(!vis[a[r]]){
vis[a[r]]=1;
last[a[r]]=r;
add(r,1);
}else{
add(last[a[r]],-1);
last[a[r]]=r;
add(r,1);
}
}
ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
}
for(rr i=1;i<=m;++i){
printf("%d\n",ans[i]);
}
}
```
---一年后代码
```cpp
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#define rr int
using namespace std;
typedef long long ll;
inline ll read() {
char i = getchar();
ll f = 1, res = 0;
while (i < '0' || i > '9') {
if (i == '-') f = -1;
i = getchar();
}
while (i >= '0' && i <= '9') {
res = res * 10 + i - '0';
i = getchar();
}
return res * f;
}
const int N = 1e6 + 50;
int n;
int c[N];
inline int lowbit(int x) {
return x & (-x);
}
inline void update(int pos, int x) {
for (rr i = pos; i < N; i += lowbit(i)) {
c[i] += x;
}
}
inline int sum(int pos) {
int res = 0;
while (pos > 0) {
res += c[pos];
pos -= lowbit(pos);
}
return res;
}
inline int query(int l, int r) {
return sum(r) - sum(l - 1);
}
struct ask{
int l, r, id;
bool operator< (const ask &A) const{
return r < A.r;
}
}a[N];
int l, r;
int last[N], pos[N], ans[N];
int main() {
n = read();
for (rr i = 1; i <= n; ++i) {
int x = read();
if (pos[x]) last[i] = pos[x];
pos[x] = i;
}
int q = read();
for (rr i = 1; i <= q; ++i) {
a[i].l = read();
a[i].r = read();
a[i].id = i;
}
sort(a + 1, a + q + 1);
int now = 1;
for (rr i = 1; i <= n; ++i) {
if (last[i]) {
update(last[i], -1);
}
update(i, 1);
while (now <= q && a[now].r == i) {
ans[a[now].id] = query(a[now].l, a[now].r);
++now;
}
}
for (rr i = 1; i <= q; ++i) {
printf("%d\n", ans[i]);
}
}
```