【bzoj1264】[AHOI2006]基因匹配Match 树状数组
2024-08-27 01:06:14
题解:
一道比较简单的题目
容易发现状态数只有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 ;
}
最新文章
- yum命令mysql,jdk,tomcat
- 【原】jquery图片预览
- 史上最易懂的Android jni开发资料--NDK环境搭建
- EXT学习之——Ext下拉框绑定无效的问题
- 函数hash_get_nth_cell
- 问题-Delphi编译时提示缺少delphi自己的单元文件
- [转] JAVA正则表达式:Pattern类与Matcher类详解(转)
- Mencached使用
- build.gradle代码
- Java面试步步走
- fopen()函数参数
- linux网络编程之一-----多播(组播)编程
- Mybatis 系列10
- Lumen框架-错误&;日志
- RDIFramework.NET ━ .NET快速信息化系统开发框架 V3.2-新增锁定用户与解除锁定用户的功能
- Linux(Ubuntu)使用日记(四)------印象笔记相关使用
- RT-SA-2019-004 Cisco RV320 Unauthenticated Diagnostic DataRetrieval
- HCharts随笔之简单入门
- python中numpy.pad简单填充0用法
- 二、xadmin----简单使用
热门文章
- linux快速将磁盘额外空间扩展到某一挂载点
- spring集成cxf实现webservice接口功能
- linux中shell变量$#,$@,$0,$1,$2的含义解释 (转载)
- backtrace和backtrace_symbols
- python学习第16天。
- 进程、线程、GIL、同步、异步、并行、并发、互斥锁
- elasticsearch中的java.io.IOException: 远程主机强迫关闭了一个现有的连接
- [maven] dependency标签理解
- jq获取页面url后边带的参数
- bat如何实现图片与名字匹配重命名