正文
HDOJ 4747 Mex
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
非常好的线段树题。。。。此题必定会火。。。。。
Mex
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 955 Accepted Submission(s): 320
Problem Description
Mex is a function on a set of integers, which is universally used for impartial game theorem. For a non-negative integer set S, mex(S) is defined as the least non-negative integer which is not appeared in S. Now our problem is about mex function on a sequence.
Consider a sequence of non-negative integers {ai}, we define mex(L,R) as the least non-negative integer which is not appeared in the continuous subsequence from aL to aR, inclusive. Now we want to calculate the sum of mex(L,R) for all 1 <= L <= R <= n.
Input
The input contains at most 20 test cases.
For each test case, the first line contains one integer n, denoting the length of sequence.
The next line contains n non-integers separated by space, denoting the sequence.
(1 <= n <= 200000, 0 <= ai <= 10^9)
The input ends with n = 0.
For each test case, the first line contains one integer n, denoting the length of sequence.
The next line contains n non-integers separated by space, denoting the sequence.
(1 <= n <= 200000, 0 <= ai <= 10^9)
The input ends with n = 0.
Output
For each test case, output one line containing a integer denoting the answer.
Sample Input
3
0 1 3
5
1 0 2 0 10
0 1 3
5
1 0 2 0 10
Sample Output
5
24
24
Hint
For the first test case:mex(1,1)=1, mex(1,2)=2, mex(1,3)=2, mex(2,2)=0, mex(2,3)=0,mex(3,3)=0. 1 + 2 + 2 + 0 +0 +0 = 5.
Source
2013 ACM/ICPC Asia Regional Hangzhou Online
Recommend
liuyiding
#include <iostream> #include <cstdio> #include <cstring> #include <map> #define lson l,m,rt<<1 using namespace std; const int maxn=200005; typedef long long int LL; int a[maxn],mex[maxn],next[maxn],mx[maxn<<2],sig[maxn<<2],cnt; void pushUP(int rt) void pushDOWN(int rt,int len) void build(int l,int r,int rt) LL query(int L,int R,int l,int r,int rt) int getID(int L,int R,int v,int l,int r,int rt) void update(int L,int R,int c,int l,int r,int rt) int main() |
* This source code was highlighted by YcdoiT. ( style: Codeblocks )