c++ - 为多个查询找到 l 到 r 范围内具有相同元素的最长公共(public)子数组

Question

给定一个数组，我们需要为多个查询找到 l 到 r 范围内具有相同元素的最长连续子数组。例如，ar[] = {1,2,2,2,4,3,1,1,3}。

查询 1:l=1,r=5, element=2, 输出将为 3

查询 2:l=1,r=5, element=1, 输出将为 1

查询 3:l=6,r=9, element=3, 输出将为 1

查询 4: l=6,r=9, element=1, 输出为 2

我可以运行一个从 l 到 r 的循环，并计算范围内给定元素的最长连续出现次数，但我需要一种更好的方法。 约束是 1<=l,r,no。查询数，数组大小<=100000 这是我的蛮力代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
    ll i,j,k,m,n,l,r,x;
    n=9;
    ll ar[n]={1,2,2,2,4,3,1,1,3};
    ll query=4;//number of queries
    while(query--)
    {
        cin>>l>>r>>x;
        l--;r--;//changing to 0-based indexing
        ll ctr=0;
        ll ans=0;
        for(i=l;i<=r;i++)
        {
            if(ar[i]==x)
            {
                ctr++;
            }
            else ctr=0;
            ans=max(ctr,ans);
        }
        cout<<ans<<endl;
    }
}

Answer 1

这个问题可以用线段树来解决。

这是我的想法(未经测试)。

struct Node {
    // Length of this segment.
    int len;

    // Value and length of the longest prefix subarray.
    int prefix_val;
    int prefix_len;

    // Value and length of the longest suffix subarray.
    int suffix_val;
    int suffix_len;

    // Value and length of the longest subarray in this segment.
    int best_len;
    int best_val;
};

// Combines two nodes.
Node combine(Node lhs, Node rhs) {
    Node res;
    res.len = lhs.len + rhs.len;

    // Compute new best prefix subarray.
    res.prefix_val = lhs.prefix_val;
    res.prefix_len = lhs.prefix_len;
    if (lhs.prefix_len == lhs.len &&
        lhs.prefix_val == rhs.prefix_val) {
        res.prefix_len = lhs.len + rhs.prefix_len;
    }

    // Compute new best suffix subarray.
    res.suffix_val = rhs.suffix_val;
    res.suffix_len = rhs.suffix_len;
    if (rhs.suffix_len == rhs.len &&
        rhs.suffix_val == lhs.suffix_val) {
        res.suffix_len = rhs.len + lhs.suffix_len;
    }
    res.best_val = lhs.best_val;
    res.best_len = lhs.best_len;
    if (res.best_len < rhs.best_len) {
        res.best_val = rhs.best_val;
        res.best_len = rhs.best_len;
    }
    if (res.best_len < res.prefix_len) {
        res.best_val = res.prefix_val;
        res.best_len = res.prefix_len;
    }
    if (res.best_len < res.suffix_len) {
        res.best_val = res.suffix_val;
        res.best_len = res.suffix_len;
    }

    // Middle subarray.
    if (lhs.suffix_val == rhs.prefix_val) {
        int len = lhs.suffix_len + rhs.prefix_len;
        if (res.best_len < len) {
            res.best_val = val;
            res.best_len = len;
        }
    }
    return res;
}

每个查询的复杂度为 O(logN)。