[2021] number of effective sequences programmed by Tencent autumn recruitment technology post

If the data in the sequence is not repeated , Then the problem will be much less difficult . This paper introduces three solutions .

（1） Violence enumeration

Violent enumeration subsequence left and right endpoints i and j, Check a[i+1] To a[j-1] Whether there is a smaller value than the endpoint , Complexity O(N^3). Available 20 branch .

（2）RMQ Optimize

RMQ（Range Minimum/Maximum Query） It can be regarded as a search structure , We can find the extremum in the interval quickly , The complexity of each search is O(1) Level . In this way, the above algorithm “ Check a[i+1] To a[j-1] Whether there is a smaller value than the endpoint ” Optimize , The complexity of the whole algorithm O(N^2), Available 70 branch .

Introduce a trick to cheat points , When the author is working out big data , Such as the above 100000 Level data , Often, all data points are the same , Or is it 1,2,3,4.....100000 Such data points . If there is no good way in the end , And plenty of time , You can write code to deal with these special situations . This method does not guarantee effectiveness ！！！

（3） Monotonic stack

Wise remark of an experienced person ： If you enumerate a[i] It is the small value of sequence , Find the data a[i] The first problem at the left and right ends is much smaller than him , This is a typical monotone stack problem . Readers must master the basic usage of monotone stack before they can read the following problem-solving ideas .

This topic can consider enumerating the second i Elements ,a[i] Find the first one to the left a[i] Small value a[k], here [k,i] The interval must satisfy the condition ,

So can we continue to look to the left for smaller ？ After simulation, it is found that it is not possible , For example, the sequence 1 3 6 5 ,5 Find... On the left 3 You can stop , With 5 The next smallest sequence is （3,6, 5）,（1,3,6,5） You can't . Of course, it's possible i There is nothing smaller on the left side of the element , In this way, no subsequence satisfying the condition can be found .

The question translates to a[i], Whether there is a smaller value on the left and right sides .

If the data in the sequence is not repeated , According to the above analysis, do it once in both directions with monotone stack , enumeration i The element is the next hour, and the result can be obtained in all cases . If the data is repeated ？

For duplicate data , such as 1,3,1,4,1, The first 5 individual 1 Is a minor element , There are two on the left 1, In monotonous stack processing, if you meet the conditions, you will stop the stack operation . In this case, you need to adjust the lower stack structure , Keep it from storing duplicate elements , But you can know how many repeating elements there are . There are many ways , For example, the stack element uses a structure , Or use a counter （map） Record the number of elements with the same value in the stack （ The code to use map）.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,a[100005];
ll ans=0;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    cin>>n;
    for(i=1; i<=n; i++)
        cin>>a[i];
    stack<int>st;
    map<int,int>mp;/**< mp Counter , Used to record the number of the same elements in the stack , Ensure that the elements in the stack must be incremented , There won't be the same value  */
    for(i=1; i<=n; i++)
    {
        while(st.size()&&a[st.top()]>a[i])
        {
            mp[a[st.top()]]=0;/**<  The stack counter is cleared  */
            st.pop();
        }
        if(st.empty())
            st.push(i);
        else
        {
            if(a[i]>a[st.top()]) /**<  This is the calculation a[i] Is the second smallest value , On the left a[i] The big ones are out of the stack , Stack top ratio a[i] Small  */
                ans++,st.push(i);
            else if(a[i]==a[st.top()])
            {/**<  Handle stack top and a[i] The same thing , For example, in this case 3 3 3 3, The first 4 individual 3 And some on the left 3 Can match  */
                ans+=mp[a[st.top()]];/**<  Be careful not to enter the stack at this time , The top value of the stack will be mp[a[i]]++ */
                if(st.size()>1)/**< 1 3 3 3 3, This is the first time 4 individual 3 Not only on the left 3 Can match , And 1 collocation , Judge whether there is anything better than a[i] Small  */
                    ans++;
            }
        }
        mp[a[i]]++;
    }
    while(st.size())
        st.pop();
    for(i=n; i>=1; i--)/**<  In reverse, there is no need to deal with duplicate elements  */
    {
        while(st.size()&&a[st.top()]>=a[i])
            st.pop();
        if(!st.empty())
            ans++;
        st.push(i);
    }
    cout<<ans;
    return 0;
}

When the author writes the code on the spot, he can solve the problem only once .

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,a[100005];
ll ans=0;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    cin>>n;
    for(i=1; i<=n; i++)
        cin>>a[i];
    stack<int>st;
    map<int,ll>mp;/**< mp Counter , Used to record the number of the same elements in the stack , Ensure that the elements in the stack must be incremented , There won't be the same value  */
    for(i=1; i<=n; i++)
    {
        while(st.size()&&a[st.top()]>a[i])
        {/**<  The following sentence is actually a calculation a[i] Is the minimum case , Because all out of stack elements , Their values are greater than a[i]
             Why mp, Example sequence  3 3 3 3 1, At this time, there is only one in the stack 3, however mp[3]=4, and 1 And the one on the left 4 individual 3 Can form a sequence  */
            ans+=mp[a[st.top()]];
            mp[a[st.top()]]=0;/**<  The stack counter is cleared  */
            st.pop();
        }
        if(st.empty())
            st.push(i);
        else
        {
            if(a[i]>a[st.top()]) /**<  This is the calculation a[i] Is the second smallest value , On the left a[i] The big ones are out of the stack , Stack top ratio a[i] Small  */
                ans++,st.push(i);
            else if(a[i]==a[st.top()])
            {  /**<  Handle stack top and a[i] The same thing , For example, in this case 3 3 3 3, The first 4 individual 3 And some on the left 3 Can match  */
                ans+=mp[a[st.top()]];/**<  Be careful not to enter the stack at this time , The top value of the stack will be mp[a[i]]++ */
                if(st.size()>1)/**< 1 3 3 3 3, This is the first time 4 individual 3 Not only on the left 3 Can match , And 1 collocation , Judge whether there is anything better than a[i] Small  */
                    ans++;
            }
        }
        mp[a[i]]++;
    }
    cout<<ans;
    return 0;
}