#599848 (C++17) No.749 クエリ全部盛り

提出ソース
結果

問題	No.749 クエリ全部盛り
ユーザー	tsuyu93
提出日時	2021-01-06 20:01:37
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	507 ms / 3,000 ms
コード長	17,507 bytes
コンパイル時間	3,226 ms
コンパイル使用メモリ	225,872 KB
実行使用メモリ	108,928 KB
最終ジャッジ日時	2024-11-07 06:52:07
合計ジャッジ時間	7,519 ms
ジャッジサーバーID （参考情報）	judge2 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	3 ms 5,248 KB
testcase_06	AC	4 ms 5,248 KB
testcase_07	AC	3 ms 5,248 KB
testcase_08	AC	3 ms 5,248 KB
testcase_09	AC	3 ms 5,248 KB
testcase_10	AC	20 ms 5,248 KB
testcase_11	AC	20 ms 5,248 KB
testcase_12	AC	21 ms 5,248 KB
testcase_13	AC	20 ms 5,248 KB
testcase_14	AC	19 ms 5,248 KB
testcase_15	AC	495 ms 108,928 KB
testcase_16	AC	503 ms 108,928 KB
testcase_17	AC	507 ms 108,800 KB
testcase_18	AC	501 ms 108,800 KB
testcase_19	AC	507 ms 108,928 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
/*
          author:ryo3ihara
            date:2021-01-06  18:59:31
            　　”継続は力なり、雨だれ石を穿つ”
            　　　　　　”slow but steady wins the race”

*/

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>

//#include<atcoder/all>
//using namespace atcoder;

/*
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mpb = boost::multiprecision;
using bint = mpb::cpp_int;
// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)
using Real = mpb::number<mpb::cpp_dec_float<1024>>;
*/
#ifdef __HOGE__
#pragma region macro
#endif
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pii = pair<int, int>;
using pld = pair<ll, ld>;
using ppiii =  pair<pii, int>;
using ppiill = pair<pii, ll>;
using ppllll = pair<pll, ll>;
using pplii = pair<pli, int>;
using mii = map<int, int>;
using dll = deque<ll>;
using qll = queue<ll>;
using pqll = priority_queue<ll>;
using pqrll = priority_queue<ll, vector<ll>, greater<ll>>;
using pqrpll = priority_queue<pll, vector<pll>, greater<pll>>;
using vint = vector<int>;
using vbool = vector<bool>;
using vstr = vector<string>;
using vll = vector<ll>;
using vpll = vector<pll>;
using vvll = vector<vector<ll>>;
using vvint = vector<vector<int>>;
using vvbool = vector<vbool>;
using vvstr = vector<vstr>;
using vvpll = vector<vector<pll>>;
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll i=0;i<n;++i)
#define rep2(i,n) for(ll i=0;i<n;++i)
#define rep3(i,a,b) for(ll i=a;i<b;++i)
#define rep4(i,a,b,c) for(ll i=a;i<b;i+=c)
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i=n;i--;)
#define rrep2(i,n) for(ll i=n;i--;)
#define rrep3(i,a,b) for(ll i=b;i-->(a);)
#define rrep4(i,a,b,c) for(ll i=(a)+((b)-(a)-1)/(c)*(c);i>=(a);i-=c)
#define rrep(...) overload4(__VA_ARGS__,rrep4,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define each1(i,a) for(auto&&i:a)
#define each2(x,y,a) for(auto&&[x,y]:a)
#define each3(x,y,z,a) for(auto&&[x,y,z]:a)
#define each(...) overload4(__VA_ARGS__,each3,each2,each1)(__VA_ARGS__)
#define all1(i) begin(i),end(i)
#define all2(i,a) begin(i),begin(i)+a
#define all3(i,a,b) begin(i)+a,begin(i)+b
#define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__)
#define rall1(i) (i).rbegin(),(i).rend()
#define rall2(i,k) (i).rbegin(),(i).rbegin()+k
#define rall3(i,a,b) (i).rbegin()+a,(i).rbegin()+b
#define rall(...) overload3(__VA_ARGS__,rall3,rall2,rall1)(__VA_ARGS__)
#define SUM(...) accumulate(all(__VA_ARGS__),0LL)
#define ALL(x) x.begin(),x.end() 
#define rALL(x) x.rbegin(),x.rend() 
#define SIZE(x) ll(x.size()) 
#define Sort(a) sort(all(a))
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__;in(__VA_ARGS__)int scan(){ return getchar(); }
#define fs first
#define sc second
void scan(int& a){ scanf("%d", &a); }
void scan(unsigned& a){ scanf("%u", &a); }
void scan(long& a){ scanf("%ld", &a); }
void scan(long long& a){ scanf("%lld", &a); }
void scan(unsigned long long& a){ scanf("%llu", &a); }
void scan(char& a){ do{ a = getchar(); }while(a == ' ' || a == '\n'); }
void scan(float& a){ scanf("%f", &a); }
void scan(double& a){ scanf("%lf", &a); }
void scan(long double& a){ scanf("%Lf", &a); }
void scan(vector<bool>& a){ for(unsigned i = 0; i < a.size(); i++){ int b; scan(b); a[i] = b; } }
void scan(char a[]){ scanf("%s", a); }
void scan(string& a){ cin >> a; }
template<class T> void scan(vector<T>&);
template<class T, size_t size> void scan(array<T, size>&);
template<class T, class L> void scan(pair<T, L>&);
template<class T, size_t size> void scan(T(&)[size]);
template<class T> void scan(vector<T>& a){ for(auto&& i : a) scan(i); }
template<class T> void scan(deque<T>& a){ for(auto&& i : a) scan(i); }
template<class T, size_t size> void scan(array<T, size>& a){ for(auto&& i : a) scan(i); }
template<class T, class L> void scan(pair<T, L>& p){ scan(p.first); scan(p.second); }
template<class T, size_t size> void scan(T (&a)[size]){ for(auto&& i : a) scan(i); }
template<class T> void scan(T& a){ cin >> a; }
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){ scan(head); in(tail...); }
void print(){ putchar(' '); }
void print(bool a){ printf("%d", a); }
void print(int a){ printf("%d", a); }
void print(unsigned a){ printf("%u", a); }
void print(long a){ printf("%ld", a); }
void print(long long a){ printf("%lld", a); }
void print(unsigned long long a){ printf("%llu", a); }
void print(char a){ printf("%c", a); }
void print(char a[]){ printf("%s", a); }
void print(const char a[]){ printf("%s", a); }
void print(float a){ printf("%.15f", a); }
void print(double a){ printf("%.15f", a); }
void print(long double a){ printf("%.15Lf", a); }
void print(const string& a){ for(auto&& i : a) print(i); }
template<class T> void print(const complex<T>& a){ if(a.real() >= 0) print('+'); print(a.real()); if(a.imag() >= 0) print('+'); print(a.imag()); print('i'); }
template<class T> void print(const vector<T>&);
template<class T, size_t size> void print(const array<T, size>&);
template<class T, class L> void print(const pair<T, L>& p);
template<class T, size_t size> void print(const T (&)[size]);
template<class T> void print(const vector<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T> void print(const deque<T>& a){ if(a.empty()) return; print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T, size_t size> void print(const array<T, size>& a){ print(a[0]); for(auto i = a.begin(); ++i != a.end(); ){ putchar(' '); print(*i); } }
template<class T, class L> void print(const pair<T, L>& p){ print(p.first); putchar(' '); print(p.second); }
template<class T, size_t size> void print(const T (&a)[size]){ print(a[0]); for(auto i = a; ++i != end(a); ){ putchar(' '); print(*i); } }
template<class T> void print(const T& a){ cout << a; }
int out(){ putchar('\n'); return 0; }
template<class T> int out(const T& t){ print(t); putchar('\n'); return 0; }
template<class Head, class... Tail> int out(const Head& head, const Tail&... tail){ print(head); putchar(' '); out(tail...); return 0; }
#ifdef DEBUG
inline ll __lg(ull x){ return 63 - __builtin_clzll(x); }
#define debug(...) { print(#__VA_ARGS__); print(":"); out(__VA_ARGS__); }
#else
#define debug(...) void(0)
#endif
#define INF32 2147483647 //2.147483647x10^{9}:32bit整数のinf
#define INF64 9223372036854775807 //9.223372036854775807x10^{18}:64bit整数のinf
const ll MOD = 1000000007;
const int inf = 1e9;
const ll INF = 1e18;
const ll MAXR = 100000; //10^5:配列の最大のrange
const ld PI=3.1415926535897932;
inline void Yes(bool b = true) { cout << (b ? "Yes" : "No") << '\n'; }
inline void YES(bool b = true) { cout << (b ? "YES" : "NO") << '\n'; }
inline void OKNG(bool b = true) { cout << (b ? "OK" : "NG") << '\n'; }
inline void possible(bool i = true){ cout << (i?"possible":"impossible") << '\n'; }
inline void Possible(bool i = true){ cout << (i?"Possible":"Impossible") << '\n'; }
inline void POSSIBLE(bool i = true){ cout << (i?"POSSIBLE":"IMPOSSIBLE") << '\n'; }
template<typename A, typename B> inline bool chmin(A& a, B b) {if (a > b) {a = b;return true;}return false;}
template<typename A, typename B> inline bool chmax(A& a, B b) {if (a < b) {a = b;return true;}return false;}
template<typename A, typename B> A min(A a, B b) {if (a < b) {return a;}return b;}
template<typename A, typename B> A max(A a, B b) {if (a > b) {return a;}return b;}
template<class T> auto min(const T& a){ return *min_element(a.begin(),a.end()); }
template<class T> auto max(const T& a){ return *max_element(a.begin(),a.end()); }
template<typename A, typename B> A power(A a, B b) {A res=1;while (b>0) {if (b&1){res*=a;}b/=2;a*=a;}return res;}
template<typename A, typename B> A powmod(A a, B b) {A res=1;while (b>0) {if (b&1){res*=a;res%=MOD;}b/=2;a*=a;a%=MOD;}return res;}
template<typename A, typename B, typename C> A powmod(A a, B b,C m) {A res=1;while (b>0) {if (b&1){res*=a;res%=m;}b/=2;a*=a;a%=m;}return res;}
template<typename A> A nlcm(vector<A> a) {A res;res = a[0];for (ll i = 1; i < (ll)a.size(); i++) {res = lcm(res, a[i]);}return res;}
template<typename A> A ngcd(vector<A> a){A res;res = a[0];for(ll i = 1; i < (ll)a.size() && res != 1; i++) {res = gcd(a[i], res);}return res;}
#ifdef __HOGE__
#pragma endregion
#endif

//segment_tree_hyper
//findや、applyは半開区間
//要素にも作用素にも非可換モノイドが使用可

template <typename U>
class segment_tree{

    using T = typename U::typeT;
    using E = typename U::typeE;
    int num = 0, lognum = 0;
    std::vector<T> segtree_t;
    std::vector<E> segtree_e;
    std::vector<int> width;

public:

    segment_tree(int n, T deft){
        _constructor(n);
        std::fill(segtree_t.begin() + (1 << lognum), segtree_t.begin() + (1 << lognum) + n, deft);
        if(U::segtree_type != 2) for(int i = (1 << lognum) - 1; i != 0; i--){
            segtree_t[i] = U::func_tt(segtree_t[i << 1], segtree_t[(i << 1) + 1]);
        }
    }

    segment_tree(std::vector<T> &vec){
        _constructor(vec.size());
        std::copy(vec.begin(), vec.end(), segtree_t.begin() + (1 << lognum));
        if(U::segtree_type != 2) for(int i = (1 << lognum) - 1; i != 0; i--){
            segtree_t[i] = U::func_tt(segtree_t[i << 1], segtree_t[(i << 1) + 1]);
        }
    }

    void _constructor(int n){
        num = n;
        while((1 << lognum) < n) lognum++;
        segtree_t = std::vector<T>(1 << (lognum + 1), U::e_t);

        if(U::segtree_type != 1){
            segtree_e = std::vector<E>(1 << (lognum + 1), U::e_e);
        }
        if(U::segtree_type == 3){
            width = std::vector<int>(1 << (lognum + 1), 1);
            for(int i = (1 << lognum) - 1; i != 0; i--){
                width[i] = width[i << 1] + width[(i << 1) + 1];
            }
        }
    }

    inline void split_query(int ind){
        int ind2 = (ind << 1);
        if(U::segtree_type == 3){
            segtree_t[ind2]     = U::func_te(segtree_t[ind2]    , segtree_e[ind], width[ind2]);
            segtree_t[ind2 + 1] = U::func_te(segtree_t[ind2 + 1], segtree_e[ind], width[ind2]);
        }
        if(U::segtree_type != 1){
            segtree_e[ind2]     = U::func_ee(segtree_e[ind2]    , segtree_e[ind]);
            segtree_e[ind2 + 1] = U::func_ee(segtree_e[ind2 + 1], segtree_e[ind]);
            segtree_e[ind] = U::e_e;
        }
    }

    void apply(int bg, int ed, E query){
        if(U::segtree_type != 1){
            bg += (1 << lognum);
            ed += (1 << lognum);

            for(int i = lognum; i >= 1; i--){
                if(((bg >> i) << i) != bg) split_query(bg >> i);
                if(((ed >> i) << i) != ed) split_query((ed - 1) >> i);
            }

            int bg_temp = bg, ed_temp = ed - 1;
            while(bg_temp < ed_temp){
                if(bg_temp & 1){
                    segtree_e[bg_temp] = U::func_ee(segtree_e[bg_temp], query);
                    if(U::segtree_type == 3) segtree_t[bg_temp] = U::func_te(segtree_t[bg_temp], query, width[bg_temp]);
                    bg_temp++;
                }
                if(~ed_temp & 1){
                    segtree_e[ed_temp] = U::func_ee(segtree_e[ed_temp], query);
                    if(U::segtree_type == 3) segtree_t[ed_temp] = U::func_te(segtree_t[ed_temp], query, width[ed_temp]);
                    ed_temp--;
                }
                bg_temp >>= 1;
                ed_temp >>= 1;
            }
            if(bg_temp == ed_temp){
                segtree_e[bg_temp] = U::func_ee(segtree_e[bg_temp], query);
                if(U::segtree_type == 3) segtree_t[bg_temp] = U::func_te(segtree_t[bg_temp], query, width[bg_temp]);
            }

            if(U::segtree_type == 3) for(int i = 1; i <= lognum; i++){
                if(((bg >> i) << i) != bg){
                    segtree_t[bg >> i] = U::func_tt(segtree_t[(bg >> i) << 1], segtree_t[((bg >> i) << 1) + 1]);
                }
                if(((ed >> i) << i) != ed){
                    segtree_t[(ed - 1) >> i] = U::func_tt(segtree_t[((ed - 1) >> i) << 1], segtree_t[(((ed - 1) >> i) << 1) + 1]);
                }
            }
        }
    }

    void apply(int ind, E query){
        if(U::segtree_type == 1){
            ind += (1 << lognum);
            segtree_t[ind] = U::func_te(segtree_t[ind], query, 1);
            ind >>= 1;
            for(; ind != 0; ind >>= 1){
                segtree_t[ind] = U::func_tt(segtree_t[ind << 1], segtree_t[(ind << 1) + 1]);
            }
        }
    }

    T find(int bg, int ed){
        if(U::segtree_type != 2){
            bg += (1 << lognum);
            ed += (1 << lognum);
            
            if(U::segtree_type == 3) for(int i = lognum; i >= 1; i--){
                if(((bg >> i) << i) != bg) split_query(bg >> i);
                if(((ed >> i) << i) != ed) split_query((ed - 1) >> i);
            }

            T res1 = U::e_t, res2 = U::e_t;
            ed--;
            while(bg < ed){
                if(bg & 1){
                    res1 = U::func_tt(res1, segtree_t[bg]);
                    bg++;
                }
                if(~ed & 1){
                    res2 = U::func_tt(segtree_t[ed], res2);
                    ed--;
                }
                bg >>= 1;
                ed >>= 1;
            }
            if(bg == ed) res1 = U::func_tt(res1, segtree_t[bg]);
            res1 = U::func_tt(res1, res2);
            return res1;
        }
        return U::e_t;
    }

    T find(int ind){
        if(U::segtree_type == 2){
            ind += (1 << lognum);
            for(int i = lognum; i >= 1; i--){
                split_query(ind >> i);
            }

            segtree_t[ind] = U::func_te(segtree_t[ind], segtree_e[ind], 1);
            segtree_e[ind] = U::e_e;
            return segtree_t[ind];
        }
        return U::e_t;
    }

    void print(int n){
        std::cout << "val : ";
        for(auto itr = segtree_t.begin(); itr != segtree_t.end(); itr++){
            std::cout << std::right << std::setw(n) << *itr << " ";
        }
        std::cout << "\n";
        std::cout << "lazy: ";
        for(auto itr = segtree_e.begin(); itr != segtree_e.end(); itr++){
            std::cout << std::right << std::setw(n) << *itr << " ";
        }
        std::cout << "\n";
    }
};
//segment_tree<QUERY<ll>> Seg(vector）　で宣言
/*
template <typename T>
struct FINDquery_APPLYquery{
    static constexpr int segtree_type = 1:一点更新区間取得  2:区間更新一点取得  3:区間更新区間取得;
    using typeT = T;
    using typeE = T;
    static constexpr typeT e_t = 要素モノイドの単位元;（type2の時不要）
    static constexpr typeT e_e = 作用素モノイドの単位元;（type1の時不要）
    static typeT func_tt(typeT a, typeT b){return 要素モノイド同士の演算;}（type2の時不要）
    static typeT func_te(typeT a, typeE b, int w){return 作用素モノイドの要素モノイドへの作用;}
    static typeE func_ee(typeE a, typeE b){return 作用素モノイド同士の演算;}(type1の時不要）)
};
*/

//range affine range sum query 
//Seg.apply(w, x, std::make_pair(b, c)); で[w,x)のa_iに対してa_i ← b x a_i + c　に更新できる（b=0でcの更新、b=1でcの加算になる）
template <typename T>
struct RsummodQ_RaffineQ{
    static constexpr int segtree_type = 3;
    using typeT = std::pair<T, T>;
    using typeE = std::array<T, 3>;
    static constexpr typeT e_t = std::make_pair(0, 0);
    static constexpr typeE e_e = {1, 0, 0};
    static typeT func_tt(typeT a, typeT b){
        return std::make_pair((a.first + b.first) % MOD, (a.second + b.second) % MOD);
    }
    static typeT func_te(typeT a, typeE b, int w){
        return std::make_pair((b[0]*a.first + b[1]*(long long)w + b[2]*a.second)%MOD, a.second) ;
    }
    static typeE func_ee(typeE a, typeE b){
        return {(a[0]*b[0]) % MOD, (a[1]*b[0]+b[1]) % MOD,(a[2]*b[0] + b[2]) % MOD };
    }
};

signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //cout << fixed << setprecision(20);

    //入力
    ll N,Q;
    cin >> N >> Q;

    vpll A(N,{0,1});
    A[0].sc=0;
    rep(i,2,N)A[i].sc=(A[i-1].sc+A[i-2].sc)%MOD;

    segment_tree<RsummodQ_RaffineQ<ll>> Seg(A);

    rep(i,Q){
        ll q,l,r,k;
        cin >> q >> l >> r >> k;
        if(q==0){
            cout << (k*Seg.find(l,r+1).fs)%MOD << endl;
        }else if(q==1){
            Seg.apply(l,r+1,{0,k,0});
        }else if(q==2){
            Seg.apply(l,r+1,{1,k,0});
        }else if(q==3){
            Seg.apply(l,r+1,{k,0,0});
        }else{
            Seg.apply(l,r+1,{1,0,k});
        }
    }
    

    //cout << ans << endl;
  return 0;
}
yukicoder

結果

テストケース

ソースコード
