为什么没有人用树状数组

P1439 【模板】最长公共子序列

dongzhen @ 2024-08-02 11:15:23

二分的思路好难想，树状数组又好想又简洁，题解一个都没有，树状数组转移一样是 O(nlogn)

for(int i=1;i<=n;++i){w[read()]=i;}
for(int i=1;i<=n;++i){
    date[i]=read();
    dp[i]=t.query(w[date[i]])+1;
    t.update(w[date[i]],dp[i]);
    ans=max(ans,dp[i]);
}

状态定义也可以直接由O(n^2)优化得来

by wukaichen888 @ 2024-08-02 11:20:12

你说得对

by XuYueming @ 2024-08-02 11:20:18

@dongzhen tlqtj

by Po7ed @ 2024-08-02 11:26:24

我就这么用的

by dongzhen @ 2024-08-02 14:21:22

@XuYueming ,对不起，下次不发代码了，只是想说一下感想而已

by chenzeen @ 2024-08-02 14:30:02

结果这题绿->黄

by _czy @ 2024-08-08 09:21:13

因为在本题 a_i 两两不同的情况才是 O(nlogn)，在一般的范围时，可以卡到 O(n^2logn)，详见这。

by heike305 @ 2024-08-09 16:06:26

@dongzhen 建议写篇题解，私信管理给你强制加上去

by dongzhen @ 2024-08-09 16:19:11

@_czy 如果这样，二分算法也是 O(nlogn)，就题论题，对于这样的题目，树状数组可以完美替代二分，如导弹拦截

|