前言(废话):CSP-S模拟赛,赛场上想了个解法没有证明,直接7分,还没暴力分高,感觉是道简单题,但不会。应该是学多了糊了
题目描述:
考虑一个n*n的矩阵A,所有初始元素全为0。
执行q次如下操作:给定四个整数r,c,l,s,对每个满足x∈[r,r+l],y∈[c,x-r+c]的元素(x,y),权值增加s。也就是,给一个左上顶点为(r,c)、直角边长为l的下三角区域加上s。
输出最终矩阵的元素异或和。
数据范围:n≤10³,q≤3*10⁵
样例输入:
10 4
1 1 10 1
5 5 4 4
1 9 4 3
3 3 5 2
样例输出:0
结尾的废话(本人思考历程):首先,这个鬼题暴力能偷57分令人很不爽。
首先,排除暴力,直接炸。其次,该题题面简单,于是没有考虑使用复杂数据结构维护,于是考虑思维题。觉得可以分开维护每个下三角的异或,最后合并处理,事实证明会写挂。最后实在想不到,直接放弃去弄t2t3了。