# P1972 [SDOI2009]HH的项链(离线＆BIT)

2021-08-10 08:02:49

P1972 [SDOI2009]HH的项链(离线&BIT)

code

``````// Problem: P1972 [SDOI2009]HH的项链
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1972
// Memory Limit: 500 MB
// Time Limit: 1500 ms
// Date: 2021-03-09 21:53:27
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0)
void Print(int *a,int n){
for(int i=1;i<n;i++)
printf("%d ",a[i]);
printf("%d\n",a[n]);
}
#define lowbit(x) x&(-x)
ll s[N];
int n,m,a[N];
void upd(int x,int v){
while(x<=n){
s[x]+=v;x+=lowbit(x);
}return;
}
ll que(int x){
ll ans=0;
while(x){
ans+=s[x];x-=lowbit(x);
}return ans;
}
struct query{
int l,r,k;
bool operator<(const query&q)const{
return r<q.r;
}
}q[N];
int ans[N],vis[N];
int main(){
scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);for(int i=1;i<=m;i++){
scanf("%d%d",&q[i].l,&q[i].r);q[i].k=i;
}
sort(q+1,q+m+1);
int p=1;
for(int i=1;i<=m;i++){
while(p<=q[i].r){
if(vis[a[p]]) upd(vis[a[p]],-1);
upd(p,1);
vis[a[p]]=p;p++;
}
ans[q[i].k]=que(q[i].r)-que(q[i].l-1);
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
```

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
```

### SP3267 DQUERY - D-query

传送门

https://blog.51cto.com/u_15326986/3328280