违规用户名920406 @ 2025-01-11 12:33:31
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,x,a[N],b[N],t[N];
void update(int x,int y)
{
for(;x<=n;x+=x&-x) t[x]=max(t[x],y);
}
int query(int x)
{
int ans=0;
for(;x;x-=x&-x) ans=max(ans,t[x]);
return ans;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>x,b[x]=i;
for(int i=1;i<=n;i++) cin>>x,a[i]=b[x];
for(int i=1;i<n;i++) update(a[i],query(a[i])+1);
cout<<query(a[n])+1;
return 0;
}前三个点AC，后面全WA
树状数组求LIS很正常吧？
by lyh0217 @ 2025-01-11 12:38:08
@违规用户名920406
LIS中a[n]不一定一定会被选到吧……
by 违规用户名920406 @ 2025-01-11 12:38:52
@lyh0217 已关注
by 违规用户名920406 @ 2025-01-11 12:39:23
@lyh0217 有道理，我是唐氏儿
by luogu_hezhenmin1 @ 2025-01-11 13:27:50
@违规用户名920406 ？？？这道题居然橙题？？？
那整个洛谷就没有紫题和黑题了
by jiangyixuan_eason @ 2025-01-11 13:32:06
@违规用户名920406 你管这叫橙题？
by 违规用户名920406 @ 2025-01-11 14:05:12
@luogu_hezhenmin1@jiangyixuan_eason
暴力LIS应该降红，树状数组应该降橙，所以优化版LIS应该也是橙，而这道题经过了一个简单的变换，肯定还是橙色，根本没有绿
by 违规用户名920406 @ 2025-01-11 14:07:08
@luogu_hezhenmin1 你真的会FFT？我看你通过记录里面有，关了关了
by luogu_hezhenmin1 @ 2025-01-11 14:12:52
@违规用户名920406 啊？我没过啊？
而且树状数组板子都是黄
by luogu_hezhenmin1 @ 2025-01-11 14:16:13
我不是python过的吗