CF1927D 题解

yyrwlj · 2024-02-07 21:32:57 · 题解

题意简述

给定一个序列，每次询问要求输出区间 [l,r] 内的两个不同元素下标，若全部相同输出两个 -1。

思路

我们发现一个区间内的元素不全相同，当且仅当区间内的最大值不等于最小值，可以使用线段树维护。

输出位置就让线段树在维护最值时，同时维护最值的位置，在回朔统计两个子树信息时，看最值是由哪个子树转移过来的即可。

Code

#define v first
#define pos second
const int N = 200005;
typedef pair<int, int> PII;
int a[N];
PII mn[N << 2], mx[N << 2];
void build(int u,int l,int r)
{
    if (l == r)
    {
        mn[u] = mx[u] = {a[l], l};
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    if (mx[u << 1].v > mx[u << 1 | 1].v)
        mx[u] = {mx[u << 1].v, mx[u << 1].pos};
    else
        mx[u] = {mx[u << 1 | 1].v, mx[u << 1 | 1].pos};
    if (mn[u << 1].v < mn[u << 1 | 1].v)
        mn[u] = {mn[u << 1].v, mn[u << 1].pos};
    else
        mn[u] = {mn[u << 1 | 1].v, mn[u << 1 | 1].pos};
}
PII query1(int u,int l,int r,int L,int R)
{
    if (L <= l && r <= R)
        return mn[u];
    int mid = (l + r) >> 1;
    PII ans = {2e9, 0};
    if (L <= mid)
        ans = query1(u << 1, l, mid, L, R);
    if (mid < R)
    {
        PII ans2 = query1(u << 1 | 1, mid + 1, r, L, R);
        if (ans2.v < ans.v)
            ans = ans2;
    }
    return ans;
}
PII query2(int u,int l,int r,int L,int R)
{
    if (L <= l && r <= R)
        return mx[u];
    int mid = (l + r) >> 1;
    PII ans = {-2e9, 0};
    if (L <= mid)
        ans = query2(u << 1, l, mid, L, R);
    if (mid < R)
    {
        PII ans2 = query2(u << 1 | 1, mid + 1, r, L, R);
        if (ans2.v > ans.v)
            ans = ans2;
    }
    return ans;
}
void work()
{
    int n;
    scanf("%d", &n);
    for (int i=1;i<=n;i++)
        scanf("%d", &a[i]);
    build(1, 1, n);
    int q;
    scanf("%d", &q);
    while (q--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        PII ans1 = query1(1, 1, n, l, r), ans2 = query2(1, 1, n, l, r);
        if (ans1.v == ans2.v)
            puts("-1 -1");
        else
            printf("%d %d\n", ans1.pos, ans2.pos);
    }
    putchar('\n');
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
        work();
    return 0;
}