主题

主题

 
   

Paint The Wall

原题:http://acm.hdu.edu.cn/showproblem.php?pid=4391

Problem Description

As a amateur artist, Xenocide loves painting the wall. The wall can be considered as a line consisting of n nodes. Each node has its own color.

Xenocide spends all day in front of the wall. Sometimes, he paints some consecutive nodes so that these nodes have the same color. When he feels tired, he focuses on a particular color and counts the number of nodes that have this color within a given interval.

Now Xenocide is tired of counting, so he turns to you for help.

Input

The input consists of several test cases.

The first line of each test case contains two integer n, m(1<=n, m<=100000) indicating the length of the wall and the number of queries.

The following line contains N integers which describe the original color of every position.

Then m lines follow. Each line contains 4 non-negative integers a, l, r, z(1<=a<=2, 0<=l<=r<n ,0<=z<231).

a = 1 indicates that Xenocide paints nodes between l and r and the resulting color is z.

a = 2 indicates that Xenocide wants to know how many nodes between l and r have the color z.

Output

Print the corresponding answer for each queries.

Sample Input

5 5

1 2 3 4 0

2 1 3 3

1 1 3 1

2 1 3 3

2 0 3 1

2 3 4 1

Sample Output

1

0

4

1


题目大意:

给出一个序列。支持两个操作:

  1. 将一段区间[l..r]染色为z

  2. 查询区间[l..r]中有多少格子颜色是z


个人解法:

很多人用线段树水掉了?

然后本蒟用的是分块。而且——还不是那么容易……

吐槽:首先一眼看过去,不是分块+桶的煞笔题么?

维护一个标记,表示这一段是否被完全覆盖。

写一个操作,下传标记,并重构块:

把块里面的A全部赋值为标记,维护桶。(重构块的操作)

  1. 对于查询:

    首先对于整块的,可以直接查桶,或者查标记。

    零散就先把标记下传下去,然后直接扫描。

  2. 对于修改:

    整块的就打标记,零散的就把标记传下去,再一个一个改就可以了。

写了一下子,发现:


32MB=4*8MB=8e6*int

桶的大小至少是O(2e5)不能小。也就是说,我们快的个数最多是O(40)。块的大小至少是O(2500),时间复杂度至少是O(1e5*2500)=O(2.5e8)。

随便多一个常数就挂了,我感觉卡不过。


此题MLE的人数与TLE的人数近似,我想不乏有人先写了一个分块+桶,然后发现MLE,一看空间限制,决定调块的大小,然后调到TLE……


于是换一个思路。

如果要维护桶,那就必须要O(2e5)的桶。因此我们应该尝试不需要桶的方法。


第一个想到的是平衡树。由于要统计出现的次数,所以用map。

这也是正解所述的分块Hash的方法?(大雾)

也就是说,一个块里面放一个map来代替桶。

这样每个操作都要带logn了。

所以总的时间复杂度是O(msqrt(n)logn)的。

但是它带一个logn。我开始以为可能还是卡不过,然后否决了它……


后来想到,为什么一定要一棵树呢?

我们直接维护一个升序的数组。

最坏情况下,每个块都要去二分查找,然后扫描剩余块。查询的复杂度是O(Threshold+Num*logn)

重构的时候,是有tag才重构。然后如果有tag就把所有的清空。然后剩下tag的那一个就好了。

修改的复杂度是O(Threshold+Num)。

注意修改是把一堆数字删去,改成一个数字。不用重新排序。


最乐观的是,直接维护数组是可以调整块的大小,降低复杂度的。然而上面那一个map的方法不能调整块的大小。再者,直接维护数组也比维护map少了部分的logn(修改是可以利用一个桶做到不用logn的)

但是常数略大。快赶上了一个logn(大雾)。于是调整块大小的时候,令Threshold=ceil(0.1*n*log2(n))。反正比一些写map的人还是快了一些。


代码如下:

https://code.csdn.net/snippets/2299885

 
 
评论
 
 
热度(1)