如果你下列数据始终输出14
input:
100 5
40 7 47 44 52 81 87 60 82 49 40 30 44 90 62 68 81 44 46 17 44 71 89 79 44 95 57 4 6 36 26 61 62 64 14 93 46 35 20 98 55 6 71 9 85 31 1 70 93 100 82 33 57 14 83 56 40 67 27 53 43 39 44 4 59 32 49 72 91 60 67 84 16 64 9 21 59 30 100 34 47 62 10 9 56 88 19 20 16 92 22 11 68 56 62 16 77 94 20 10
M 66 67 1
M 82 97 13
M 14 90 20
M 47 76 7
A 58 86 80
output:
13
那么你大概率在未完全覆盖的块中暴力更新时,对着排序数组直接更新了,看看下面这段代码,捋一捋。
a数组->排序数组
b数组->原始数组
#define ox of[x]
#define oy of[y]
#define f(x,y) for(register I i=x;i<=y;i++)
f(x,r[ox])b[i]+=v;
f(l[oy],y)b[i]+=v;
f(l[ox],r[ox])a[i]=b[i];
f(l[oy],r[oy])a[i]=b[i];
你应当先在b数组中更新对应元素,然后把b数组的块复制到排序数组a对应的块中,然后在a数组的块中再次进行排序。
也就是说,除了更新未完全覆盖的具体元素外,始终以块为操作单位。
这属于本人的粗心导致的错误,我认为不会有人错在这的
cccccorz