社区讨论

求助,样例已过

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 条回复,欢迎继续交流。

正在加载回复...