Codeforces 1175F The Number of Subpermutations (思维+rmq)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：

求区间[l, r]是一个1~r-l+1的排列的区间个数

n<=3e5

思路：

如果[l,r]是一个排列，首先这里面的数应该各不相同，然后max(l,r)应该等于r-l+1，这就能唯一确定这个区间满足条件了

我们只需要预处理出对于每个左端点，它能伸延到的最远的r，使得l到r各不相同，然后暴力

注意如果对于一次暴力不满足max(l,r)==r-l+1，那么此时r应该跳到l+max(r-l+1)-1，因为在这里才至少可能会满足条件

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#include<functional>

#define fst first

#define sc second

#define pb push_back

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

#define lowbit(x) ((x)&(-x)) 

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const db eps = 1e-;

const int mod = 1e9+;

const int maxn = 2e6+;

const int maxm = 2e6+;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

int a[maxn];

int d[maxn][];

int n;

void init(){

    for(int i = ; i <= n; i++) d[i][] =a[i];

    for(int j = ; (<<j) <= n; j++){

        for(int i = ; i + (<<j) -  <= n; i++){

            d[i][j] = max(d[i][j-], d[i + (<<(j-))][j-]);

        }

    }

}

int rmq(int l, int r){

    int k = ;

    while((<<(k+)) <= r-l+)k++;

    return max(d[l][k], d[r-(<<k)+][k]);

}

int mx[maxn];

int id[maxn];

int main() {

    scanf("%d", &n);

    for(int i = ; i <= n; i++){

        scanf("%d", &a[i]);

    }

    mx[n+]=n;

    for(int i = n; i >= ; i--){

        if(id[a[i]])mx[i]=min(mx[i+],id[a[i]]-);

        else mx[i]=mx[i+];

        id[a[i]]=i;

    }

    init();

    int ans=;

    for(int i = ; i <= n; i++){

        int j = i;

        while(j<=mx[i]){

            //printf("%d %d %d\n",i,j,rmq(i,j));

            if(rmq(i,j)==j-i+){ans++;j++;}

            else j=i+rmq(i,j)-;

        }

    }

    printf("%d",ans);

    return ;

}