procon

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub mugen1337/procon

:warning: 順列である連続部分列の数え上げ
(tips/CountSubpermutation.hpp)

概要

https://codeforces.com/contest/1175/problem/F
https://kmjp.hatenablog.jp/entry/2019/09/02/0930

ある部分列が順列であるかどうかを判定するためにはhashが速い．
他には区間種類数+区間maxもあるが，hashが爆速だし，その気になれば余裕で更新に耐えうる

Depends on

Code

// https://codeforces.com/problemset/problem/1175/F

#include "../template.hpp"

#include "../Other/RandomNumberGenerator.hpp"

// 1-indexed permutation
ll Subpermutations(vector<int> v){
    int n=(int)v.size();

    RandomNumberGenerator rng;
    vector<ll> hash(n+1),hash_s(n+2,0);
    for(int i=1;i<=n;i++){
        hash[i]=rng(0,1<<31);
        hash_s[i]=hash_s[i-1]^hash[i];
    }
    ll res=0;
    // 1の右に最大値がある場合, 1の左に最大値がある場合で解く
    rep(_,2){
        vector<ll> hash_vs(n+1,0);
        rep(i,n){
            hash_vs[i+1]=hash_vs[i]^hash[v[i]];
        }

        rep(i,n)if(v[i]==1){
            if(_) res++;
            int mx=0;
            for(int j=i+1;j<n;j++){
                if(v[j]==1) break;
                chmax(mx,v[j]);
                if(j+1-mx>=0 and ((hash_vs[j+1]^hash_vs[j+1-mx])==hash_s[mx])) res++;
            }
        }
        reverse(ALL(v));
    }

    return res;
}

signed main(){
    int n;cin>>n;
    vector<int> a(n);
    cin>>a;
    cout<<Subpermutations(a)<<endl;
    return 0;
}
#line 1 "tips/CountSubpermutation.hpp"
// https://codeforces.com/problemset/problem/1175/F

#line 1 "template.hpp"
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) begin(x),end(x)
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}
template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

#line 4 "tips/CountSubpermutation.hpp"

#line 1 "Other/RandomNumberGenerator.hpp"
struct RandomNumberGenerator{
    mt19937 mt;
    RandomNumberGenerator():mt(chrono::steady_clock::now().time_since_epoch().count()){}
    // [a,b)
    int operator()(int a,int b){
        uniform_int_distribution<int> d(a,b-1);
        return d(mt);
    }
};
#line 6 "tips/CountSubpermutation.hpp"

// 1-indexed permutation
ll Subpermutations(vector<int> v){
    int n=(int)v.size();

    RandomNumberGenerator rng;
    vector<ll> hash(n+1),hash_s(n+2,0);
    for(int i=1;i<=n;i++){
        hash[i]=rng(0,1<<31);
        hash_s[i]=hash_s[i-1]^hash[i];
    }
    ll res=0;
    // 1の右に最大値がある場合, 1の左に最大値がある場合で解く
    rep(_,2){
        vector<ll> hash_vs(n+1,0);
        rep(i,n){
            hash_vs[i+1]=hash_vs[i]^hash[v[i]];
        }

        rep(i,n)if(v[i]==1){
            if(_) res++;
            int mx=0;
            for(int j=i+1;j<n;j++){
                if(v[j]==1) break;
                chmax(mx,v[j]);
                if(j+1-mx>=0 and ((hash_vs[j+1]^hash_vs[j+1-mx])==hash_s[mx])) res++;
            }
        }
        reverse(ALL(v));
    }

    return res;
}

signed main(){
    int n;cin>>n;
    vector<int> a(n);
    cin>>a;
    cout<<Subpermutations(a)<<endl;
    return 0;
}
Back to top page