数算实习线段树求区间众数

1、POJ3368 线段树 求区间众数 整段离散化2011-09-22 23:41:08|分类： HYPERLINK /blog/ l m=0&t=1&c=fks_084065085087088064084081080095085081085074084087082066087 o 线段树 线段树|举报|字号订阅 HYPERLINK /blog/static/1749014132011822113155983/ /blog/static/1749014132011822113155983/ 题意：给定一个有序序列 然后求在给定区间里的众数的长度第一步 离散化 （这里的离散化跟之前不同）在这边，离散

2、化相当于把一整段都染成同一个颜色，也就是给连续相同的数一个标号同时还要记录每一段颜色的起始位置和结束位置离散化完以后 对于一个区间 i , j 有一下几种情况：1、marki = markj 则答案就是 j - i + 12、marki + 1 = markj 则答案为 max(标号为marki的长度,标号为markj的长度)3、markj - marki 1 则答案为 max(标号为marki的长度,标号为markj的长度),marki+1到markj-1这个区间里的最大长度) （即切割成三段）代码：线段树版本 HYPERLINK /code/view/22684/ #include#inc

3、lude#include#define L(x) (x)1)#define R(x) (x)1;tnum.max=-200000000;if(left=right)return;makeTree(left,tnum.mid,L(num);makeTree(tnum.mid+1,right,R(num);voidupdate(intleft,intright,intnum,intval)if(valtnum.max)tnum.max=val;if(left=tnum.left&right=tnum.right)return;if(lefttnum.mid)update(left,right,R(

4、num),val);elseif(righttnum.mid)returnquerry(left,right,R(num);elseif(right=tnum.mid)returnquerry(left,right,L(num);elsereturnmax(querry(left,tnum.mid,L(num),querry(tnum.mid+1,right,R(num);intmain()intn,q,index,temp,val,i,left,right;while(1)/initscanf(%d,&n);if(n=0)break;scanf(%d,&q);index=-1;temp=-2

5、00000000;/离散化for(i=0;itemp)index+;temp=val;posi=index;lastindex=i;/建树makeTree(0,index,1);for(i=0;i=index;i+)if(i=0)update(i,i,1,lasti+1);elseupdate(i,i,1,lasti-lasti-1);/查询for(i=0;iq;i+)scanf(%d%d,&left,&right);if(rightleft)temp=left;left=right;right=left;left-;right-;if(posleft=posright)printf(%dn,

6、right-left+1);elseif(posleft=posright-1)printf(%dn,max(lastposleft-left+1,right-lastposleft);elsetemp=lastposleft-left+1;temp=max(temp,right-lastposright-1);temp=max(temp,querry(posleft+1,posright-1,1);printf(%dn,temp);return0; HYPERLINK /qq574857122/article/details/19862701 UVA 11235 求区间连续数的众数 RMQ分

7、类： HYPERLINK /qq574857122/article/category/1535763 水题 HYPERLINK /qq574857122/article/category/1739345 RMQ2014-02-25 00:32393人阅读 HYPERLINK /qq574857122/article/details/19862701 l comments 评论(0) HYPERLINK javascript:void(0); o 收藏 收藏 HYPERLINK /qq574857122/article/details/19862701 l report o 举报 举报题目链接：

8、 HYPERLINK /index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2176 t _blank /index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2176题意：给定n长的序列， query次询问下面n个数表示询问对于每次询问的区间，回答该区间连续相同的数 这样的段最长有多长思路：RMQ裸题特判下左右端点然后中间部分RMQ即可#include#include#include#includeusing namespace

9、 std;const int MAXN = 100100;int n,query;int AMAXN;int FMinMAXN20,FMaxMAXN20;void Init()int i,j;for(i=1;i=n;i+)FMini0=FMaxi0=Ai;for(i=1;(1i)=n;i+) /按区间长度递增顺序递推 for(j=1;j+(1i)-1=n;j+) /区间起点 FMinji=min(FMinji-1,FMinj+(1(i-1)i-1);FMaxji=max(FMaxji-1,FMaxj+(1(i-1)i-1); int Query(int l,int r)int k=(int)(

10、log(double(r-l+1)/log(double)2);return max(FMaxlk,FMaxr-(1k)+1k);int numMAXN, lMAXN, rMAXN;int main()int i,j,a,b;while(scanf(%d,&n), n)scanf(%d,&query);int cnt = 1;int L = 1, R = 1;for(i=1;i=n;i+)scanf(%d,&numi);if(numi = numi-1 & i!=1)R+; cnt+;if(i!=1 & numi!=numi-1) | i=n)for(j = L; j = R; j+)Aj = cnt;lj = L;rj = R;cnt = 1;L = R = i;for(j = L; j b)swap(a,b);L = ra; if(L=b)printf(%dn, b-a+1);continue;R = lb; if(R=a)printf(%dn, b-a+1);continue;int ans