BZOJ 洛谷 删掉的数即三个区间数的并,想到bitset;查多个区间的数,想到莫队。 考虑bitset的每一位如何对应每个数的不同出现次数。只要离散化后不去重,每次记录time就可以了。 但是如果对所有询问开一个bitset...
[Luogu 4688] [Ynoi2016]掉进兔子洞 (莫队+bitset) 题面 一个长为 n 的序列 a。有 m 个询问,每次询问三个区间,把三个区间中同时出现的数一个一个删掉,问最后三个区间剩下的数的个数和,询问独立。注意这里删掉...
题目链接 luogu P4688 [Ynoi2016]掉进兔子洞 题解 莫队维护bitset区间交个数 代码 // luogu-judger-enable-o2 #include<cmath> #include<bitset> #include<cstdio> #include<cstring> #i...
题目大意:给定一个$n(n\leqslant10^5)$序列,$m(m\leqslant10^5)$个询问,每个询问给出$l_1,r_1,l_2,r_2,l_3,r_3$。令$s$为该三个区间的交集的大小,则输出$|[l_1,r_1]|+|[l_2,r_2]|+|[l_3,r_3]|−3|s|$ 题...
题面传送门:https://www.luogu.org/problemnew/show/P4688 (温馨提示,请直接翻至题目描述部分) 1e5的数据范围,以及对区间每个权值出现次数取min此类主席树才能解决的操作会让我们想到莫队; 三个区间取交集...
题意 题目链接 一个长为 n 的序列 a。 有 m 个询问,每次询问三个区间,把三个区间中同时出现的数一个一个删掉,问最后三个区间剩下的数的个数和,询问独立。 注意这里删掉指的是一个一个删,不是把等于这个值的...
题目链接:洛谷 我们知道要求的是\([l_1,r_1],[l_2,r_2],[l_3,r_3]\)的可重集取交的大小,肯定是要用bitset的,那怎么做可重集呢? 那就是要稍微动点手脚,首先在离散化的时候,将\(a_x\)设为\(\leq a_x\)的数的...