結果

問題 No.992 最長増加部分列の数え上げ
ユーザー ningenMe
提出日時 2020-02-20 20:10:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 346 ms / 2,000 ms
コード長 6,451 bytes
コンパイル時間 1,101 ms
コンパイル使用メモリ 91,060 KB
実行使用メモリ 34,944 KB
最終ジャッジ日時 2024-10-08 19:09:52
合計ジャッジ時間 13,084 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>

using namespace std;
using ll = long long;
const ll MOD = (ll)1e9 + 7;

template<class Operator> class SegmentTree {
    Operator Op;                            //Operator 演算子、型、単位元を持つ
    using typeNode = decltype(Op.unitNode); //nodeの型
    size_t length;                          //セグメント木の最下段の要素の数(vectorの要素の数を超える2べきの数)
    vector<typeNode> node;                  //ノード
    
public:
    
    //unitで初期化
    SegmentTree(const size_t num){
        for (length = 1; length < num; length *= 2);
        node.resize(2 * length, Op.unitNode);
    }
    
    //vectorで初期化
    SegmentTree(const vector<typeNode> & vec){
        for (length = 1; length < vec.size(); length *= 2);
        node.resize(2 * length, Op.unitNode);
        for (int i = 0; i < vec.size(); ++i) node[i + length] = vec[i];
        for (int i = length - 1; i >= 0; --i) node[i] = Op.funcNode(node[(i<<1)+0],node[(i<<1)+1]);
    }
    
    //同じinitで初期化
    SegmentTree(const size_t num, const typeNode init) {
        for (length = 1; length < num; length *= 2);
        node.resize(2 * length, init);
    }
    
    //idx : 0-indexed
    void update(size_t idx, const typeNode var) {
        if(idx < 0 || length <= idx) return;
        idx += length;
        node[idx] = Op.funcMerge(node[idx],var);
        while(idx >>= 1) node[idx] = Op.funcNode(node[(idx<<1)+0],node[(idx<<1)+1]);
    }
    
    //[l,r)
    typeNode get(int l, int r) {
        if (l < 0 || length <= l || r < 0 || length < r) return Op.unitNode;
        typeNode vl = Op.unitNode, vr = Op.unitNode;
        for(l += length, r += length; l < r; l >>=1, r >>=1) {
            if(l&1) vl = Op.funcNode(vl,node[l++]);
            if(r&1) vr = Op.funcNode(node[--r],vr);
        }
        return Op.funcNode(vl,vr);
    }
    
    void print(){
        cout << "{ " << get(0,1);
        for(int i = 1; i < length; ++i) cout << ", " << get(i,i+1);
        cout << " }" << endl;
        
        for(int i = 1,j = 1; i < 2*length; ++i) {
            cout << node[i] << " ";
            if(i==((1<<j)-1) && ++j) cout << endl;
        }
    }
    
};

template<class typeNode> struct nodeMaxRangeMerge {
    typeNode unitNode = {0,0};
    typeNode funcNode(typeNode l,typeNode r){return (l.first != r.first ? (l.first > r.first ? l : r) : make_pair(l.first,l.second + r.second));}
    typeNode funcMerge(typeNode l,typeNode r){return (l.first != r.first ? (l.first > r.first ? l : r) : r);}
};

template<long long mod> class ModInt {
public:
    long long x;
    ModInt():x(0) {
        // do nothing
    }
    ModInt(long long y) : x(y>=0?(y%mod): (mod - (-y)%mod)%mod) {
        // do nothing
    }
    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator+=(const long long y) {
        ModInt p(y);
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator+=(const int y) {
        ModInt p(y);
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator-=(const long long y) {
        ModInt p(y);
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator-=(const int y) {
        ModInt p(y);
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    ModInt &operator*=(const ModInt &p) {
        x = (x * p.x % mod);
        return *this;
    }
    ModInt &operator*=(const long long y) {
        ModInt p(y);
        x = (x * p.x % mod);
        return *this;
    }
    ModInt &operator*=(const int y) {
        ModInt p(y);
        x = (x * p.x % mod);
        return *this;
    }
    ModInt &operator/=(const ModInt &p) {
        *this *= p.inv();
        return *this;
    }
    ModInt &operator/=(const long long y) {
        ModInt p(y);
        *this *= p.inv();
        return *this;
    }
    ModInt &operator/=(const int y) {
        ModInt p(y);
        *this *= p.inv();
        return *this;
    }
    ModInt operator=(const int y) {
        ModInt p(y);
        *this = p;
        return *this;
    }
    ModInt operator=(const long long y) {
        ModInt p(y);
        *this = p;
        return *this;
    }
    ModInt operator-() const { return ModInt(-x); }
    ModInt operator++() {
        x++;
        if(x>=mod) x-=mod;
        return *this;
    }
    ModInt operator--() {
        x--;
        if(x<0) x+=mod;
        return *this;
    }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }
    ModInt inv() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }
    ModInt pow(long long n) const {
        ModInt ret(1), mul(x);
        while(n > 0) {
            if(n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
    friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }
    friend istream &operator>>(istream &is, ModInt &a) {
        long long t;
        is >> t;
        a = ModInt<mod>(t);
        return (is);
    }
};
using modint = ModInt<MOD>;

int main() {
    int N; cin >> N;
    vector<ll> A(N);
    for(int i = 0; i < N; ++i) cin >> A[i];
    SegmentTree<nodeMaxRangeMerge<pair<int,modint>>> dp(N,{0,0});
    map<ll,vector<int>> mpv;
    for(int i = 0; i < N; ++i) mpv[A[i]].push_back(i);
    for(auto e:mpv) {
        auto v = e.second;
        vector<pair<int,modint>> tmp;
        for(auto r:v) {
            auto m = dp.get(0, r);
            if(m.first) m.first++;
            else m = {1,1};
            tmp.push_back(m);
        }
        for(int i = 0; i < v.size(); ++i) {
            dp.update(v[i], tmp[i]);
        }
    }
    cout << dp.get(0, N).second << endl;
}
0