±RMQ问题指被查询序列每一对相邻数的值的差要么为1要么为-1,这种特殊的RMQ问题的解决代码如下C代码#includeiostream#includevector#includealgorithm#includerandomusingnamespacestd;structm_info{longlongm_value;size_t index;m_info(longlongm,size_t i):m_value(m),index(i){}m_info()default;booloperator(constm_infobe_compared)const{returnm_valuebe_compared.m_valueindexbe_compared.index;}booloperator!(constm_infobe_compared)const{return!(operator(be_compared));}};constm_infomin_m_info(constm_infoleft,constm_inforight){if(left.m_valueright.m_value){returnleft;}returnright;}voidSparseTable(vectorvectorm_infod,vectorlonglongseq){for(size_t i0;iseq.size();i){d[i][0]m_info(seq[i],i);}for(size_t i1;(1i)seq.size();i){for(size_t j0;jseq.size()-(1i);j){if(d[j][i-1].m_valued[j(1i-1)][i-1].m_value){d[j][i]d[j][i-1];}else{d[j][i]d[j(1i-1)][i-1];}}}}m_infoquery(size_t i,size_t j,vectorvectorm_infod){size_t lj-i1;size_t klog2(l);if(d[i][k].m_valued[j-(1k)1][k].m_value)returnd[i][k];returnd[j-(1k)1][k];}size_tlog2(size_t N){size_t k0;while(1ullkN){k;}--k;returnk;}classConstraintRMQ{public:m_infoqueryRMQ(size_t i,size_t j);ConstraintRMQ(vectorlonglongv);private:size_t N;size_t segment_length;size_t block_num;vectorlonglongvalue_seq;vectorvectorvectorm_infogroup_in_query_map_table;vectorsize_tindex_for_every_block;vectorvectorm_infogroup_between_query_table;vectorsize_tmin_in_block_index;voidpreprocessForConstraintRMQ();voidpreprocessAllPlusMinusSeq(size_t level,size_t bit_mode_index,vectorlonglongminus_add_value);voidgetFirstValueForBlock(size_t block_index,m_inforesult);};voidConstraintRMQ::getFirstValueForBlock(size_t first_value_in_block_offset,m_inforesult){result.m_valuevalue_seq[first_value_in_block_offset];result.indexfirst_value_in_block_offset;}m_infoConstraintRMQ::queryRMQ(size_t i,size_t j)//i,j从0开始{if(ij||jN){cout非法的查询索引!endl;exit(-1);}size_t i_block_indexi/segment_length;size_t i_in_block_indexi%segment_length;size_t j_block_indexj/segment_length;size_t j_in_block_indexj%segment_length;m_info result;if(i_block_indexj_block_index){resultquery(i_in_block_index,j_in_block_index,group_in_query_map_table[index_for_every_block[i_block_index]]);getFirstValueForBlock(i_block_index*segment_length,result);}else{size_t block_index;if(i_in_block_index0j_in_block_indexsegment_length-1){resultquery(i_block_index,j_block_index,group_between_query_table);block_indexresult.index;resultm_info(result.m_value,min_in_block_index[block_index]);}else{m_info r_ref;m_info result2;m_info result3;if(i_block_index1j_block_index){result2query(i_in_block_index,segment_length-1,group_in_query_map_table[index_for_every_block[i_block_index]]);getFirstValueForBlock(i_block_index*segment_length,result2);result3query(0,j_in_block_index,group_in_query_map_table[index_for_every_block[j_block_index]]);getFirstValueForBlock(j_block_index*segment_length,result3);r_refmin_m_info(result2,result3);}else{if(i_in_block_index0){resultquery(i_block_index,j_block_index-1,group_between_query_table);}elseif(j_in_block_indexsegment_length-1){resultquery(i_block_index1,j_block_index,group_between_query_table);}else{resultquery(i_block_index1,j_block_index-1,group_between_query_table);}block_indexresult.index;resultm_info(result.m_value,min_in_block_index[block_index]);if(i_in_block_index0||j_in_block_indexsegment_length-1){if(i_in_block_index0){result2query(0,j_in_block_index,group_in_query_map_table[index_for_every_block[j_block_index]]);getFirstValueForBlock(j_block_index*segment_length,result2);}else{result2query(i_in_block_index,segment_length-1,group_in_query_map_table[index_for_every_block[i_block_index]]);getFirstValueForBlock(i_block_index*segment_length,result2);}r_refmin_m_info(result,result2);////////////////}else{result2query(i_in_block_index,segment_length-1,group_in_query_map_table[index_for_every_block[i_block_index]]);getFirstValueForBlock(i_block_index*segment_length,result2);result3query(0,j_in_block_index,group_in_query_map_table[index_for_every_block[j_block_index]]);getFirstValueForBlock(j_block_index*segment_length,result3);r_refmin_m_info(result,min_m_info(result2,result3));}}if(i_block_index1j_block_index||r_ref!result){if(i_block_index1j_block_indexr_refresult3||i_block_index1!j_block_index(i_in_block_index!0j_in_block_index!segment_length-1r_refresult3)){returnresult3;}else{returnresult2;}}}}returnresult;}ConstraintRMQ::ConstraintRMQ(vectorlonglongv):value_seq(v),N(v.size()),segment_length((log2(N)1)1),group_in_query_map_table(1ullsegment_length-1,vectorvectorm_info(segment_length,vectorm_info(log2(segment_length)1))){if(value_seq.empty()){coutERROR输入序列为空!endl;exit(-1);}for(size_t i1;ivalue_seq.size();i){if(value_seq[i]-value_seq[i-1]!1value_seq[i]-value_seq[i-1]!-1){coutERROR输入序列不是-1序列!endl;exit(-1);}}size_t r;if((rN%segment_length)!0){block_numN/segment_length1;if(value_seq.back()(1ll63)){cout错误末端值等于最小值!endl;exit(-1);}rsegment_length-r;booloriginalfalse;for(size_t i1;ir;i){if(!original){value_seq.push_back(value_seq[N-1]-1);}else{value_seq.push_back(value_seq[N-1]);}original!original;}}else{block_numN/segment_length;}new(index_for_every_block)vectorsize_t(block_num);new(group_between_query_table)vectorvectorm_info(block_num,vectorm_info(log2(block_num)1));new(min_in_block_index)vectorsize_t(block_num);preprocessForConstraintRMQ();}voidConstraintRMQ::preprocessForConstraintRMQ(){vectorlonglongminus_add_value(segment_length,0);preprocessAllPlusMinusSeq(0,0,minus_add_value);vectorlonglongm_value_for_every_block(block_num);size_t start_index_for_left_bound0;for(size_t i0;iblock_num;i){size_t bit_mode_index0;size_t jstart_index_for_left_bound1;for(;;){if(value_seq[j]-value_seq[j-1]1){bit_mode_index|1;}j;if(jstart_index_for_left_boundsegment_length)break;bit_mode_index1;}index_for_every_block[i]bit_mode_index;m_info tquery(0,segment_length-1,group_in_query_map_table[bit_mode_index]);m_value_for_every_block[i]t.m_valuevalue_seq[start_index_for_left_bound];min_in_block_index[i]t.indexstart_index_for_left_bound;start_index_for_left_boundj;}SparseTable(group_between_query_table,m_value_for_every_block);}voidConstraintRMQ::preprocessAllPlusMinusSeq(size_t level,size_t bit_mode_index,vectorlonglongminus_add_value)//true为正,bit 1false为负 bit 0{if(level1segment_length){SparseTable(group_in_query_map_table[bit_mode_index],minus_add_value);return;}minus_add_value[level1]minus_add_value[level]1;if(level2segment_length){preprocessAllPlusMinusSeq(level1,bit_mode_index|1,minus_add_value);}else{preprocessAllPlusMinusSeq(level1,(bit_mode_index|1)1,minus_add_value);}minus_add_value[level1]minus_add_value[level]-1;if(level2segment_length){preprocessAllPlusMinusSeq(level1,bit_mode_index,minus_add_value);}else{preprocessAllPlusMinusSeq(level1,bit_mode_index1,minus_add_value);}}intmain(){constintN256;vectorlonglongrmq_seq(N);rmq_seq[0]N;for(size_t i1;iN;i){if(rand()%2){rmq_seq[i]rmq_seq[i-1]1;}else{rmq_seq[i]rmq_seq[i-1]-1;}}ConstraintRMQobj(rmq_seq);for(size_t i0;irmq_seq.size()-1;i){for(size_t ji1;jrmq_seq.size();j){m_info robj.queryRMQ(i,j);longlongmrmq_seq[i];for(size_t ki1;kj;k){if(rmq_seq[k]m){mrmq_seq[k];}}if(r.m_valuem){cout[i,j]查询结果正确!endl;}else{cout[i,j]查询结果错误!endl;exit(-1);}}}return0;}
±RMQ问题指被查询序列每一对相邻数的值的差要么为1要么为-1,这种特殊的RMQ问题的解决代码如下C代码#includeiostream#includevector#includealgorithm#includerandomusingnamespacestd;structm_info{longlongm_value;size_t index;m_info(longlongm,size_t i):m_value(m),index(i){}m_info()default;booloperator(constm_infobe_compared)const{returnm_valuebe_compared.m_valueindexbe_compared.index;}booloperator!(constm_infobe_compared)const{return!(operator(be_compared));}};constm_infomin_m_info(constm_infoleft,constm_inforight){if(left.m_valueright.m_value){returnleft;}returnright;}voidSparseTable(vectorvectorm_infod,vectorlonglongseq){for(size_t i0;iseq.size();i){d[i][0]m_info(seq[i],i);}for(size_t i1;(1i)seq.size();i){for(size_t j0;jseq.size()-(1i);j){if(d[j][i-1].m_valued[j(1i-1)][i-1].m_value){d[j][i]d[j][i-1];}else{d[j][i]d[j(1i-1)][i-1];}}}}m_infoquery(size_t i,size_t j,vectorvectorm_infod){size_t lj-i1;size_t klog2(l);if(d[i][k].m_valued[j-(1k)1][k].m_value)returnd[i][k];returnd[j-(1k)1][k];}size_tlog2(size_t N){size_t k0;while(1ullkN){k;}--k;returnk;}classConstraintRMQ{public:m_infoqueryRMQ(size_t i,size_t j);ConstraintRMQ(vectorlonglongv);private:size_t N;size_t segment_length;size_t block_num;vectorlonglongvalue_seq;vectorvectorvectorm_infogroup_in_query_map_table;vectorsize_tindex_for_every_block;vectorvectorm_infogroup_between_query_table;vectorsize_tmin_in_block_index;voidpreprocessForConstraintRMQ();voidpreprocessAllPlusMinusSeq(size_t level,size_t bit_mode_index,vectorlonglongminus_add_value);voidgetFirstValueForBlock(size_t block_index,m_inforesult);};voidConstraintRMQ::getFirstValueForBlock(size_t first_value_in_block_offset,m_inforesult){result.m_valuevalue_seq[first_value_in_block_offset];result.indexfirst_value_in_block_offset;}m_infoConstraintRMQ::queryRMQ(size_t i,size_t j)//i,j从0开始{if(ij||jN){cout非法的查询索引!endl;exit(-1);}size_t i_block_indexi/segment_length;size_t i_in_block_indexi%segment_length;size_t j_block_indexj/segment_length;size_t j_in_block_indexj%segment_length;m_info result;if(i_block_indexj_block_index){resultquery(i_in_block_index,j_in_block_index,group_in_query_map_table[index_for_every_block[i_block_index]]);getFirstValueForBlock(i_block_index*segment_length,result);}else{size_t block_index;if(i_in_block_index0j_in_block_indexsegment_length-1){resultquery(i_block_index,j_block_index,group_between_query_table);block_indexresult.index;resultm_info(result.m_value,min_in_block_index[block_index]);}else{m_info r_ref;m_info result2;m_info result3;if(i_block_index1j_block_index){result2query(i_in_block_index,segment_length-1,group_in_query_map_table[index_for_every_block[i_block_index]]);getFirstValueForBlock(i_block_index*segment_length,result2);result3query(0,j_in_block_index,group_in_query_map_table[index_for_every_block[j_block_index]]);getFirstValueForBlock(j_block_index*segment_length,result3);r_refmin_m_info(result2,result3);}else{if(i_in_block_index0){resultquery(i_block_index,j_block_index-1,group_between_query_table);}elseif(j_in_block_indexsegment_length-1){resultquery(i_block_index1,j_block_index,group_between_query_table);}else{resultquery(i_block_index1,j_block_index-1,group_between_query_table);}block_indexresult.index;resultm_info(result.m_value,min_in_block_index[block_index]);if(i_in_block_index0||j_in_block_indexsegment_length-1){if(i_in_block_index0){result2query(0,j_in_block_index,group_in_query_map_table[index_for_every_block[j_block_index]]);getFirstValueForBlock(j_block_index*segment_length,result2);}else{result2query(i_in_block_index,segment_length-1,group_in_query_map_table[index_for_every_block[i_block_index]]);getFirstValueForBlock(i_block_index*segment_length,result2);}r_refmin_m_info(result,result2);////////////////}else{result2query(i_in_block_index,segment_length-1,group_in_query_map_table[index_for_every_block[i_block_index]]);getFirstValueForBlock(i_block_index*segment_length,result2);result3query(0,j_in_block_index,group_in_query_map_table[index_for_every_block[j_block_index]]);getFirstValueForBlock(j_block_index*segment_length,result3);r_refmin_m_info(result,min_m_info(result2,result3));}}if(i_block_index1j_block_index||r_ref!result){if(i_block_index1j_block_indexr_refresult3||i_block_index1!j_block_index(i_in_block_index!0j_in_block_index!segment_length-1r_refresult3)){returnresult3;}else{returnresult2;}}}}returnresult;}ConstraintRMQ::ConstraintRMQ(vectorlonglongv):value_seq(v),N(v.size()),segment_length((log2(N)1)1),group_in_query_map_table(1ullsegment_length-1,vectorvectorm_info(segment_length,vectorm_info(log2(segment_length)1))){if(value_seq.empty()){coutERROR输入序列为空!endl;exit(-1);}for(size_t i1;ivalue_seq.size();i){if(value_seq[i]-value_seq[i-1]!1value_seq[i]-value_seq[i-1]!-1){coutERROR输入序列不是-1序列!endl;exit(-1);}}size_t r;if((rN%segment_length)!0){block_numN/segment_length1;if(value_seq.back()(1ll63)){cout错误末端值等于最小值!endl;exit(-1);}rsegment_length-r;booloriginalfalse;for(size_t i1;ir;i){if(!original){value_seq.push_back(value_seq[N-1]-1);}else{value_seq.push_back(value_seq[N-1]);}original!original;}}else{block_numN/segment_length;}new(index_for_every_block)vectorsize_t(block_num);new(group_between_query_table)vectorvectorm_info(block_num,vectorm_info(log2(block_num)1));new(min_in_block_index)vectorsize_t(block_num);preprocessForConstraintRMQ();}voidConstraintRMQ::preprocessForConstraintRMQ(){vectorlonglongminus_add_value(segment_length,0);preprocessAllPlusMinusSeq(0,0,minus_add_value);vectorlonglongm_value_for_every_block(block_num);size_t start_index_for_left_bound0;for(size_t i0;iblock_num;i){size_t bit_mode_index0;size_t jstart_index_for_left_bound1;for(;;){if(value_seq[j]-value_seq[j-1]1){bit_mode_index|1;}j;if(jstart_index_for_left_boundsegment_length)break;bit_mode_index1;}index_for_every_block[i]bit_mode_index;m_info tquery(0,segment_length-1,group_in_query_map_table[bit_mode_index]);m_value_for_every_block[i]t.m_valuevalue_seq[start_index_for_left_bound];min_in_block_index[i]t.indexstart_index_for_left_bound;start_index_for_left_boundj;}SparseTable(group_between_query_table,m_value_for_every_block);}voidConstraintRMQ::preprocessAllPlusMinusSeq(size_t level,size_t bit_mode_index,vectorlonglongminus_add_value)//true为正,bit 1false为负 bit 0{if(level1segment_length){SparseTable(group_in_query_map_table[bit_mode_index],minus_add_value);return;}minus_add_value[level1]minus_add_value[level]1;if(level2segment_length){preprocessAllPlusMinusSeq(level1,bit_mode_index|1,minus_add_value);}else{preprocessAllPlusMinusSeq(level1,(bit_mode_index|1)1,minus_add_value);}minus_add_value[level1]minus_add_value[level]-1;if(level2segment_length){preprocessAllPlusMinusSeq(level1,bit_mode_index,minus_add_value);}else{preprocessAllPlusMinusSeq(level1,bit_mode_index1,minus_add_value);}}intmain(){constintN256;vectorlonglongrmq_seq(N);rmq_seq[0]N;for(size_t i1;iN;i){if(rand()%2){rmq_seq[i]rmq_seq[i-1]1;}else{rmq_seq[i]rmq_seq[i-1]-1;}}ConstraintRMQobj(rmq_seq);for(size_t i0;irmq_seq.size()-1;i){for(size_t ji1;jrmq_seq.size();j){m_info robj.queryRMQ(i,j);longlongmrmq_seq[i];for(size_t ki1;kj;k){if(rmq_seq[k]m){mrmq_seq[k];}}if(r.m_valuem){cout[i,j]查询结果正确!endl;}else{cout[i,j]查询结果错误!endl;exit(-1);}}}return0;}
