在线生成手机网站,网站改版后 存在大量404页面,黄页推广引流网站,织梦可以仿所有网站吗正题
链接#xff1a;http://poj.org/problem?id3368 大意
给出一个不下降序列#xff0c;求一个区域内最多相同的数的出现次数。 解题思路
线段树 用left表示左边的连续个数#xff0c;right表示右边的连续个数#xff0c;maxs表示最长的连续个数#xff0c;然后比较…正题
链接http://poj.org/problem?id3368 大意
给出一个不下降序列求一个区域内最多相同的数的出现次数。 解题思路
线段树 用left表示左边的连续个数right表示右边的连续个数maxs表示最长的连续个数然后比较。
如果左边的所有数都等于右边最左的数则 tree[k].lefttree[k∗2].righttree[k∗21].lefttree[k].lefttree[k∗2].righttree[k∗21].lefttree[k].left=tree[k*2].right+tree[k*2+1].left
如果右边的所有数都等于左边最右的数则 tree[k].righttree[k∗2].righttree[k∗21].lefttree[k].righttree[k∗2].righttree[k∗21].lefttree[k].right=tree[k*2].right+tree[k*2+1].left
如果左边最右边的数等于右边最左边的数则最优解在中间
tree[k].maxsmax(tree[k∗2].maxs,tree[k∗21].maxs,tree[k∗2].righttree[k∗21].left)tree[k].maxsmax(tree[k∗2].maxs,tree[k∗21].maxs,tree[k∗2].righttree[k∗21].left)
tree[k].maxs=max(tree[k*2].maxs,tree[k*2+1].maxs,tree[k*2].right+tree[k*2+1].left)然后用类似方法推区间 代码
#includecstdio
#includeiostream
using namespace std;
struct treenode{int l,r,maxs,left,right;
}tree[400001];
int n,m,x,y,num[100001];
char c;
void build(int k,int a,int b)//建树
{tree[k].la;tree[k].rb;if (ab) {tree[k].left1;tree[k].right1;tree[k].maxs1;return;}int wz(ab)/2;build(k*2,a,wz);build(k*21,wz1,b);if (tree[k*2].leftwz-a1num[wz]num[wz1]) tree[k].lefttree[k*2].righttree[k*21].left;elsetree[k].lefttree[k*2].left;if (tree[k*21].rightb-wznum[wz]num[wz1]) tree[k].righttree[k*2].righttree[k*21].left;elsetree[k].righttree[k*21].right;if (num[wz]num[wz1]) tree[k].maxsmax(max(tree[k*2].maxs,tree[k*21].maxs),tree[k*2].righttree[k*21].left);elsetree[k].maxsmax(tree[k*2].maxs,tree[k*21].maxs);
//统计
}
int find(int k,int a,int b)
{if (tree[k].lb||tree[k].ra||tree[k].rtree[k].l) return 0;if (tree[k].rb tree[k].la) return tree[k].maxs;int wz(tree[k].rtree[k].l)/2,m1,m11,m21;if (num[wz]num[wz1])mmin(wz-a1,tree[k*2].right)min(b-wz,tree[k*21].left);//中间最优解if (awz)m1find(k*2,a,b);//左边最优解if (bwz)m2find(k*21,a,b);//右边最优解mmax(m,max(m1,m2));//全部的最优解return m;
}
int main()
{while(scanf(%d,n)){if (n0) break;scanf(%d,m);for (int i1;in;i)scanf(%d,num[i]);memset(tree,0,sizeof(tree));build(1,1,n);for (int i1;im;i){scanf(%d%d,x,y);printf(%d\n,find(1,x,y));}}
}
