首页 > 代码库 > hdu 4747 Mex

hdu 4747 Mex

2024-07-16 21:29:21   219人阅读

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 }
View Code

 


联系
我们