• 程序设计实习实验班2017推荐习题

    程序设计实习实验班2017推荐习题

    区间众数问题这题写莫队是最容易的,可以对于每种出现次数的数字维护一个堆,用于删除时维护答案[crayon-65f9409a67090016264955/]「BZOJ3659」WhichDreamedIt 神奇钥匙求以1为起点的欧拉回路的个数乘1的度数BESTtheorem[crayon-65f9409a6709f305483604/]「bzoj4031」[HEOI2015]小Z的房间矩阵树定理推荐阅读算法合集之《欧几里得算法的应用》[crayon-65f9409a670a7442488978/]POJ2373DividingthePath用dp(i)...

  • 「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日17,686分块,莫队算法
  • 「BZOJ3289」Mato的文件管理

    「BZOJ3289」Mato的文件管理

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

    42014年12月3日6,740树状数组,莫队算法
  • 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日8,733莫队算法,最近公共祖先
  • 「BZOJ3757」苹果树

    「BZOJ3757」苹果树

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

    02014年11月28日9,831莫队算法,最近公共祖先
  • 「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日5,567莫队算法
  • 「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日9,479树状数组,离线处理,莫队算法
  • 「BZOJ2038」[2009国家集训队] 小Z的袜子(hose)

    「BZOJ2038」[2009国家集训队] 小Z的袜子(hose)

    Description作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……具体来说,小Z把这N只袜子从1到N编号,然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。你的任务便是告诉小Z,他有多大的概率抽到两只颜色...

    212014年4月26日30,208莫队算法