uva 11235 Frequent values(游程编码+区间最小值查询)


游程编码(Run Length Encoding , RLE)



用value[i] count[i] 分别表示 第i段的数值 和 出现次数;

num[p] left[p] right[p]分别表示位置p所在段的编号和左右端点的位置。




#include #include #include using namespace std; const int maxn = 100001; int n,q; int d[maxn][35]; int a[maxn]; int value[maxn],count_[maxn]; int num[maxn],left[maxn],right[maxn]; void RMQ_int(){ for(int i=0;i num[right_]-1) ans=max(ans,0); else{ ans=max(ans,RMQ(num[left_]+1,num[right_]-1)); } } printf("%d\n",ans); } } return 0; }

点击复制链接 与好友分享!回本站首页
上一篇:zoj3811Untrusted Patrol((bfs+并查集)

POJ 1089 Intervals 区间覆盖+ 贪心

TYVJ P2065(区间嵌套与统计)

POJ 2355(区间最大值-zkw线段树优化D

POJ 3171(区间覆盖最小代价)

区间完全覆盖问题 &&区间均取最少2个



区间dp-zoj3541-The Last Puzzle

HDU 3954 区间更新区间查询 打怪升级


uva 11235 Frequent values(游程编码+区间最小值查询)
ZOJ 3640 Help Me
uva 11235 Frequent values(游程编码+区间最小值查询)
CF 518C(Anya and
uva 11235 Frequent values(游程编码+区间最小值查询)
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-04 人气:6


  • POJ 3368 Frequent values(线段树区间合并) 2014-07-18

    Frequent values Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 13352 Accepted: 4913 Description You are given a sequence of n integers a1 , a2 , ... , an in non-decreasing order. In addition to that, you are given several queries consisti

  • UVA 818 Cutting Chains (DFS) 2012-01-11

    What a find! Anna Locke has just bought several links of chain some of which may be connected. They are made from zorkium, a material that was frequently used to manufacture jewelry in the last century, but is not used for that purpose anymore. It ha

  • UVa 548 Tree(建树,递归遍历) 2012-02-26

    题意 给你一个树的中序遍历和后序遍历 某个节点的权值为从根节点到该节点所经过节点的和 求权值最小的叶节点的值 如果存在多个 输出值最小的那个 把树建好就好说了 递归递归dfs msun保存最小叶节点权值 ans保存答案 #include #include #include using namespace std; const int maxn = 10005, INF = 0x3f3f3f3f; int in[maxn], post[maxn], msum, ans; struct node {

  • uva 1382 Distant Galaxy (枚举) 2012-03-30

    uva 1382 Distant Galaxy You are observing a distant galaxy using a telescope above the Astronomy Tower, and you think that a rectangle drawn in that galaxy whose edges are parallel to coordinate axes and contain maximum star systems on its edges has

  • UVa 704 - Colour Hash, 双向bfs,很给力 2012-03-30

    类型:隐式图搜索,双向bfs 原题: This puzzle consists of two wheels. Both wheels can rotate both clock and counter-clockwise. They contain 21 coloured pieces, 10 of which are rounded triangles and 11 of which are separators. Figure 1 shows the final position of ea

  • UVA - 10673 - Play with Floor and Ceil (简单数学!) 2012-04-12

    题目链接:Play with Floor and Ceil UVA - 10673 Play with Floor and Ceil Time Limit: 3000MS Memory Limit: Unknown 64bit IO Format: %lld & %llu SubmitStatus Description Problem A Play with Floor and Ceil Input: standard input Output: standard output Tim

  • UVA - 1069 Always an integer (模拟) 2012-07-01

    Description Combinatorics is a branch of mathematics chiefly concerned with counting discrete objects. For instance, how many ways can you pick two people out of a crowd ofn people? Into how many regions can you divide a circular disk by connectingn

  • UVA - 12075 Counting Triangles 2012-09-02

    Description Triangles are polygons with three sides and strictly positive area. Lattice triangles are the triangles all whose vertexes have integer coordinates. In this problem you have to find the number of lattice triangles in anMxN grid. For examp

  • UVA - 11645 Bits 2012-09-12

    Description Problem J Bits Input: Standard Input Output: Standard Output A bit is a binary digit, taking a logical value of either "1" or "0" (also referred to as "true" or "false" respectively). And every decimal number has a binary representation w

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.057 (s). 10 q(s)