結果

問題 No.404 部分門松列
ユーザー tottoripaper
提出日時 2016-10-23 23:29:44
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 4,749 bytes
コンパイル時間 3,306 ms
コンパイル使用メモリ 173,976 KB
実行使用メモリ 27,904 KB
最終ジャッジ日時 2024-11-24 02:08:49
合計ジャッジ時間 11,223 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)

using ll = long long;
using P = std::tuple<ll,ll>;

const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};

// I want to delete this stupid solution ;(
#define sandwich(x) [](auto a, auto b){return (x)(a, b);}

template <typename T>
using F2 = std::function<T(T,T)>;

template <typename T, int N, typename F = std::plus<T>>
    struct SegmentTree{
        SegmentTree(T u, F f = F()){
            size = 1;
            while(size < N){
                size <<= 1;
            }
            
            unit = u;
            func = f;
            
            init();
        }
        void init(){
            for(int i=0;i<size;++i){
                data[i+size] = unit;
            }
            
            for(int i=size-1;i>0;--i){
                data[i] = func(data[i*2], data[i*2+1]);
            }
        }
        void update(int k, int v){
            k += size;
            data[k] = v;
            
            while(k > 1){
                k >>= 1;
                data[k] = func(data[k*2], data[k*2+1]);
            }
        }
        inline T query(int l, int r){
            return _query(l, r, 1, 0, size);
        }
        T _query(int a, int b, int k, int l, int r){
            if(b <= l || r <= a){return unit;}
            if(a <= l && r <= b){return data[k];}
            int mid = (l + r) >> 1;
            return func(_query(a, b,   2*k,   l, mid),
                        _query(a, b, 2*k+1, mid, r  ));
        }
        
        T unit, data[N*4];
        int size;
        F func;
    };

template <int N>
struct SegmentTree2{
    SegmentTree2(){
        size = 1;
        while(size < N){
            size <<= 1;
        }
            
        init();
    }
    void init(){
        for(int i=0;i<size;++i){
            data[i] = std::make_tuple(0, 0);
        }

        memset(data2, 0, sizeof(data2));
    }
    void addFirst(int k, int v){
        fst(data[k]) += v;
        data2[k + size] = fst(data[k]) * snd(data[k]);
        update(k + size);
    }
    void addSecond(int k, int v){
        snd(data[k]) += v;
        data2[k + size] = fst(data[k]) * snd(data[k]);
        update(k + size);
    }
    
    void update(int k){
        while(k > 1){
            k >>= 1;
            data2[k] = data2[k*2] + data2[k*2+1];
        }
    }
    inline ll query(int l, int r){
        return _query(l, r, 1, 0, size);
    }
    ll _query(int a, int b, int k, int l, int r){
        if(b <= l || r <= a){return 0ll;}
        if(a <= l && r <= b){return data2[k];}
        int mid = (l + r) >> 1;
        return _query(a, b,   2*k,   l, mid) +
            _query(a, b, 2*k+1, mid, r);
    }
        
    P data[N];
    ll data2[N*4];
    int size;
};

int N, Q;
int A[200000], L[200000], H[200000];

void compress(){
    vector<int> v(A, A+N);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    
    for(int i=0;i<N;++i){
        A[i] = lower_bound(v.begin(), v.end(), A[i]) - v.begin();
    }

    for(int i=0;i<Q;++i){
        L[i] = lower_bound(v.begin(), v.end(), L[i]) - v.begin();
        H[i] = upper_bound(v.begin(), v.end(), H[i]) - v.begin();
    }
}

SegmentTree<ll, 200000> segtree_l(0), segtree_r(0), segtree(0);
SegmentTree2<200000> segtree2;

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

    std::cin >> N;

    for(int i=0;i<N;++i){
        std::cin >> A[i];
    }
   
    std::cin >> Q;

    for(int i=0;i<Q;++i){
        std::cin >> L[i] >> H[i];
    }
    
    compress();

    // for(int i=0;i<Q;++i){
    //     std::cout << L[i] << ", " << H[i] << std::endl;
    // }
    
    for(int i=0;i<N-2;++i){
        segtree_l.update(A[i], segtree_l.query(A[i], A[i]+1) + 1);
        segtree2.addFirst(A[i], 1);
    }

    segtree_r.update(A[N-1], 1);
    segtree2.addSecond(A[N-1], 1);

    for(int i=N-2;i>0;--i){
        ll mx_p_n = 1ll * segtree_l.query(0, A[i]) * segtree_r.query(0, A[i]) - segtree2.query(0, A[i]),
           mn_p_n = 1ll * segtree_l.query(A[i]+1, N) * segtree_r.query(A[i]+1, N) - segtree2.query(A[i]+1, N);

        // std::cout << i << ": " << A[i] << ", " << (mx_p_n + mn_p_n) << std::endl;
        
        segtree.update(A[i], segtree.data[A[i] + segtree.size] + mx_p_n + mn_p_n);
        segtree_l.update(A[i-1], segtree_l.data[A[i-1] + segtree_l.size] - 1);
        segtree_r.update(A[i], segtree_r.data[A[i] + segtree_r.size] + 1);
        segtree2.addFirst(A[i-1], -1);
        segtree2.addSecond(A[i], +1);
    }
    
    for(int i=0;i<Q;++i){
        printf("%lld\n", segtree.query(L[i], H[i]));
    }
}
0