• 【分块】数列分块入门1-9 by hzwer

    【分块】数列分块入门1-9 by hzwer

    整理一些思路,然后我会在CH小组内出一系列的分块训练题https://www.contesthunter.org/group/%E7%A6%8F%E5%BB%BA%E5%B8%88%E5%A4%A7%E9%99%84%E4%B8%AD已完结由于每道题题面太长,限于篇幅,只给出大意,具体题目见小组内赛题,代码附在文末 可能涉及的几个词语解释:区间:数列中连续一段的元素区间操作:将某个区间[a,b]的所有元素进行某种改动的操作块:我们将数列划分成若干个不相交的区间,每个区间...

    132016年6月18日2,987分块
  • 【小奇模拟赛2】小奇的危机

    【小奇模拟赛2】小奇的危机

    【题目背景】小奇驾驶飞船来到了一个奇怪的星球,这个星球的所以城市都在地下,而且由于环境不断恶化,星球上发生了可怕的生化危机。【问题描述】星球上有n个城市,标号为1-n,用n-1条双向通道连接,保证任意两个城市能互相到达。生化危机爆发了!但由于政府安全能力有限,安全区只包括在标号l到r的城市,小奇现在在城市x,它想知道最近的安全城市的距离。【输入格式】第一行有1个整数n。接下来n-1行,每行3个整数u,v,l,表示u,...

    02016年5月22日1,151STL,dijkstra,分块
  • 【cf551X】Codeforces Round #307 (Div. 2)

    【cf551X】Codeforces Round #307 (Div. 2)

    A.GukiZandContest排序[crayon-5881c14c3511a079534571/]B.ZgukistringZ统计每个串每个字母的使用次数,枚举串b出现次数,计算c最大出现次数,更新答案我不知道为什么写太挫还能T[crayon-5881c14c35127538922757/]C.GukiZhatesBoxes感受一下可以发现,比较远的箱子堆去的人越少越好所以二分答案后,从后往前贪心check即可[crayon-5881c14c3513a251176706/]D.GukiZandBinaryOperations按位考虑,给定K以后,每一位...

  • 【bzoj3809】Gty的二逼妹子序列

    【bzoj3809】Gty的二逼妹子序列

    DescriptionAutumn和Bakser又在研究Gty的妹子序列了!但他们遇到了一个难题。对于一段妹子们,他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。为了方便,我们规定妹子们的美丽度全都在[1,n]中。给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n),对于m(1<=m<=1000000)次询问“l,r,a,b”,每次输出sl...sr中,权值∈[a,b]的权值的种类数。Input第一行包括两个整数n,m(1<=n<=100...

    192014年12月21日3,301分块,莫队算法
  • 【codechefFNCS】Chef and Churu

    【codechefFNCS】Chef and Churu

    题解分块水过将函数分块,每一块大小√n,预处理一块内的函数统计每一个数字的次数,以及这一块的答案这一部分n√n并用树状数组维护a的前缀和,线段树呵呵。。。对于询问将整块的答案加起来,其余部分的每个函数在树状数组中查询对于修改修改树状数组依照每一个数字在每一块的次数,更新每一块的答案这一部分n√nlogn若理论分析似乎分块设小会更优,但若考虑下常数会发现好像并不会。。。注意本题要用unsignedlonglong还有一个很牛...

    02014年12月18日1,134分块,树状数组
  • 【bzoj3289】Mato的文件管理

    【bzoj3289】Mato的文件管理

    DescriptionMato同学从各路神犇以各种方式(你们懂的)收集了许多资料,这些资料一共有n份,每份有一个大小和一个编号。为了防止他人偷拷,这些资料都是加密过的,只能用Mato自己写的程序才能访问。Mato每天随机选一个区间[l,r],他今天就看编号在此区间内的这些资料。Mato有一个习惯,他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来,再用他写的排序程序给文件大小排序。排序程序可以在1单位时间内...

    42014年12月3日2,047树状数组,莫队算法
  • WC2013糖果公园

    WC2013糖果公园

    DescriptionInputOutputSampleInputSampleOutput841312784HINT题解30分暴力。。。模拟即可第4-5个测试点由于m较小,且在链上,所以可以用前缀和水过。。。对于每个询问统计每种糖果的答案贡献满分做法带修改树上莫队。。。参见vfk的博客http://vfleaking.blog.163.com/blog/#m=0&t=1&c=fks_084070093085082071086081080095085081085075084081080064080但是vfk的这种树分块方式。。。。。。感觉[B,3B]的话把应...

    52014年11月29日2,822莫队算法,最近公共祖先
  • 【bzoj3757】苹果树

    【bzoj3757】苹果树

    Description神犇家门口种了一棵苹果树。苹果树作为一棵树,当然是呈树状结构,每根树枝连接两个苹果,每个苹果都可以沿着一条由树枝构成的路径连到树根,而且这样的路径只存在一条。由于这棵苹果树是神犇种的,所以苹果都发生了变异,变成了各种各样的颜色。我们用一个到n之间的正整数来表示一种颜色。树上一共有n个苹果。每个苹果都被编了号码,号码为一个1到n之间的正整数。我们用0代表树根。只会有一个苹果直接根。有许许多多的...

    02014年11月28日2,704莫队算法,最近公共祖先
  • 【bzoj3781】小B的询问

    【bzoj3781】小B的询问

    Description小B有一个序列,包含N个1~K之间的整数。他一共有M个询问,每个询问给定一个区间[L..R],求Sigma(c(i)^2)的值,其中i的值从1到K,其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。Input第一行,三个整数N、M、K。第二行,N个整数,表示小B的序列。接下来的M行,每行两个整数L、R。OutputM行,每行一个整数,其中第i行的整数表示第i个询问的答案。SampleInput64313211314263556S...

    12014年11月27日1,789莫队算法
  • 【bzoj2002】[Hnoi2010]Bounce 弹飞绵羊

    【bzoj2002】[Hnoi2010]Bounce 弹飞绵羊

    Description某天,Lostmonkey发明了一种超级弹力装置,为了在他的绵羊朋友面前显摆,他邀请小绵羊一起玩个游戏。游戏一开始,Lostmonkey在地上沿着一条直线摆上n个装置,每个装置设定初始弹力系数ki,当绵羊达到第i个装置时,它会往后弹ki步,达到第i+ki个装置,若不存在第i+ki个装置,则绵羊被弹飞。绵羊想知道当它从第i个装置起步时,被弹几次后会被弹飞。为了使得游戏更有趣,Lostmonkey可以修改某个弹力装置的弹力系数,任...

    112014年7月30日3,302分块,link cut tree
  • 【bzoj2141】排队

    【bzoj2141】排队

    Description排排坐,吃果果,生果甜嗦嗦,大家笑呵呵。你一个,我一个,大的分给你,小的留给我,吃完果果唱支歌,大家乐和和。红星幼儿园的小朋友们排起了长长地队伍,准备吃果果。不过因为小朋友们的身高有所区别,排成的队伍高低错乱,极不美观。设第i个小朋友的身高为hi,我们定义一个序列的杂乱程度为:满足ihj的(i,j)数量。幼儿园阿姨每次会选出两个小朋友,交换他们的位置,请你帮忙计算出每次交换后,序列的杂乱程度。为方...

    42014年7月26日1,978分块
  • 【czy系列赛】czy的后宫3

    【czy系列赛】czy的后宫3

    czy的后宫3【题目描述】上次czy在机房妥善安排了他的后宫之后,他发现可以将他的妹子分为c种,他经常会考虑这样一个问题:在[l,r]的妹子中间,能挑选出多少不同类型的妹子呢?注意:由于czy非常丧尸,所以他要求在所挑选的妹子类型在[l,r]中出现次数为正偶数,你懂得。问题简述:n个数,m次询问,每次问[l,r]区间有多少个数恰好出现正偶数次【输入格式】第一行3个整数,表示n,c,m第二行n个数,每个数Ai在[1,c]之间,表示一个Ai类型...

    42014年7月19日2,027树状数组,离线处理,莫队算法
  • 【bzoj2821】作诗(Poetize)

    【bzoj2821】作诗(Poetize)

    Description神犇SJY虐完HEOI之后给傻×LYD出了一题:SHY是T国的公主,平时的一大爱好是作诗。由于时间紧迫,SHY作完诗之后还要虐OI,于是SHY找来一篇长度为N的文章,阅读M次,每次只阅读其中连续的一段[l,r],从这一段中选出一些汉字构成诗。因为SHY喜欢对偶,所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认为选出的汉字的种类数(两个一样的汉字称为同一种)越多越好...

    62014年7月19日2,287分块
1 / 2 1 2 下一页 »