306119: CF1148H. Holy Diver
Memory Limit:1024 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Holy Diver
题意翻译
给定一个最初为空的数组,需要支持以下操作: - 给定 $a,l,r,k$,在数组末尾插入 $a$,然后查询有多少数对 $(i,j)$($l\leq i\leq j\leq r$),满足 $\mathrm{mex}(\{a_i,a_{i+1},a_{i+2},\ldots,a_j\})=k$。 强制在线。 $\mathrm{mex}(S)$ 表示集合 $S$ 中最小的未出现的**自然数**。题目描述
You are given an array which is initially empty. You need to perform $ n $ operations of the given format: - " $ a $ $ l $ $ r $ $ k $ ": append $ a $ to the end of the array. After that count the number of integer pairs $ x, y $ such that $ l \leq x \leq y \leq r $ and $ \operatorname{mex}(a_{x}, a_{x+1}, \ldots, a_{y}) = k $ . The elements of the array are numerated from $ 1 $ in the order they are added to the array. To make this problem more tricky we don't say your real parameters of the queries. Instead your are given $ a' $ , $ l' $ , $ r' $ , $ k' $ . To get $ a $ , $ l $ , $ r $ , $ k $ on the $ i $ -th operation you need to perform the following: - $ a := (a' + lans) \bmod(n + 1) $ , - $ l := (l' + lans) \bmod{i} + 1 $ , - $ r := (r' + lans) \bmod{i} + 1 $ , - if $ l > r $ swap $ l $ and $ r $ , - $ k := (k' + lans) \bmod(n + 1) $ , where $ lans $ is the answer to the previous operation, initially $ lans $ is equal to zero. $ i $ is the id of the operation, operations are numbered from $ 1 $ .The $ \operatorname{mex}(S) $ , where $ S $ is a multiset of non-negative integers, is the smallest non-negative integer which does not appear in the set. For example, $ \operatorname{mex}(\{2, 2, 3\}) = 0 $ and $ \operatorname{mex} (\{0, 1, 4, 1, 6\}) = 2 $ .输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the length of the array. The next $ n $ lines contain the description of queries. Each of them $ n $ lines contains four non-negative integers $ a' $ , $ l' $ , $ r' $ , $ k' $ ( $ 0, \leq a', l', r', k' \leq 10^9 $ ), describing one operation.
输出格式
For each query print a single integer — the answer to this query.
输入输出样例
输入样例 #1
5
0 0 0 1
0 1 0 5
5 2 1 0
5 2 1 0
2 4 3 3
输出样例 #1
1
1
2
6
3
输入样例 #2
5
2 0 0 2
2 0 1 1
0 0 2 0
3 2 2 0
0 2 3 0
输出样例 #2
0
0
3
0
0