图片说明
图片说明

  • 题意：
    输入俩个序列，rmq(w,l,r)表示w序列从al到ar的最小值的下标 。
    题目要求输出最大的r，且要求区间1到r的rmq(w,l,r) == rmq(v,l,r)对任意的1到r的子串都相等

  • 题解：
    定义俩个stack，从1到n，分别插入俩个队列的元素，始终维护这俩个stack的队首元素是以当前元素的最小的元素，如果俩个stack的大小不一样，就输出i-1，如果没有，输出n。
    准确的说stack的size是从1到当前值距离最小值的距离。

代码：

#include <bits/stdc++.h>
using namespace std;
int a[100010],b[100010];
int main()
{
    int n;
    while(cin>>n&&n)
    {
        int flag = 0,ans = 0;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
            cin>>b[i];
        stack<int> s1,s2;
        for(int i=1;i<=n;i++)
        {
            while(!s1.empty() && s1.top() > a[i])
                s1.pop();
            while(!s2.empty() && s2.top() > b[i])
                s2.pop();
            s1.push(a[i]),s2.push(b[i]);
            if(s1.size() != s2.size()){
                flag = 1;
                ans = i-1;
            }
            if(flag)
                break;
        }
        if(flag){
            cout<<ans<<endl;
        }else{
            cout<<n<<endl;
        }
    }
    return 0;
}