P5906 题解

· · 题解

众所周知，模板题当然不能模板做。

众所周知，对于静态序列询问，一种很奇葩但是很好想的思路是：预处理所有序列的答案，然后依次回答。

但是很多时候内存和时间都不允许我们这么做，所以就有了线段树等数据结构和莫队。

考虑数据结构维护，发现题目要求的东西不符合结合性和可减性；考虑莫队，但是删除元素不好转移，我又不会回滚莫队。

所以我们返璞归真，考虑下一开始的思想能不能搞。

我们每隔 L 个点选择一个“关键点”，然后只预处理以关键点为端点的询问。

对于同一个端点，可以 O(n) 求出所有答案：从当前端点开始不断加数，记录下每个数第一次出现的位置，然后做差更新答案即可。

这样预处理部分时间复杂度 O(\frac{n^2}{L})，空间复杂度 O(\frac{n^2}{L^2})。

询问时，先选择一个被询问区间包含的最长预处理区间“继承”答案，然后将两侧的数暴力加进来（这样的数不超过 2L 个。），方法是用动态数组（包括但不限于 std::vector 等）存下每个数字出现的位置（记得离散化），加数时二分一下就行（详见代码部分）。

这一部分空间复杂度 O(n)，时间复杂度 O(nL\log n)。

总时间复杂度 O(n(\frac{n}{L}+L\log n))，在 L=O(\sqrt{\frac{n}{\log n}}) 时达到最小值 O(n\sqrt{n\log n})，此时空间复杂度为 O(n\log n)，均可通过本题。

（不过后面一部分的常数显著大于预处理，经过我自己的测试取 L=\frac{1}{2}\sqrt{\frac{n}{\log_2n}} 时更好的选择。）

理论复杂度劣于根号分治和回滚莫队，但这是高贵的在线解法啊。

当然如果有 O(1) 往区间加数统计答案的方法的话理论复杂度就不劣了，但我暂时没想到。

代码（有用的部分大概不到 50 行）：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<random>
#include<unordered_map>
using namespace std;

namespace code{
    using ll=long long;
    using ull=unsigned long long;
    using uint=unsigned int;
#define F(i,x,y) for(int i=(x),__tt2__=(y);i<=__tt2__;i++)
#define R(i,x,y) for(int i=(x),__tt2__=(y);i>=__tt2__;i--)
#define _F(i,x,y) for(int i=(x),__tt2__=(y);i<__tt2__;i++)
#define _R(i,x,y) for(int i=(x),__tt2__=(y);i>__tt2__;i--)
#define debug(x) cout<<#x<<'='<<(x)<<endl
    constexpr int N=200005,B=4000,L=N/B;
    int ans[B+1][B+1];
    int a[N];
    unordered_map<int,int>t;
    vector<int>s[N];
    int first[N];
    int main(){
        cin.tie(0)->sync_with_stdio(0);
        int n;
        cin>>n;
        F(i,1,n){
            cin>>a[i];
            if(!t[a[i]])t[a[i]]=i;
            a[i]=t[a[i]];
            s[a[i]].push_back(i);
        }
        const int tmp=n/L;
        F(i,0,tmp){
            int j=i*L-1;
            F(k,0,tmp){
                if(k!=0)ans[i][k]=ans[i][k-1];
                while(j<k*L){
                    j++;
                    if(first[a[j]]<i*L)first[a[j]]=j;
                    ans[i][k]=max(ans[i][k],j-first[a[j]]);
                }
            }
        }
        int m;
        cin>>m;
        while(m--){
            int l,r;
            cin>>l>>r;
            const int bl=(l-1)/L+1,br=r/L;
            int rans=ans[bl][br];
            _F(i,l,min(bl*L,r)){
                rans=max(rans,*(upper_bound(s[a[i]].begin(),s[a[i]].end(),r)-1)-i);
            }
            _R(i,r,max(br*L,l)){
                rans=max(rans,i-*(lower_bound(s[a[i]].begin(),s[a[i]].end(),l)));
            }
            cout<<rans<<'\n';
        }
        return 0;
    }
}
signed main(){return code::main();}