HEOI2012 采花 两种做法

2018-01-23jzqjzq?

文章目录

原题链接:BZOJ2743
做法有两种:一种是莫队(然而被卡了),还有一种套个树状数组
说起来原来luogu这题的数据范围是1e5的呢……莫队轻松过QAQ

先说莫队吧
感觉和HH的项链十分相像,只不过HH是1,这里是2
一开始数据范围1e5,所以直接莫队不虚……
具体做法和HH其实一样的,就是add的时候统计答案一波
时间复杂度 $O(n\sqrt{n})$
luogu一开始T的原因竟是sort炸了?
奥妙重重

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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
using namespace std;
struct ppap{int x,y,k,w;}a[100001];
int n,c,m,now=0,ans[100001],b[100001],p[100001];
inline bool cmp(ppap a,ppap b){return a.k==b.k?a.y<b.y:a.k<b.k;}
inline void add(int x,int v){
b[p[x]]+=v;if(v<0&&b[p[x]]==1)now--;
if(v>0&&b[p[x]]==2)now++;
}
inline void work(){
int l=1,r=0;
for(int i=1;i<=m;i++){
while(l<a[i].x)add(l++,-1);
while(l>a[i].x)add(--l,1);
while(r<a[i].y)add(++r,1);
while(r>a[i].y)add(r--,-1);
ans[a[i].w]=now;
}
}
int main()
{
scanf("%d%d%d",&n,&c,&m);int k=sqrt(n);
for(int i=1;i<=n;i++)scanf("%d",&p[i]);
for(int i=1;i<=m;i++){
scanf("%d%d",&a[i].x,&a[i].y);a[i].w=i;
a[i].k=(a[i].x-1)/k+1;
}
sort(a+1,a+m+1,cmp);
work();
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}

接着说标算
我们还是离线来做。
对于一段区间,某数出现两次才会对答案造成贡献
那么我们对于每一个位置维护nex数组表示该数下一个出现位置
然后将询问离线(按左端点排序)后从左往右扫,更新区间
树状数组维护一下就好了,时间复杂度$O(nlogn)$

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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
using namespace std;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
write(x);puts("");
}
struct ppap{int x,y,p;}q[2000010];
int n,c,m,a[2000010],f[2000010],nex[2000010],p[2000010],ans[2000010];
inline void add(int x,int v){for(;x<=n;x+=x&-x)f[x]+=v;}
inline int ssum(int x){int ans=0;for(;x;x-=x&-x)ans+=f[x];return ans;}
inline bool cmp(ppap a,ppap b){return a.x<b.x;}
int main()
{
n=read();c=read();m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=n;i;i--)nex[i]=p[a[i]],p[a[i]]=i;
for(int i=1;i<=c;i++)if(p[i]&&nex[p[i]])add(nex[p[i]],1);
for(int i=1;i<=m;i++)q[i].x=read(),q[i].y=read(),q[i].p=i;
sort(q+1,q+m+1,cmp);
int l=1;
for(int i=1;i<=m;i++){
for(;l<q[i].x;l++){
if(nex[l])add(nex[l],-1);
if(nex[l]&&nex[nex[l]])add(nex[nex[l]],1);
}
ans[q[i].p]=ssum(q[i].y)-ssum(q[i].x-1);
}
for(int i=1;i<=m;i++)writeln(ans[i]);
return 0;
}