提高班作业 反复横跳 WA0求助

常规
1 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
int l[maxn][45],r[maxn][45];
int a[maxn];
int n,k,q;
int stk[maxn];
int top;
signed main()
{
    cin >> n >> k >> q;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++)
    {
        while(a[stk[top]] < a[i] && top >= 1)
        {
            top--;
        }
        l[i][0] = stk[top];
        stk[++top] = i;
    }
    top = 0;
    for(int i = n;i >= 1;i--)
    {
        while(a[stk[top]] < a[i] && top >= 1)
        {
            top--;
        }
        r[i][0] = stk[top];
        stk[++top] = i;
    }
    r[n][0] = r[n + 1][0] = n + 1;
    for(int i = 1;i <= 30;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            l[j][i] = min(l[l[j][i - 1]][i - 1],l[r[j][i - 1]][i - 1]);
            r[j][i] = max(r[r[j][i - 1]][i - 1],r[l[j][i - 1]][i - 1]);
        }
    }
    while(q--)
    {
        int a,b;
        cin >> a >> b;
        if(a > b)swap(a,b);
        int ans = 0;
        for(int i = 30;i >= 0;i--)
        {
            if(r[a][i] <= b && r[a][i] >= 1)
            {
                ans += (1ll << i);
                a = r[a][i];
            }
        }
        for(int i = 30;i >= 0;i--)
        {
            if(l[b][i] >= a && l[b][i] <= n)
            {
                ans += (1ll << i);
                b = l[b][i];
            }
        }
        cout << ans - 1 << '\n';
    }
    return 0;
}
2 个赞
2

思路就是倍增

2 个赞
3

查询部分感觉有一点问题，需要同步把两个指针移动把

 int l = a, r = a;
    for (int i = 19; i >= 0; i--) {
      int nl = min(L[l][i], L[r][i]);
      int nr = max(R[l][i], R[r][i]);
      if (nr < b)
        l = nl, r = nr, ans+=(1<<i);
    }
1 个赞
4

但是这样子不一定能走到 b 吧，老师。

下面那个代码还是 WA0.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
int l[maxn][45],r[maxn][45];
int a[maxn];
int n,k,q;
int stk[maxn];
int top;
signed main()
{
    cin >> n >> k >> q;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++)
    {
        while(a[stk[top]] < a[i] && top >= 1)
        {
            top--;
        }
        l[i][0] = stk[top];
        stk[++top] = i;
    }
    top = 0;
    for(int i = 1;i <= 30;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            r[i][j] = 0x3f3f3f3f;
        }
    }
    for(int i = n;i >= 1;i--)
    {
        while(a[stk[top]] < a[i] && top >= 1)
        {
            top--;
        }
        r[i][0] = stk[top];
        stk[++top] = i;
    }
    for(int i = 1;i <= 30;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            l[j][i] = min(l[l[j][i - 1]][i - 1],l[r[j][i - 1]][i - 1]);
            r[j][i] = max(r[r[j][i - 1]][i - 1],r[l[j][i - 1]][i - 1]);
        }
    }
    while(q--)
    {
        int a,b;
        cin >> a >> b;
        if(a > b)swap(a,b);
        int ans = 0;
        int L = a,R = a;
        for(int i = 30;i >= 0;i--)
        {
            int nl = min(l[L][i],l[R][i]);
            int nr = max(r[L][i],r[R][i]);
            if(nr < b)
            {
                L = nl;
                R = nr;
                ans += (1ll << i);
            }
        }
        cout << ans << '\n';
    }
    return 0;
}
1 个赞
5 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
int l[maxn][45],r[maxn][45];
int a[maxn];
int n,k,q;
int stk[maxn];
int top;
signed main()
{
    cin >> n >> k >> q;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++)
    {
        while(a[stk[top]] < a[i] && top >= 1)
        {
            top--;
        }
        l[i][0] = stk[top];
        stk[++top] = i;
    }
    top = 0;
    for(int i = n;i >= 1;i--)
    {
        while(a[stk[top]] < a[i] && top >= 1)
        {
            top--;
        }
        r[i][0] = stk[top];
        stk[++top] = i;
    }
    for(int i = 1;i <= 19;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            l[j][i] = min(l[l[j][i - 1]][i - 1],l[r[j][i - 1]][i - 1]);
            r[j][i] = max(r[r[j][i - 1]][i - 1],r[l[j][i - 1]][i - 1]);
        }
    }
    while(q--)
    {
        int a,b;
        cin >> a >> b;
        if(a > b)swap(a,b);
        int ans = 0;
        int L = a,R = a;
        for(int i = 19;i >= 0;i--)
        {
            int nl = min(l[L][i],l[R][i]);
            int nr = max(r[L][i],r[R][i]);
            if(nr < b)
            {
                L = nl;
                R = nr;
                ans += (1ll << i);
            }
        }
        cout << ans << '\n';
    }
    return 0;
}
1 个赞
6 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int l[maxn][45],r[maxn][45];
int a[maxn];
int n,k,q;
int stk[maxn];
int top;
signed main()
{
    cin >> n >> k >> q;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
    }
    for(int i = 1;i <= n;i++)
    {
        while(a[stk[top]] < a[i] && top >= 1)
        {
            top--;
        }
        if (top!=0) l[i][0] = stk[top];
            else l[i][0]=i;
        stk[++top] = i;
    }
    top = 0;
    for(int i = n;i >= 1;i--)
    {
        while(a[stk[top]] < a[i] && top >= 1)
        {
            top--;
        }
        if (top!=0) r[i][0] = stk[top];
            else r[i][0]=i;
        stk[++top] = i;
    }
    l[0][0]=0;
    r[n + 1][0] = n + 1;
    for(int i = 1;i < 20;i++)
    {
        for(int j = 0;j <= n+1;j++)
        {
            l[j][i] = min(l[l[j][i - 1]][i - 1],l[r[j][i - 1]][i - 1]);
            r[j][i] = max(r[r[j][i - 1]][i - 1],r[l[j][i - 1]][i - 1]);
        }
    }
    while(q--)
    {
        int a,b;
        cin >> a >> b;
        if(a > b)swap(a,b);
        int ans = 0;
        int L=a,R=a;
        for(int i = 19;i >= 0;i--)
        {
            int nl = min(l[L][i], l[R][i]);
            int nr = max(r[L][i], r[R][i]);
            if(nr<b)
            {
                ans += (1ll << i);
                L=nl;
                R=nr;
            }
        }
        a = R;
        L = R = b;
        for(int i = 20;i >= 0;i--)
        {
            int nl = min(l[L][i], l[R][i]);
            int nr = max(r[R][i], r[L][i]);
            if(a<nl)
            {
                ans += (1ll << i);
                L=nl;
                R=nr;
            }
        }
        cout << ans<< '\n';
    }
    return 0;
}
1 个赞
7

拿你那个代码改的，可以看看

1 个赞