數(shù)算實(shí)習(xí)線段樹求區(qū)間眾數(shù)

1、POJ3368 線段樹 求區(qū)間眾數(shù) 整段離散化2011-09-22 23:41:08|分類： HYPERLINK /blog/ l m=0&t=1&c=fks_084065085087088064084081080095085081085074084087082066087 o 線段樹 線段樹|舉報(bào)|字號訂閱 HYPERLINK /blog/static/1749014132011822113155983/ /blog/static/1749014132011822113155983/ 題意：給定一個有序序列 然后求在給定區(qū)間里的眾數(shù)的長度第一步 離散化 （這里的離散化跟之前不同）在這邊，離散

2、化相當(dāng)于把一整段都染成同一個顏色，也就是給連續(xù)相同的數(shù)一個標(biāo)號同時還要記錄每一段顏色的起始位置和結(jié)束位置離散化完以后 對于一個區(qū)間 i , j 有一下幾種情況：1、marki = markj 則答案就是 j - i + 12、marki + 1 = markj 則答案為 max(標(biāo)號為marki的長度,標(biāo)號為markj的長度)3、markj - marki 1 則答案為 max(標(biāo)號為marki的長度,標(biāo)號為markj的長度),marki+1到markj-1這個區(qū)間里的最大長度) （即切割成三段）代碼：線段樹版本 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 求區(qū)間連續(xù)數(shù)的眾數(shù) 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 舉報(bào) 舉報(bà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個數(shù)表示詢問對于每次詢問的區(qū)間，回答該區(qū)間連續(xù)相同的數(shù) 這樣的段最長有多長思路：RMQ裸題特判下左右端點(diǎn)然后中間部分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+) /按區(qū)間長度遞增順序遞推 for(j=1;j+(1i)-1=n;j+) /區(qū)間起點(diǎn) 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