WC2013糖果公园

2014年11月29日4,6415

Description

Input

Output

Sample Input

Sample Output

84
131
27
84

HINT


题解

30分暴力。。。模拟即可

第4-5个测试点由于m较小,且在链上,所以可以用前缀和水过。。。

对于每个询问统计每种糖果的答案贡献

满分做法带修改树上莫队。。。

参见vfk的博客

http://vfleaking.blog.163.com/blog/#m=0&t=1&c=fks_084070093085082071086081080095085081085075084081080064080

但是vfk的这种树分块方式。。。

。。。感觉[B,3B]的话把应该把B设小点,但是这样的话链上就会。。。

不过这些都无所谓啦。。。

30

50

100

 

  • SkyDec2014年11月28日 下午5:47 回复

    这题要注意常数,不然会像我一样疯狂地爆OJ

    #1  
    • hzwer2014年11月28日 下午7:01 回复
      admin

      嘿嘿嘿我有数据

      #11
  • 涨红2016年1月8日 下午1:22 回复

    黄学长 请问能不能证明一下时间复杂度
    感觉加上一维时间每次修改可以到O(n)
    不太靠谱。。

    #2  
    • hzwer2016年1月8日 下午9:24 回复
      admin

      vfk的博客里有,n^(5/3)的复杂度,类似一般莫队的分析

      #21
      • 逗比2016年1月8日 下午11:37 回复

        吃个饭就懂了……

        #22