Mex（线段树的巧妙应用）

题目要求求某段区间第一个没有出现的数（0,1,2,3.。。。），对于所有的区间，我们把这样的数加起来最后得到一个结果。

首先，我们要求出这样的数，然后还得列举出所有的区间，复杂度太大了。

换种思路，我们定住L，是不是一次性能求出所有的R所得出的结果，这就用到线段树的性质了，因为在移动L的过程中，移一步只变化一个数，那么就可以用线段树进行维护。

首先求出[1,R] 以1为左端的所有区间的情况，记录每个点也就是1到那个点的这段区间值sum[i]，以这个值建一颗树，那么在L向前移动的时候，每次丢掉一个数a[i-1]，因为少了这一个数，肯定后面有部分区间是变化的，有部分是不变化的，从这点开始向后找第一个与a[i-1]值相等的数的位置p，那么这个位置后面的sum肯定不会变化，因为丢掉的数又补上了。

那么就可以只考虑，从i位置到p这段里面的sum，如果原先的sum本来就比a[i-1]小，那说明a[i-1]的减少不影响它的值，所以不用改变，而所有大于a[i-1]的值将都变为a[i-1],这样更新一下，求和就可以了。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 #include<map>

 using namespace std;

 //#pragma comment(linker, "/STACK:1024000000,1024000000")

 #define N 200010

 #define LL __int64

 #define INF 0xfffffff

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 vector<int>po[N];

 map<int,int>f;

 LL s[N<<];

 int tm[N<<];

 LL lz[N<<];

 int sum[N];

 int p[N],a[N];

 bool vis[N];

 void up(int w)

 {

     s[w] = s[w<<]+s[w<<|];

     tm[w] = max(tm[w<<],tm[w<<|]);

     //cout<<tm[w]<<" "<<w<<endl;

 }

 void down(int w,int m)

 {

     if(lz[w]!=-)

     {

         tm[w<<] = tm[w<<|] = lz[w];

         lz[w<<] = lz[w<<|] = lz[w];

         s[w<<] = lz[w]*(m-m/);

         s[w<<|] = lz[w]*(m/);

         lz[w] = -;

         //cout<<lz[w]<<" <"<<w<<endl;

     }

 }

 void build(int l,int r,int w)

 {

     if(l==r)

     {

         s[w] = sum[l];

         tm[w] = sum[l];

         return ;

     }

     int m = (l+r)>>;

     build(l,m,w<<);

     build(m+,r,w<<|);

     up(w);

 }

 void update(int a,int b,int d,int l,int r,int w)

 {

     if(a<=l&&b>=r)

     {

         s[w] = (LL)d*(r-l+);

         tm[w] = d;

         lz[w] = d;

         //cout<<l<<", "<<r<<" "<<tm[w]<<" "<<d<<endl;

         return ;

     }

     int m = (l+r)>>;

     down(w,r-l+);

     if(a<=m) update(a,b,d,l,m,w<<);

     if(b>m) update(a,b,d,m+,r,w<<|);

     up(w);

 }

 int find(int k,int l,int r,int w)

 {

     // cout<<s[w]<<" "<<tm[w]<<" "<<l<<" "<<r<<" "<<w<<endl;

     if(l==r)

     {

         //cout<<l<<" "<<tm[w]<<endl;

         return l;

     }

     int m = (l+r)>>;

     down(w,r-l+);

     if(tm[w<<]>k)

         return find(k,l,m,w<<);

     else

         return find(k,m+,r,w<<|);

 }

 LL query(int a,int b,int l,int r,int w)

 {

     if(a<=l&&b>=r)

     {

         return s[w];

     }

     int m = (l+r)>>;

     LL res = ;

     down(w,r-l+);

     if(a<=m)

         res+=query(a,b,l,m,w<<);

     if(b>m)

         res+=query(a,b,m+,r,w<<|);

     return res;

 }

 int main()

 {

     int n,i;

     while(scanf("%d",&n)&&n)

     {

         f.clear();

         memset(p,,sizeof(p));

         memset(vis,,sizeof(vis));

         memset(lz,-,sizeof(lz));

         for(i = ; i <= n ; i++)

             po[i].clear();

         int g = ;

         for(i = ; i <= n; i++)

         {

             scanf("%d",&a[i]);

             if(!f[a[i]]) f[a[i]] = ++g;

             po[f[a[i]]].push_back(i);

         }

         int o = ;

         for(i = ; i <= n ; i++)

         {

             if(a[i]<N)

                 vis[a[i]] = ;

             if(a[i]<sum[i-])

                 sum[i] = sum[i-];

             else

             {

                 while(vis[o])

                     o++;

                 sum[i] = o;

             }

         }

         LL ans=;

         build(,n,);

         ans+=s[];

         //cout<<ans<<endl;

         p[f[a[]]] = ;

         for(i = ; i <= n ; i++)

         {

             int k;

             int mk = f[a[i-]];

             if(p[mk]<po[mk].size())

             {

                 k = po[mk][p[mk]]-;

                 //cout<<k<<endl;

                 //p[mk]++;

             }

             else k = n;

             update(,i-,,,n,);

             int fk;

             if(tm[]>a[i-])

             {

                 fk = find(a[i-],,n,);

                     update(fk,k,a[i-],,n,);

             }

             ans+=query(i,n,,n,);

            // cout<<ans<<endl;

            //cout<<ans<<" "<<fk<<" "<<k<<" "<<a[i-1]<<endl;

             //cout<<i<<endl;

             //if(a[i]!=a[i-1])

             p[f[a[i]]]++;

         }

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

Mex（线段树的巧妙应用）

最新文章

热门文章