Найти самый длинный общий подмассив с одним и тем же элементом в диапазоне от l до r для нескольких запросов

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, элемент = 1, вывод будет 1

Запрос 3: l = 6, r = 9, элемент = 3, вывод будетбудет 1

Запрос 4: l = 6, r = 9, element = 1, выходной результат будет 2

Я могу запустить цикл от l до r и вычислить самое продолжительное непрерывное вхождениеданный элемент в ассортименте, но мне нужен лучший подход. Ограничения: 1 <= l, r, no. запросов, размер массива <= 100000 Вот мой код грубой силы: </p>

#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) для запроса.