题意:
给你N个数,按照非减序列给出;
然后M个询问,每个询问一个区间,问在(a,b)之间最多相同数量数字的个数。
Sample Input
10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10 0
Sample Output
1 4 3
思路:
第一道线段树,以前只会树状数组,然后今天碰上这道题,就去学习了一下线段树。
发现其实树状数组能做的题目线段树都可以做,所以还是得好好弄懂这个。
参考了别人的解题报告,总算是写出来了。
期间WA了无数次,各种小错误,最后终于A掉了。太辛苦了
#include <iostream> #include <cstdio> #include <algorithm> #include <string> #include <cmath> #include <cstring> #include <queue> #include <set> #include <vector> #include <stack> #include <map> #include <iomanip> #define PI acos(-1.0) #define Max 100005 #define inf 1<<28 using namespace std; struct kdq { int l,r,max; } tree[Max*4];//树 struct qdk { int start,end; } seg[Max]; int point[Max]; int hash[Max]; int k=0; void build_tree(int l,int r,int u)//建树 { tree[u].l=l; tree[u].r=r; if(l==r) { tree[u].max=seg[l].end-seg[l].start+1; return ; } int mid=(l+r)/2; build_tree(l,mid,u<<1);//左子树 build_tree(mid+1,r,(u<<1)+1);//右子树 tree[u].max=max(tree[u<<1].max,tree[(u<<1)+1].max);//父节点的最大值是左子树和右子树的最大值 } int query(int left,int right,int u)//询问 { if(left==tree[u].l&&right==tree[u].r) return tree[u].max; if(right<=tree[u<<1].r)//如果right小于左子树的 right,则将left,right插入左子树。 return query(left,right,u<<1); if(left>=tree[(u<<1)+1].l)//如果left大于右子树的left,则将left,right插入右子树。 return query(left,right,(u<<1)+1); int a=query(left,tree[u<<1].r,u<<1); int b=query(tree[(u<<1)+1].l,right,(u<<1)+1); return max(a,b);//输出最大值 } int main() { int i,j,l,n,m; while(scanf("%d",&n),n) { cin>>m; for(i=1; i<=n; i++) scanf("%d",&point[i]); k=0; int pre=10000000; for(i=1; i<=n; i++)//离散化处理 { if(point[i]!=pre) { k++; seg[k].start=i; seg[k].end=i; pre=point[i]; } else seg[k].end=i;//所有相同的数为一个集合。 hash[i]=k; } int pos1,pos2; build_tree(1,k,1); int aa,bb; while(m--) { scanf("%d%d",&aa,&bb); pos1=hash[aa]; pos2=hash[bb]; if(hash[aa]==hash[bb])//如果在一个集合内,则输出他们的差值记为最大的出现次数。 { printf("%d\n",bb-aa+1); continue; } int num3=0; int num1=seg[pos1].end-aa+1;//point[aa]的出现次数 int num2=bb-seg[pos2].start+1;//point[bb]的出现次数 if(pos2-pos1>1)//如果两个集合之间还有集合 num3=query(pos1+1,pos2-1,1);//则继续计算 printf("%d\n",max(max(num1,num2),num3)); } } return 0; }
继续继续