提出 #74391491

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()

struct FastSet {
    using u64 = u_int64_t;
    static constexpr u64 B = 64;
    u64 size;
    vector<vector<u64>> a;
    FastSet(u64 n) : size(n) {
        do a.emplace_back(n = (n + B - 1) / B);
        while(n > 1);
    }
    bool operator[](int i) { return a[0][i / B] >> (i % B) & 1; }
    void set(int i) {
        for(auto& v : a) {
            v[i / B] |= 1ULL << (i % B);
            i /= B;
        }
    }
    void reset(ll i) {
        for(auto& v : a) {
            v[i / B] &= ~(1ULL << (i % B));
            if(v[i / B]) break;
            i /= B;
        }
    }
    int next(int i) {  // i を超える最⼩の要素
        for (int h = 0; h < (int)a.size(); h++) {
            i++;
            if(i / B >= (int)a[h].size()) break;
            u64 d = a[h][i / B] >> (i % B);
            if(d) {
                i += countr_zero(d);
                while(h--) i = i * B + countr_zero(a[h][i]);
                return i;
            }
            i /= B;
        }
        return size;
    }
    int prev(int i) {  // i より小さい最⼤の要素
        for (int h = 0; h < (int)a.size(); h++) {
            i--;
            if(i < 0) break;
            u64 d = a[h][i / B] << (~i % B);
            if(d) {
                i -= countl_zero(d);
                while(h--) i = i * B + __lg(a[h][i]);
                return i;
            }
            i /= B;
        }
        return -1;
    }
};

// https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
namespace po167{
    struct mint61{
        using u64 = unsigned long long;
        static constexpr u64 MOD = (1ULL << 61) - 1;
        static constexpr u64 MASK30 = (1ULL << 30) - 1;
        static constexpr u64 MASK31 = (1ULL << 31) - 1;
        u64  x;
        u64 calcmod(u64 a){
            u64 au = (a >> 61);
            u64 ad = (a & MOD);
            u64 res = au + ad;
            if (res >= MOD) res -= MOD;
            return res;
        }
        mint61(){ x = 0;}
        mint61(long long x_){
            while (x_ < 0) x_ += MOD;
            x = calcmod(x_);
        }
        mint61 &operator+=(mint61 b){
            if ((x += b.x) >= MOD) x -= MOD;
            return *this;
        }
        mint61 &operator-=(mint61 b){
            if (x >= b.x) x -= b.x;
            else{
                x += MOD;
                x -= b.x;
            }
            return *this;
        }
        mint61 &operator*=(mint61 b){
            u64 au = (x >> 31);
            u64 ad = (x & MASK31);
            u64 bu = (b.x >> 31);
            u64 bd = (b.x & MASK31);
            u64 mid = ad * bu + au * bd;
            u64 midu = (mid >> 30);
            u64 midd = (mid & MASK30);
            x = calcmod(au * bu * 2 + midu + (midd << 31) + ad * bd);
            return *this;
        }
        friend mint61 operator+(mint61 a, mint61 b){return a += b;}
        friend mint61 operator-(mint61 a, mint61 b){return a -= b;}
        friend mint61 operator*(mint61 a, mint61 b){return a *= b;}
        friend bool operator==(mint61 a, mint61 b){return a.x == b.x;}
        friend bool operator!=(mint61 a, mint61 b){return a.x != b.x;}
        mint61 pow(long long e) const {
            mint61 r = 1,b =*this;
            if (e < 0) e = MOD - 1 + e % (MOD - 1);
            while (e){
                if (e & 1) r *= b;
                b *= b;
                e >>= 1;
            }
            return r;
        }
    };
}

using mint = po167::mint61;

random_device seed_gen;
mt19937 rng(seed_gen());
// return [l, r)
long long rand_long(long long l,long long r){
    return uniform_int_distribution<long long>(l,r-1)(rng);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];
    const int L = 200'200;
    FastSet fs(L);
    ll ans = 0;
    vector<mint> z(L);
    rep(i, 0, L) z[i] = rand_long(1, mint::MOD);
    vector<mint> z_sum(L);
    rep(i, 0, L - 1) z_sum[i + 1] = z_sum[i] + z[i];
    auto g = [&](int st, int en) -> tuple<vector<mint::u64>, vector<mint::u64>, vector<int>> {
        mint sum = 0;
        vector<mint::u64> real, small;
        int d = 1;
        vector<int> same;
        if (st > en) d = -1;
        for (int i = st; i != en + d; i += d){
            int a = A[i];
            while (fs[a]){
                fs.reset(a);
                sum -= z[a];
                a++;
            }
            fs.set(a);
            sum += z[a];
            real.push_back(sum.x);
            int l = fs.next(-1);
            int r = fs.prev(L);
            if (l == r) same.push_back(l);
            else small.push_back((z_sum[r + 1] - sum - z_sum[l] + z[l]).x);
        }
        while (true){
            int tmp = fs.next(-1);
            if (tmp == fs.size) break;
            fs.reset(tmp);
        }
        return {real, small, same};
    };
    auto h = [&](vector<auto> X, vector<auto> Y) -> ll {
        sort(all(X));
        sort(all(Y));
        int a = 0, b = 0;
        ll res = 0;
        while (a != (int)X.size() && b != (int)Y.size()){
            if (X[a] < Y[b]) a++;
            else if (X[a] > Y[b]) b++;
            else{
                int tmp = 0;
                while (a + tmp != (int)X.size() && X[a + tmp] == X[a]){
                    tmp++;
                }
                while (b != (int)Y.size() && X[a] == Y[b]){
                    b++;
                    res += tmp;
                }
                a += tmp;
            }
        }
        return res;
    };
    auto calc = [&](auto self, int l, int r) -> void {
        if (l + 1 == r){
            ans++;
            return;
        }
        int m = (l + r) / 2;
        self(self, l, m);
        self(self, m, r);
        auto [L_real, L_small, L_same] = g(m - 1, l);
        auto [R_real, R_small, R_same] = g(m, r - 1);
        ans += h(L_real, R_small);
        ans += h(L_small, R_real);
        ans += h(L_same, R_same);
    };
    calc(calc, 0, N);
    cout << ans << "\n";
}

提出情報

ジャッジ結果