codeforces 1175F rmq+区间不重复

题意：找从[l,r]每一个元素都不重复且最大值为r-l+1的区间数

题解：先找到以i为左端点的最远右端点r，然后rmq判断一下最大值是不是r-l+1思路

rmq直接套板子就可以

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10, INF = 0x3f3f3f3f;
#define pi acos(-1.0)
int a[maxn],d[maxn][25];
int vis[maxn],mx[maxn];
int n;
void init()
{
    for(int i=1;i<=n;i++)
        d[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            d[i][j]=max(d[i][j-1],d[i+(1<<j-1)][j-1]);
}
int rmq(int l,int r)
{
    int k=log2(r-l+1);
    return max(d[l][k],d[r-(1<<k)+1][k]);
}

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    mx[n+1]=n;
    for(int i=n;i>=1;i--){
        if(vis[a[i]])mx[i]=min(mx[i+1],vis[a[i]]-1);
        else mx[i]=mx[i+1];
        vis[a[i]]=i;
    }
    init();
    int ans=0;
    for(int i=1;i<=n;i++){
        int j=i;
        while(j<=mx[i]){
            if(rmq(i,j)==j-i+1){
                ans++;
                j++;
            }else j=i+rmq(i,j)-1;
        }
    }
    cout<<ans<<endl;
}