定睛一看,这题就是一道数据结构题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意简述
给定一个矩阵,要求你资瓷一种修改和一种查询操作:
1. 将矩阵 (x1,y1,x2,y2)(x_1,y_1,x_2,y_2)(x1 ,y1 ,x2 ,y2 ) 全部作标记。
2. 询问 (x,y)(x,y)(x,y) 被作了几次标记,最后一次标记是什么时候做的。
我们自然想到了数组套线段树。对于每一行,有一颗线段树对应它的每一列。每一个节点都要记录被标记的次数和最后被标记的时间。修改时,我们为对应行的线段树进行区间标记。查询时,我们返回对应行列的节点编号,得到这个点的被标记的次数和最后被标记的时间。经过一波计算,我们发现单次修改的时间复杂度为 O(nlogn)O(n\log n)O(nlogn) ,单次查询的时间复杂度为 O(logn)O(\log n)O(logn)。若 xxx 与 yyy 同数量级(题目未标明),则总时间复杂度为 O(xnlogn)O(xn\log n)O(xnlogn),相比一般模拟的 O(xn2)O(xn^2)O(xn2)
优。当然这题数据过水,你怎么写都能AC。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
AC Code~ 不要只看这里啊。
课后作业:试着使用线段树套线段树(或树状数组)(可以参考P3380 【模板】树套树)进一步优化时间复杂度,令单次修改的时间复杂度为 O(log2n)O(\log^2 n)O(log2n) ,单次查询的时间复杂度为 O(log2n)O(\log^2 n)O(log2n),总时间复杂度为 O(xlog2n)O(x\log^2 n)O(xlog2n)。哈哈我真是无聊@_@