• 「CODEVS1081」线段树练习 2(线段树 / 树状数组)

    「CODEVS1081」线段树练习 2(线段树 / 树状数组)

    题目描述 Description给你N个数,有两种操作1:给区间[a,b]的所有数都增加X2:询问第i个数是什么?输入描述 InputDescription第一行一个正整数n,接下来n行n个整数,再接下来一个正整数Q,表示操作的个数.接下来Q行每行若干个整数。如果第一个数是1,后接3个正整数a,b,X,表示在区间[a,b]内每个数增加X,如果是2,后面跟1个整数i,表示询问第i个位置的数是多少。输出描述 OutputDescription对于每个询问输出一行一个答...

    02014年1月17日4,574线段树,树状数组
  • 「vijos1514」天才的记忆

    「vijos1514」天才的记忆

    背景神仙飞啊飞描述从前有个人名叫WandNandB,他有着天才般的记忆力,他珍藏了许多许多的宝藏。在他离世之后留给后人一个难题(专门考验记忆力的啊!),如果谁能轻松回答出这个问题,便可以继承他的宝藏。题目是这样的:给你一大串数字(编号为1到N,大小可不一定哦!),在你看过一遍之后,它便消失在你面前,随后问题就出现了,给你M个询问,每次询问就给你两个数字A,B,要求你瞬间就说出属于A到B这段区间内的最大数。一天...

    02014年1月7日3,403ST表
  • 「BZOJ3039」玉蟾宫

    「BZOJ3039」玉蟾宫

    Description有一天,小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫,玉蟾宫宫主蓝兔盛情地款待了它们,并赐予它们一片土地。这片土地被分成N*M个格子,每个格子里写着'R'或者'F',R代表这块土地被赐予了rainbow,F代表这块土地被赐予了freda。现在freda要在这里卖萌。。。它要找一块矩形土地,要求这片土地都标着'F'并且面积最大。但是rainbow和freda的OI水平都弱爆了,找不出这块土地,而蓝兔也想看freda卖萌(她显...

    02014年1月6日4,908单调栈
  • 「vijos1083」小白逛公园

    「vijos1083」小白逛公园

    描述小新经常陪小白去公园玩,也就是所谓的遛狗啦…在小新家附近有一条“公园路”,路的一边从南到北依次排着n个公园,小白早就看花了眼,自己也不清楚该去哪些公园玩了。一开始,小白就根据公园的风景给每个公园打了分-.-。小新为了省事,每次遛狗的时候都会事先规定一个范围,小白只可以选择第a个和第b个公园之间(包括a、b两个公园)选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时,由于一些公园的景观...

    02013年12月31日4,816线段树
  • 「vijos1659」河蟹王国

    「vijos1659」河蟹王国

    描述河蟹王国有一位河蟹国王,他的名字叫羊驼。河蟹王国富饶安定,人们和谐相处。有一天,羊驼国王心血来潮,想在一部分人中挑出最和谐的人。于是,羊驼国王将他的子民排成了一列(==!!b汗~好长呀)。每个人都有一个初始的和谐值。羊驼国王每次会选择一个区间[L,R],这个区间中和谐值最大的人就是国王选出的人。而且,在某一时间,区间[L',R']里的人会变得熟悉,因此他们每个人的和谐值都会上升一个相同的值C。羊驼国王想知道...

    22013年12月30日3,610线段树
  • 「JoyOI1473」校门外的树3

    「JoyOI1473」校门外的树3

    描述Description校门外有很多树,有苹果树,香蕉树,有会扔石头的,有可以吃掉补充体力的……如今学校决定在某个时刻在某一段种上一种树,保证任一时刻不会出现两段相同种类的树,现有两个操作:K=1,读入l,r表示在l~r之间种上的一种树K=2,读入l,r表示询问l~r之间能见到多少种树(l,r>0)输入格式InputFormat第一行n,m表示道路总长为n,共有m个操作接下来m行为m个操作输出格式OutputFormat对于每个k=2输出一个答案样例输...

    42013年12月30日4,852线段树
  • 「vijos1512」SuperBrother打鼹鼠

    「vijos1512」SuperBrother打鼹鼠

    背景SuperBrother在机房里闲着没事干(再对比一下他的NOIP,真是讽刺啊......),于是便无聊地开始玩“打鼹鼠”......描述在这个“打鼹鼠”的游戏中,鼹鼠会不时地从洞中钻出来,不过不会从洞口钻进去(鼹鼠真胆大……)。洞口都在一个大小为n(n<=1024)的正方形中。这个正方形在一个平面直角坐标系中,左下角为(0,0),右上角为(n-1,n-1)。洞口所在的位置都是整点,就是横纵坐标都为整数的点。而SuperBrother也不时地会想知道...

    02013年12月30日3,663树状数组
  • 「CODEVS1082」线段树练习 3

    「CODEVS1082」线段树练习 3

    题目描述 Description给你N个数,有两种操作:1:给区间[a,b]的所有数增加X2:询问区间[a,b]的数的和。输入描述 InputDescription第一行一个正整数n,接下来n行n个整数, 再接下来一个正整数Q,每行表示操作的个数, 如果第一个数是1,后接3个正整数, 表示在区间[a,b]内每个数增加X,如果是2, 表示操作2询问区间[a,b]的和是多少。输出描述 OutputDescription对于每个询问输出一行一个答案样例输入...

    02013年12月28日4,492线段树
  • 树状数组入门

    树状数组入门

    如果给定一个数组,要你求里面所有数的和,一般都会想到累加。但是当那个数组很大的时候,累加就显得太耗时了,时间复杂度为O(n),并且采用累加的方法还有一个局限,那就是,当修改掉数组中的元素后,仍然要你求数组中某段元素的和,就显得麻烦了。所以我们就要用到树状数组,他的时间复杂度为O(lgn),相比之下就快得多。下面就讲一下什么是树状数组:一般讲到树状数组都会少不了下面这个图:下面来分析一下上面那个图看能得出...

    42013年12月28日4,631树状数组
  • 「CODEVS3185 – 3187」队列练习1, 2, 3

    「CODEVS3185 - 3187」队列练习1, 2, 3

    队列练习1http://codevs.com/problem/3185/[crayon-66058eb37f35d067209910/]队列练习2http://codevs.com/problem/3186/[crayon-66058eb37f36a415464976/]队列练习3http://codevs.com/problem/3187/[crayon-66058eb37f371524523063/] ...

    82013年12月26日2,396基础数据结构
  • NOI2004郁闷的出纳员

    NOI2004郁闷的出纳员

    输入描述 InputDescription第一行有两个非负整数n和min。n表示下面有多少条命令,min表示工资下界。接下来的n行,每行表示一条命令。命令可以是以下四种之一:名称格式作用I命令I_k新建一个工资档案,初始工资为k。如果某员工的初始工资低于工资下界,他将立刻离开公司。A命令A_k把每位员工的工资加上kS命令S_k把每位员工的工资扣除kF命令F_k查询第k多的工资_(下划线)表示一个空格,I命令、A命令、S命令中的k是一个...

    82013年12月26日13,139treap,splay,线段树
  • 「POJ2892」Tunnel Warfare

    「POJ2892」Tunnel Warfare

    DescriptionDuringtheWarofResistanceAgainstJapan,tunnelwarfarewascarriedoutextensivelyinthevastareasofnorthChinaPlain.Generallyspeaking,villagesconnectedbytunnelslayinaline.Exceptthetwoattheends,everyvillagewasdirectlyconnectedwithtwoneighboringones.Frequentlytheinvaderslaunchedattackonsomeofthevillagesanddestroyedthepartsoftunnelsinthem.TheEighthRouteArmycommandersrequestedthelatest...

    02013年12月25日4,076treap