首页 > 代码库 > BZOJ1878: [SDOI2009]HH的项链
BZOJ1878: [SDOI2009]HH的项链
1878: [SDOI2009]HH的项链
Time Limit: 4 Sec Memory Limit: 64 MBSubmit: 1673 Solved: 808
[Submit][Status]
Description
Input
Output
Sample Input
1 2 3 4 3 5
3
1 2
3 5
2 6
Sample Output
2
4
HINT
对于20%的数据，N ≤ 100，M ≤ 1000；
对于40%的数据，N ≤ 3000，M ≤ 200000；
对于100%的数据，N ≤ 50000，M ≤ 200000。
Source
Day2
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #define inf 100000000012 #define maxn 50000+100013 #define maxm 200000+1000014 #define maxk 1000000+100015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 using namespace std;19 inline int read()20 {21 int x=0,f=1;char ch=getchar();22 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}23 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}24 return x*f;25 }26 struct rec{int x,y,id;}a[maxm];27 int s[maxn],ans[maxm],next[maxn],head[maxk],n,m;28 void add(int x,int y)29 {30 for(;x<=n;x+=x&(-x))s[x]+=y;31 }32 int sum(int x)33 {34 int t=0;35 for(;x;x-=x&(-x))t+=s[x];36 return t;37 }38 bool cmp(rec a,rec b)39 {40 return a.y<b.y;41 }42 int main()43 {44 freopen("input.txt","r",stdin);45 freopen("output.txt","w",stdout);46 n=read();47 for(int i=1;i<=n;i++)48 {49 int x=read();50 next[i]=head[x];51 head[x]=i;52 }53 m=read();54 for(int i=1;i<=m;i++)55 a[i].x=read(),a[i].y=read(),a[i].id=i;56 sort(a+1,a+m+1,cmp);57 int now=0;58 for(int i=1;i<=m;i++)59 {60 while(now<a[i].y)61 {62 now++;63 add(next[now]+1,1);64 add(now+1,-1);65 }66 ans[a[i].id]=sum(a[i].x);67 } 68 for(int i=1;i<=m;i++)printf("%d\n",ans[i]);69 return 0;70 }
2.按左端点排序
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #define inf 100000000012 #define maxn 50000+100013 #define maxm 200000+1000014 #define maxk 1000000+100015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 using namespace std;19 inline int read()20 {21 int x=0,f=1;char ch=getchar();22 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}23 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}24 return x*f;25 }26 struct rec{int x,y,id;}a[maxm];27 int s[maxn],ans[maxm],next[maxn],head[maxk],n,m,mx,b[maxn];28 void add(int x,int y)29 {30 for(;x<=n;x+=x&(-x))s[x]+=y;31 }32 int sum(int x)33 {34 int t=0;35 for(;x;x-=x&(-x))t+=s[x];36 return t;37 }38 bool cmp(rec a,rec b)39 {40 return a.x==b.x?a.y<b.y:a.x<b.x;41 }42 int main()43 {44 freopen("input.txt","r",stdin);45 freopen("output.txt","w",stdout);46 n=read();47 for(int i=1;i<=n;i++)b[i]=read();48 for(int i=n;i>=1;i--)49 {50 next[i]=head[b[i]];51 head[b[i]]=i;52 mx=max(mx,b[i]);53 }54 m=read();55 for(int i=1;i<=m;i++)56 a[i].x=read(),a[i].y=read(),a[i].id=i;57 sort(a+1,a+m+1,cmp);58 for(int i=1;i<=mx;i++)if(head[i])add(head[i],1);59 int now=1;60 for(int i=1;i<=m;i++)61 {62 while(now<a[i].x)63 {64 if(next[now])add(next[now],1); 65 now++;66 }67 ans[a[i].id]=sum(a[i].y)-sum(a[i].x-1);68 } 69 for(int i=1;i<=m;i++)printf("%d\n",ans[i]);70 return 0;71 }
本题数据规模较大，需要合理使用数据结构。题目中有两个元素：区间和颜色。如果直接使用线段树套平衡树，需要牵扯到“合并”操作，时间复杂度很高（比如当询问类似[2,N-1]的时候）。因此，需要做一些预处理工作使得询问更容易解决。
观察在某一区间内出现的某种颜色，假设有若干个同色点都在这个区间中，而该颜色只能计算一遍，因此我们需要找出一个有“代表性”的点，当然是第一个最有“代表性”。观察该点，以及它前后同色点的位置，有什么可以利用的规律？很显然，它的上一个同色点肯定在区间左侧，而同区间内的该颜色的其他点，它们的上一个同色点显然在区间内。这样，我们的工作便是找到询问区间[l,r]中这样的点x的个数：点x的上一个同色点在询问区间[l,r]左侧。
到这一步，我们有一个在线算法：建线段树，将询问分成O(lbN)个小区间分别处理。如果再套平衡树，需要二分查找才能求符合条件的点的“个数”。这样总的理论最坏复杂度为O(M(lbN)3)，虽然实际情况会好一些，但还是难以符合要求。我们分析一下该算法复杂度高的原因：平衡树难以很好支持求“个数”的运算，需要二分来实现。那么求“个数”效率最高的是什么数据结构？当然是树状数组。
当然，线段树是无法再套树状数组的，那样空间复杂度会达到O(N2)，所以我们要舍弃线段树，寻找新的算法。对于一堆“无序”的询问区间，如果没有线段树，便很难处理。因此我们考虑将区间按左端点排序，使其有序，然后从左到右扫描每个点。再考虑那些“上一个同色点在询问区间左侧”的点，我们的目的是快速求出该区间中这种点的个数。而这些点的上一个同色点因为在询问区间左侧，所以已经被扫描过，而区间内其他点却没有！这样，如果我们换个角度，改“上一个”为“下一个”，预处理出每个点i的下一个同色点的位置Next[i]，并且在扫描过该点i后使树状数组C[Next[i]]=1。那么对于询问区间[l,r]，答案便是Sumc[r]-Sumc[l-1]！这样，算法只有“加1”和“求和”两种操作。问题到此得到圆满解决， 最终时间复杂度为O(MlbN)。
BZOJ1878: [SDOI2009]HH的项链