P9572 「NnOI R2-T4」Colorful Days♪

· · 题解

题目传送门

(姐姐砍我！)

令两个指针 si 与 ti ，分别指向 s 数组与 t 数组中的一个元素，他们的初始值均为 1 。

首先统计 s 数组中所有数的下标：

cin>>n>>m>>c1>>c2;
for(int i=1;i<=n;i++){
    cin>>s[i];
    v[s[i]].push_back(i);
}

对，要开 10^6 个 vector。并且我们能保证每个 v[i] 存的下标是单调递增的。

然后，对于每一个 ti ，先判断 v[t[ti]] 是否为空，即判断 t[ti]] 是否在 s 数组中出现过，如果没有就直接 ti++ 就行了。

如果有，就在 v[t[ti]] 中用 lower_bound 查找第一个 c 使 s[c]=t[ti] 。如果返回值为 v[t[ti]].end()，那么没有查到任何一个 c \leq si ，需要再拼一个 s 数组，即 k++，并且将 si 指向 s 数组内第一个等于 t[ti] 的数的下一个数，以便 lower_bound 正常运行。如果正常返回，那么直接把 si 指向查找结果的下一个就行了。对于上面两种情况，最长公共子序列的长度都要加 1 。

什么？你说你不知道什么是 lower_bound？这个函数返回的是一个升序区间内第一个大于等于参数值的指针，这你懂了吧？

指针 ti 最多遍历 m 次，lower_bound 的时间复杂度最坏为 O(\log n) ，故总时间复杂度为 O(m\log n) 。

下面是 AC 代码：

#include<bits/stdc++.h>
using namespace std;
int si,ti,c1,c2,t[10000001],s[10000001],k=1,cnt=0;
vector<int> v[1000001];
vector<int>::iterator it;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m>>c1>>c2;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        v[s[i]].push_back(i);
    }
    for(int i=1;i<=m;i++){
        cin>>t[i];
    }
    ti=1;
    si=1;
    while(1){
        while(v[t[ti]].empty()&&ti<=m)ti++;
        if(ti>m)break;
        cnt++;
        it=lower_bound(v[t[ti]].begin(),v[t[ti]].end(),si);
        if(it==v[t[ti]].end()){
            k++;
            si=*v[t[ti]].begin()+1;
        }
        else{
            si=*it+1;
        }
        ti++;
    }
    cout<<c1*cnt<<" "<<c2*k;
}