题目链接

传送门

写在前面


如果你是死宅 或者你不是死宅但是你很喜欢<美好的每一天——不连续的存在>这款galgame 请继续阅读并忽略<写在前面>这部分内容
如果你不是死宅 并且你还没有了解题意 请直接跳到Description这一部分的倒数几行看一句话题意
如果你不是死宅 并且你已经了解了题意 请直接移步题解部分
不听我这部分的话的人 后果自负2333

Description

我(或者是在读这篇文字的你)不属于这个世界
这是世界的界限
6.41
世界的意义必定存在于世界之外
世界中的一切事物如其所存在般而存在,如其所发生般而发生
世界之中不存在价值
--《逻辑哲学论》
我们的情人,不过是随便借个名字,用幻想吹出来的肥皂泡
把信拿去吧,你可以使假戏成真
我本来是无病呻吟,漫无目的的吐露爱情---现在这些漂泊不定的鸟儿有地方栖息了,你可以从信里看出来
拿去吧---由于不是出自真心,话就说得格外动听,拿去吧,就这么办吧...

果然……好女人要有的是,烟、楼顶……还有轻飘飘的衣服呀……
某一天,水上由岐看见天上掉下了个布制玩偶
为了被天空接受而投掷出的她的布偶,不知在天空飞舞了多少次,已经遍体鳞伤
"被天空接受"那是为了寻找不知何时开始在这个城市流传的"回归天空之路"的行为

为了被天空接受而被扔出去的木偶,在空中飞舞并最终坠落
那是为了将其本身即为世界的少女送予天空的少女的行为

横跨银河,被称作Vega与Altair,或是织女星与牛郎星的两颗星星,再加上北十字星之顶的天鹅座构成了夏之大三角
它被称作譬如三位一体的神圣的图形
只有神圣的图形在天空闪耀之时,世界才与天空相遇

我想试一试,第一次,也是最后一次的恶作剧

那是...什么?
什么事也没有哦,只是,间宫君他自己主动跳下去了而已哦~
怎么回事?
什么事也没有哦,只是,间宫君他自己主动跳下去了而已哦~
但是我看到了,是那个杀死了大家吗?
什么事也没有哦,只是,间宫君他自己主动跳下去了而已哦~
不,那个东西,什么都没有做,只是...
什么事也没有哦,只是,间宫君他自己主动跳下去了而已哦~
只是...怎么回事...
什么事也没有哦,只是,间宫君他自己主动跳下去了而已哦~
我确实听到了头盖骨破碎的声音
但是那个,并非是外面的世界
而是总自己的里面传来的

水上同学...我偶尔会思考这种事情...
世界的极限到底在哪里呢...
世界的...世界的尽头的更尽头...
要是能有那种地方...
要是假如我能够站在那个地方的话...我还是能跟平时一样看着那个尽头的风景吗?我有这种想法....
我理所当然的想着这种事...然后决定似乎是有些奇怪啊
因为那里是世界的尽头哦
是世界的极限哦
如果我能够看到那个的话...世界的极限...是否就等同于我的极限呢?
因为,从那里看到的世界...我所看见的...不就是我的世界吗?
世界的极限...就会变成我的极限吧~
世界就是我看到的摸到的,并且感受到的东西
那样的话,世界到底是什么呢
世界和我到底有什么不同呢...我有这种想法
有吗?
世界和我的差别
是一样的
但是,或许其他人也有相同的感觉...
就连你,或许也认为世界就是你自己吧
并且,我觉得那个大概是正确的...
虽然我不太清楚...大概是你也站在世界的尽头,跟我一样在看着它吧
所以,你也和世界一样
但是啊,那样果然很奇怪啊...
如果世界就是我的话...为什么我会看不到你看到的世界呢?
明明我的世界里有你存在...却看不到你看到的世界
我从来没有看到过你看到的世界
那个,简直就像是两者不会交集的平行宇宙一样...
即使有现象暗示着那个东西存在...却是绝对的无法触碰...
我...看不到你所在的世界...
但是...
那个也是真的是真的吗?
我真的没有看到过你的世界吗...
既然所有的人都平等的拥有她们自己的世界的话
那么为什么世界会变成一个呢?
为什么那么多的世界会存在于这里呢?
世界变成一个的理由
...我偶尔会思考这种事情
所以...我才能够喜欢上你
您正在打galgame,然后突然发现您今天太颓了,于是想写个数据结构题练练手:
一个长为 n 的序列 a。
有 m 个询问,每次询问三个区间,把三个区间中同时出现的数一个一个删掉,问最后三个区间剩下的数的个数和,询问独立。
注意这里删掉指的是一个一个删,不是把等于这个值的数直接删完,
比如三个区间是 [1,2,2,3,3,3,3] , [1,2,2,3,3,3,3] 与 [1,1,2,3,3],就一起扔掉了 1 个 1,1 个 2,2 个 3。

Input

第一行两个数表示 n , m。
第二行 n个数表示 a[i]。
之后 m 行,每行 6 个数 l1 , r1 , l2, r2 , l3 , r3 表示这三个区间。

Output

对于每个询问,输出一个数表示答案。

Sample Input

5 2
1 2 2 3 3
1 2 2 3 3 4
1 5 1 5 1 5

Sample Output

3
0

HINT

n , m <= 100000 , 1 <= a[i] <= 1000000000

Source

By nzhtl1477

想说的话

一直想推推这个gal
不过碍于最近忙着补番加上追剧所以没有时间$QAQ$

题解

这题绝壁神题
这个题上来我们可以看看问的是什么
$\sum _ {i=1}^{3} (r_i-l_i+1) - 3 * \sum _ {j=1} ^ {Max}min(cnt_1[j],cnt_2[j],cnt_3[j])$
然后发现前面那部分非常好办
考虑后面那部分
看到$a_i$的范围我先想到了把这个数列离散化一下
然后我考虑到的是用一个操作把出现的最少次数搞出来
如果这要是一个$0-1$串的话这不就是一个与操作么
所以说我用bitset来维护这个事情
求一段区间内各数字出现的次数是莫队算法的经典问题。对于本题,我们把一个询问的三个区间拆开解决,最后再合并起来。每次合并都是O(n)的复杂度,不优秀,这里我们使用bitset优化,记录cnt。注意到数字可能重复出现,而bitset只能记录0和1,因此在离散化前不能有去重操作。例如对样例数据:1 2 2 3 3 ,离散化后应为:1 2 2 4 4,在bitset中用第2位表示出现的第1个2,第3位表示第二个2,以此类推。
但这样会MLE,于是我们强行把询问分组,每25000个为一组,分批求解,解决了空间不足的问题。
但是这样的话如果常数大点可能会TLE 我常数小不关我事这样怎么办呢 我们可以考虑手写一个bitset嘛对不对
我是不会写 幸好我常数小

代码