首页 > 代码库 > hdu 4747 Mex
hdu 4747 Mex
http://acm.hdu.edu.cn/showproblem.php?pid=4747
题意:定义一个函数mex(i,j),mex(i,j)为从i到j之间没有出现的最小的非负整数,求所有的mex(i,j)的值的和。
我们可以知道mex(i,i+1)到mex(i,i+n)的值是递增的。可以先求从mex(1,1),mex(1,2)....mex(1,n)的值,然后通过以1开始的mex推出以2开始的mex的值,以此递推下去。
使用线段树维护,删除前面的数。删掉第一个数a[1]. 那么在下一个a[1]出现前的 大于a[1]的mex值都要变成a[1]。使用线段树维护区间的值修改和区间求和。
1 #include <cstdio> 2 #include <cstring> 3 #include <map> 4 #include <algorithm> 5 #define LL long long 6 #define maxn 200001 7 using namespace std; 8 9 LL max2(LL a,LL b) 10 { 11 return b>a?b:a; 12 } 13 14 struct node 15 { 16 int l,r; 17 int max1; 18 LL sum; 19 int flag; 20 } tree[maxn*4]; 21 int a[maxn]; 22 int n; 23 int mex[maxn]; 24 int next[maxn]; 25 26 void build(int i,int l,int r) 27 { 28 tree[i].l=l; 29 tree[i].r=r; 30 tree[i].flag=0; 31 if(l==r) 32 { 33 tree[i].max1=mex[l]; 34 tree[i].sum=mex[l]; 35 return ; 36 } 37 int mid=(l+r)>>1; 38 build(i<<1,l,mid); 39 build(i<<1|1,mid+1,r); 40 tree[i].max1=max2(tree[i<<1].max1,tree[i<<1|1].max1); 41 tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum; 42 } 43 44 45 void down(int i) 46 { 47 if(tree[i].l==tree[i].r) return ; 48 if(tree[i].flag) 49 { 50 tree[i<<1].sum=(LL)tree[i].max1*(tree[i<<1].r-tree[i<<1].l+1); 51 tree[i<<1].max1=tree[i].max1; 52 tree[i<<1].flag=1; 53 tree[i<<1|1].sum=(LL)tree[i].max1*(tree[i<<1|1].r-tree[i<<1|1].l+1); 54 tree[i<<1|1].max1=tree[i].max1; 55 tree[i<<1|1].flag=1; 56 tree[i].flag=0; 57 } 58 } 59 60 void update(int i,int l,int r,int key) 61 { 62 if(tree[i].l==l&&tree[i].r==r) 63 { 64 tree[i].sum=(LL)key*(tree[i].r-tree[i].l+1); 65 tree[i].max1=key; 66 tree[i].flag=1; 67 return; 68 } 69 down(i); 70 int mid=(tree[i].l+tree[i].r)>>1; 71 if(r<=mid) 72 { 73 update(i<<1,l,r,key); 74 } 75 else if(l>mid) 76 { 77 update(i<<1|1,l,r,key); 78 } 79 else 80 { 81 update(i<<1,l,mid,key); 82 update(i<<1|1,mid+1,r,key); 83 } 84 if(tree[i].l!=tree[i].r) 85 { 86 tree[i].max1=max2(tree[i<<1].max1,tree[i<<1|1].max1); 87 tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum; 88 } 89 } 90 91 int get_max(int i,int key) 92 { 93 if(tree[i].l==tree[i].r) 94 { 95 return tree[i].l; 96 } 97 down(i); 98 if(tree[i<<1].max1>key) 99 return get_max(i<<1,key);100 else return get_max(i<<1|1,key);101 }102 int main()103 {104 while(scanf("%d",&n)!=EOF)105 {106 if(n==0) break;107 for(int i=1; i<=n; i++)108 {109 scanf("%d",&a[i]);110 }111 map<int,int>q;112 int t1=0;113 for(int i=1; i<=n; i++)114 {115 q[a[i]]=1;116 while(q.find(t1)!=q.end()) t1++;117 mex[i]=t1;118 }119 q.clear();120 for(int i=n; i>=1; i--)121 {122 if(q.find(a[i])==q.end()) next[i]=n+1;123 else next[i]=q[a[i]];124 q[a[i]]=i;125 }126 build(1,1,n);127 LL ans=0;128 for(int i=1; i<=n; i++)129 {130 ans+=tree[1].sum;131 if(tree[1].max1>a[i])132 {133 int ll=get_max(1,a[i]);134 int rr=next[i];135 if(ll<rr)136 {137 update(1,ll,rr-1,a[i]);138 }139 }140 update(1,i,i,0);141 }142 printf("%I64d\n",ans);143 }144 return 0;145 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。