首页 > 代码库 > [HDU 4747] Mex （线段树）
[HDU 4747] Mex （线段树）
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4747
这道题是我去年刚入校队的时候参加网赛的题目。
一年过去了，我依然还是不会做。。
这是我难题计划的开始吧。。
竟然还敲挫了，自己真是弱。
题意：
给你一个数列a，定义Mex[L,R]为a[L,R]中没有出现过的最小的自然数。求1<=l<=r<=n的所有Mex[l,r]之和。
解法我也是看了解题报告才知道的。
请参看cxlove大神的博文：http://blog.csdn.net/acm_cxlove/article/details/11749383
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <set> 5 using namespace std; 6 7 typedef long long LL; 8 typedef pair<int,int> PII; 9 const int MAX_N = 2e5+100;10 LL delta[MAX_N<<2],sum[MAX_N<<2],maxn[MAX_N<<2];11 PII b[MAX_N];12 int a[MAX_N],next[MAX_N],n;13 set<int> Set;14 15 void push_down(int idx,int l,int r){16 if( delta[idx]!=-1 ){17 int m = l+r>>1;18 sum[idx<<1] = (m-l+1)*delta[idx];19 sum[idx<<1|1] = (r-m)*delta[idx];20 delta[idx<<1] = delta[idx<<1|1] = maxn[idx<<1] = maxn[idx<<1|1] = delta[idx];21 delta[idx] = -1;22 }23 }24 25 void push_up(int idx){26 sum[idx] = sum[idx<<1]+sum[idx<<1|1];27 maxn[idx] = max(maxn[idx<<1],maxn[idx<<1|1]);28 }29 30 void update(int L,int R,LL x,int idx,int l,int r){31 if( R<l||L>r ) return;32 if( L<=l&&R>=r ) {33 sum[idx] = (r-l+1)*x;34 maxn[idx] = delta[idx] = x;35 return;36 }37 push_down(idx,l,r);38 int m = l+r>>1;39 if( L<=m ) update(L,R,x,idx<<1,l,m);40 if( R>m ) update(L,R,x,idx<<1|1,m+1,r);41 push_up(idx);42 }43 44 int query(LL x,int idx,int l,int r){45 if( maxn[idx]<=x ) return r+1;46 if( l==r ) return l;47 push_down(idx,l,r);48 int m = l+r>>1;49 if( maxn[idx<<1]>x ) return query(x,idx<<1,l,m);50 else return query(x,idx<<1|1,m+1,r);51 }52 53 LL querySum(int L,int R,int idx,int l,int r){54 if( L<=l&&R>=r ) return sum[idx];55 push_down(idx,l,r);56 int m = l+r >> 1 ;57 LL res = 0;58 if( L<=m ) res = querySum(L,R,idx<<1,l,m);59 if( R>m ) res += querySum(L,R,idx<<1|1,m+1,r);60 return res;61 }62 63 int main(){64 while(scanf("%d",&n)!=EOF&&n){65 memset(sum,0,sizeof(sum));66 memset(delta,-1,sizeof(delta));67 Set.clear();68 for(int i=1;i<=n;i++){69 scanf("%d",&a[i]);70 b[i] = PII(a[i],i);71 next[i] = n+1;72 }73 sort(b+1,b+1+n);74 b[n+1].first = b[n].first; b[n+1].second = n+1;75 for(int i=1;i<=n;i++){76 if( b[i].first==b[i+1].first ) next[b[i].second] = b[i+1].second;77 }78 int mmex = 0;79 for(int i=1;i<=n;i++){80 Set.insert(a[i]);81 while( Set.find(mmex)!=Set.end() ) mmex++;82 update(i,i,mmex,1,1,n);83 }84 LL ans = sum[1];85 for (int l = 1; l <= n; l++) {86 update(l,l,0,1,1,n);87 int p = query(a[l],1,1,n);88 p = max(l+1,p);89 int q = next[l] - 1;90 update(p,q,a[l],1,1,n);91 ans += sum[1];92 }93 printf("%I64d\n", ans);94 }95 return 0;96 }
[HDU 4747] Mex （线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。