【bzoj1264】[AHOI2006]基因匹配Match 树状数组

题解：

一道比较简单的题目

容易发现状态数只有5*n个

而转移需要满足i1<i2;j1<j2

那么很明显是二维平面数点

暴力一点就是二维树状数组+map

5nlog^3 比较卡常

但是注意到我们的dp是保证了i1<i2的

所以本质是扫描线+树状数组

5nlogn

由于代码非常简单编译调试一遍过

代码：

#include <bits/stdc++.h>

using namespace std;

#define IL inline

#define rint register int

#define rep(i,h,t) for (rint i=h;i<=t;i++)

#define dep(i,t,h) for (rint i=t;i>=h;i--)

#define mid ((h+t)/2)

#define me(x) memset(x,0,sizeof(x))

#define lowbit(x) (x&(-x))

const int N=2e5;

int n,a[N],b[N],f[N][],cnt[N];

char ss[<<],*A=ss,*B=ss;

IL char gc()

{

  return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;

}

template<class T>IL void read(T &x)

{

  rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=(c^);

  while (c=gc(),<c&&c<) x=(x<<)+(x<<)+(c^); x*=f;

}

IL void maxx(int &x,int y)

{

  if (x<y) x=y;

}

struct sgt{

  int data[N];

  int query(int x)

  {

    int ans=;

    while (x)

    {

      maxx(ans,data[x]);

      x-=lowbit(x);

    }

    return(ans);

  }

  void insert(int x,int y)

  {

    while (x<=n)

    {

      maxx(data[x],y);

      x+=lowbit(x);

    }

  }

}S;

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  read(n); n*=;

  rep(i,,n) read(a[i]);

  rep(i,,n) read(b[i]);

  rep(i,,n)

    f[b[i]][++cnt[b[i]]]=i;

  int ans=;

  rep(i,,n)

    dep(j,,)

    {

      int kk=S.query(f[a[i]][j]-)+;

      S.insert(f[a[i]][j],kk);

      maxx(ans,kk);

    }

  cout<<ans<<endl;

  return ;

}