【模拟8.03】数颜色（vector//主席树）

才知道vector在插入值后是可以直接修改的...

那就很简单了

用vector的lowerbound这样的二分操作，提前储存每个颜色的位置

发现交换相对位置不变

#include<iostream>

#include<cstdio>

#include<string>

#include<algorithm>

#include<cmath>

#include<vector>

#include<map>

#include<set>

#include<cstring>

#define MAXN 310001

#define int long long

#define ps push_back

using namespace std;

int n,m;vector<int>v[MAXN];int a[MAXN];

int find(int l,int r,int x)

{

    return upper_bound(v[x].begin(),v[x].end(),r)-lower_bound(v[x].begin(),v[x].end(),l);

}

int kx(int l,int x)

{

    return lower_bound(v[x].begin(),v[x].end(),l)-v[x].begin();

}

signed main()

{

   scanf("%lld%lld",&n,&m);

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

   {

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

       v[a[i]].ps(i);

   }

   for(int i=1;i<=m;++i)

   {

       int orz;

       int l,r,x;

       scanf("%lld",&orz);

       if(orz==1)

       {

            scanf("%lld%lld%lld",&l,&r,&x);

            printf("%lld\n",find(l,r,x));

       }

       else

       {

            scanf("%lld",&l);

            if(a[l]==a[l+1])continue;

            int me=kx(l,a[l]);

            int me1=kx(l+1,a[l+1]);

            //printf("me=%lld\nme1=%lld\n",me,me1);

            //printf("v[%lld][%lld]=%lld\n",a[l+1],me1,v[a[l+1]][me1]);

            v[a[l]][me]=l+1;

            v[a[l+1]][me1]=l;

            swap(a[l],a[l+1]);

       }

   }

}

还有主席树做法（我怎么没想到.....）

ps：超时了，只是存板子（它竟然卡我....）

#include<iostream>

#include<cstdio>

#include<string>

#include<algorithm>

#include<cmath>

#include<vector>

#include<map>

#include<set>

#include<cstring>

#define MAXN 1000001

#define int long long

#define ps push_back

using namespace std;

struct node

{

  int ls,rs,val;

}T[20*MAXN];

int root[MAXN];int a[MAXN];

int tot=0;int n,m;

void insert(int &now,int l,int r,int x,int k,int last)

{

    now=++tot;

    T[now]=T[last];

    int mid=(l+r)>>1;

    if(l==r)

    {

         T[now].val+=k;

         return ;

    }

    if(x<=mid)insert(T[now].ls,l,mid,x,k,T[last].ls);

    else insert(T[now].rs,mid+1,r,x,k,T[last].rs);

}

int query(int x,int l,int r,int val)

{

    if(l==r){return T[x].val;}

    int mid=(l+r)>>1;

    if(val<=mid)return query(T[x].ls,l,mid,val);

    else return query(T[x].rs,mid+1,r,val);

}

int maxn=0;

signed main()

{

    scanf("%lld%lld",&n,&m);

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

    {

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

        maxn=max(maxn,a[i]);

    }

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

    {

        //root[i]=root[i-1];

        insert(root[i],1,maxn,a[i],1,root[i-1]);

    }

    for(int i=1;i<=m;++i)

    {

        int orz,l,r,x;

        scanf("%lld",&orz);

        if(orz==1)

        {

             scanf("%lld%lld%lld",&l,&r,&x);

             if(x>maxn){printf("0\n");continue;}

             printf("%lld\n",query(root[r],1,maxn,x)-query(root[l-1],1,maxn,x));

        }

        else

        {

             scanf("%lld",&l);

             insert(root[l],1,maxn,a[l],-1,root[l-1]);

             insert(root[l],1,maxn,a[l+1],1,root[l-1]);

             swap(a[l],a[l+1]);

        }

    }

}

巴特西

【模拟8.03】数颜色（vector//主席树）

最新文章

热门文章