非常好的线段树题。。。。此题必定会火。。。。。
Mex
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 955 Accepted Submission(s): 320
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.
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.
0 1 3
5
1 0 2 0 10
24
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.
#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 )