社区讨论
求助,样例已过
P4303[AHOI2006] 基因匹配参与者 1已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lo8k3wur
- 此快照首次捕获于
- 2023/10/27 19:55 2 年前
- 此快照最后确认于
- 2023/10/27 19:55 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef double db;
const int N=1e5+50;
const int M=1e5+50;
inline ll read(){
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
ll t,n;
ll a[N],f[N];
ll maxn[N<<2];
vector<ll>pos[N];
ll ls(ll x){return x<<1;}
ll rs(ll x){return x<<1|1;}
void push_up(ll p){
maxn[p]=max(maxn[ls(p)],maxn[rs(p)]);
}
void update(ll nx,ll ny,ll l,ll r,ll p,ll k){
if(nx<=l&&r<=ny){
maxn[p]=max(maxn[p],k);
return;
}
ll mid=(l+r)>>1;
if(nx<=mid) update(nx,ny,l,mid,ls(p),k);
if(ny>mid) update(nx,ny,mid+1,r,rs(p),k);
push_up(p);
}
ll query(ll nx,ll ny,ll l,ll r,ll p){
ll res=0;
if(nx<=l&&r<=ny) return maxn[p];
ll mid=(l+r)>>1;
if(nx<=mid) res=max(res,query(nx,ny,l,mid,ls(p)));
if(ny>mid) res=max(res,query(nx,ny,mid+1,r,rs(p)));
return res;
}
int main()
{
n=read();
for(int i=1;i<=5*n;++i){
ll x;
x=read();
pos[x].push_back((ll)i);
}
for(int i=1;i<=5*n;++i){
a[i]=read();
if(pos[a[i]].size()==0) continue;
sort(pos[a[i]].begin(),pos[a[i]].end());
for(int j=pos[a[i]].size()-1;j>=0;--j){
ll res=query(1,pos[a[i]][j],1,5*n,1);
update(pos[a[i]][j],pos[a[i]][j],1,5*n,1,res+1);
}
}
printf("%lld\n",query(1,5*n,1,5*n,1));
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...