题解:

一道比较简单的题目

容易发现状态数只有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 ;
}

最新文章

  1. yum命令mysql,jdk,tomcat
  2. 【原】jquery图片预览
  3. 史上最易懂的Android jni开发资料--NDK环境搭建
  4. EXT学习之——Ext下拉框绑定无效的问题
  5. 函数hash_get_nth_cell
  6. 问题-Delphi编译时提示缺少delphi自己的单元文件
  7. [转] JAVA正则表达式:Pattern类与Matcher类详解(转)
  8. Mencached使用
  9. build.gradle代码
  10. Java面试步步走
  11. fopen()函数参数
  12. linux网络编程之一-----多播(组播)编程
  13. Mybatis 系列10
  14. Lumen框架-错误&amp;日志
  15. RDIFramework.NET ━ .NET快速信息化系统开发框架 V3.2-新增锁定用户与解除锁定用户的功能
  16. Linux(Ubuntu)使用日记(四)------印象笔记相关使用
  17. RT-SA-2019-004 Cisco RV320 Unauthenticated Diagnostic DataRetrieval
  18. HCharts随笔之简单入门
  19. python中numpy.pad简单填充0用法
  20. 二、xadmin----简单使用

热门文章

  1. linux快速将磁盘额外空间扩展到某一挂载点
  2. spring集成cxf实现webservice接口功能
  3. linux中shell变量$#,$@,$0,$1,$2的含义解释 (转载)
  4. backtrace和backtrace_symbols
  5. python学习第16天。
  6. 进程、线程、GIL、同步、异步、并行、并发、互斥锁
  7. elasticsearch中的java.io.IOException: 远程主机强迫关闭了一个现有的连接
  8. [maven] dependency标签理解
  9. jq获取页面url后边带的参数
  10. bat如何实现图片与名字匹配重命名