WC2013糖果公园

2014年11月29日8,9705

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

 

avatar
2 Comment threads
3 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
逗比hzwerSkyDec Recent comment authors
  Subscribe  
提醒
涨红

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

SkyDec

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