杭州赛区的这一题是个巨坑,虽然现场1A瞬秒,至今觉得不科学.
该题只有两个操作,一是在一个点加一个值,二是求一个菱形区域的和.这不是和二维树状数组的水题长得一摸一样嘛......至于如何把菱形变成平行于坐标轴的矩形,果断只要把地图转45度就可以了,然后稍微推一下坐标的变换公式.然后对于每一次第二个操作用容斥原理做四次求和.
ps:现场的C题为什么没解题报告?虽然C题现场没做出来,但经事后讨论,先用等差数列求和公式算出Q=k时的所有数的个数(包括重复的),因为Q最大为1000000,所以从1开始到1000000递推一遍打表,当然也要同时减去重复的个数.当Q=1时,没有重复的,所以答案为n-0,当Q=k时,减去的重复个数=每两个相邻的相同数字之间有(p-2)个数字的个数的和(2<=p<=k)那如何算相邻的相同数字之间有q个数字的个数呢?因为元素的个数最大到1000000,所以只要对于每个不同数字记录它上一次出现的位置,如果再次碰到相同的数字与上一次的位置之差为q+1,则相距为q的个数+1,同时更新该数字上一次出现的位置,所以只要把数列扫一遍就能知道所有相距为q的个数(1<=q<=n-2).总效率是O(n)的.