YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

时间限制:2000MS      内存限制:524288KB

难度:\(6.5\)

  • 题目描述

给定一个长度为 \(n\) 的正整数序列 \(\{a_i\}\),有 \(m\) 次操作。格式如下:

1 l r x 将区间 \([l,r]\) 中的所有数变为 \(x\)。

2 l r x 查询区间 \([l,r]\) 中数字 \(x\) 的出现次数。

  • 输入格式

第一行两个正整数 \(n,m\),表示序列长度和操作次数。

第二行 \(n\) 个正整数,第 \(i\) 个数为 \(a_i\),表示序列初始值。

接下来 \(m\) 行每行四个正整数,表示操作,含义如题目所示。

  • 输出格式

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

  • 样例 1 输入

  • 样例 1 输出

  • 数据规模与约定

对于 \(20\%\) 的数据,\(1 \leq n,m \leq 2000\) 。

对于 \(50\%\) 的数据,\(1 \leq n,m \leq 100000\) 。

对于另外 \(10\%\) 的数据,没有 \(1\) 操作。

对于 \(100\%\) 的数据,\(1 \leq n,m,a_i,x \leq 400000\),\(1 \leq l \leq r \leq n\),保证数据不是纯随机生成。

 

 

 


 

 

 

考场上看到区间推平一眼 ODT,然而底下数据保证不随机www

然后第二眼就是分块,\(n \leq 400000\) 这能过?

不管了,先打了www

然后脑补了一个分块,修改时中间打标记,端点暴力修改,查询暴力块内二分,是 \(O(n \sqrt n \log n)\) 的。

然后很神奇的过了???

某同学也写了一个分块,然而他只拿了 \(50pts\) wwwwww

神奇常数wwwwww最大点才1.29s比正解还快wwwwwwwwwwwwwwwww

然后被全询问 \([1,n]\) 卡掉了)

 

然后结束一看,正解就是 ODT)

由于 ODT 修改复杂度是对的,所以修改时可以用 ODT,查询时就不能了。

所以对每种颜色都开一个线段树(标记永久化比打 \(tag\) 快很多,特别是动态开点)维护这个颜色出现在哪些区间里,查询时直接在线段树里查就行了。

修改时用 ODT 遍历每个需要修改的区间,在各自的线段树上删去原区间后,加入新区间即可。

时间复杂度 \(O(m \log^2 n)\)。

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注