結果
問題 | No.749 クエリ全部盛り |
ユーザー |
![]() |
提出日時 | 2019-03-02 23:39:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 600 ms / 3,000 ms |
コード長 | 13,330 bytes |
コンパイル時間 | 3,275 ms |
コンパイル使用メモリ | 192,268 KB |
実行使用メモリ | 58,624 KB |
最終ジャッジ日時 | 2024-06-23 13:05:18 |
合計ジャッジ時間 | 8,675 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <stdlib.h>#include <assert.h>#include <iostream>#include <algorithm>#include <functional>#include <queue>#include <deque>#include <stack>#include <list>#include <set>#include <map>#include <unordered_set>#include <unordered_map>#include <cmath>#include <complex>#include <iomanip>#include <bitset>#include <random>using namespace std;using i64 = int_fast64_t;using ui64 = uint_fast64_t;using db = long double;using pii = pair<int, int>;using pli = pair<int_fast64_t, int>;using pll = pair<int_fast64_t, int_fast64_t>;using pdi = pair<double, int>;template <class T> using vct = vector<T>;template <class T> using heap = priority_queue<T>;template <class T> using minheap = priority_queue<T, vector<T>, greater<T>>;template <class T> constexpr T inf = numeric_limits<T>::max() / 4 - 1;constexpr int dx[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0};constexpr int dy[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0};constexpr long double gold = 1.618033988;constexpr long double eps = 1e-15;#define mod 1000000007#define stdout_precision 10#define stderr_precision 2#define itr(i,v) for(auto i = begin(v); i != end(v); ++i)#define ritr(i,v) for(auto i = rbegin(v); i != rend(v); ++i)#define rep(i,n) for(int i = 0; i < (n); ++i)#define all(v) begin(v), end(v)#define rall(v) rbegin(v), rend(v)#define fir first#define sec second#define fro front#define bac back#define u_map unordered_map#define u_set unordered_set#define l_bnd lower_bound#define u_bnd upper_bound#define rsz resize#define ers erase#define emp emplace#define emf emplace_front#define emb emplace_back#define pof pop_front#define pob pop_back#define mkp make_pair#define mkt make_tuple#define popcnt __builtin_popcountstruct setupper {setupper() {ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);std::cerr.tie(nullptr);std::cout << fixed << setprecision(stdout_precision);std::cerr << fixed << setprecision(stderr_precision);// #ifdef Local// std::cerr << "\n---stderr---\n";// auto print_atexit = []() {// std::cerr << "Exec time : " << clock() / (double)CLOCKS_PER_SEC * 1000.0 << "ms\n";// std::cerr << "------------\n";// };// atexit((void(*)())print_atexit);// #endif}} setupper_;namespace std {template <class T> void hash_combine(size_t &seed, T const &key) {seed ^= hash<T>()(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2);}template <class T, class U> struct hash<pair<T,U>> {size_t operator()(pair<T,U> const &pr) const{size_t seed = 0;hash_combine(seed,pr.first);hash_combine(seed,pr.second);return seed;}};template <class Tup, size_t index = tuple_size<Tup>::value - 1> struct hashval_calc {static void apply(size_t& seed, Tup const& tup) {hashval_calc<Tup, index - 1>::apply(seed, tup);hash_combine(seed,get<index>(tup));}};template <class Tup> struct hashval_calc<Tup,0> {static void apply(size_t& seed, Tup const& tup) {hash_combine(seed,get<0>(tup));}};template <class ...T> struct hash<tuple<T...>> {size_t operator()(tuple<T...> const& tup) const{size_t seed = 0;hashval_calc<tuple<T...>>::apply(seed,tup);return seed;}};}template <class T, class U> istream &operator>> (istream &s, pair<T,U> &p) { return s >> p.first >> p.second; }template <class T, class U> ostream &operator<< (ostream &s, const pair<T,U> p) { return s << p.first << " " << p.second; }template <class T> ostream &operator<< (ostream &s, const vector<T> &v) {for(size_t i = 0; i < v.size(); ++i) s << (i ? " " : "") << v[i];return s;}#define dump(...) cerr << " [ " << __LINE__ << " : " << __FUNCTION__ << " ] " << #__VA_ARGS__ << " : ";\dump_func(__VA_ARGS__)template <class T> void dump_func(T x) { cerr << x << '\n'; }template <class T,class ...Rest> void dump_func(T x, Rest ... rest) { cerr << x << ","; dump_func(rest...); }template <class T = int> T read() { T x; return cin >> x, x; }template <class T> void write(T x) { cout << x << '\n'; }template <class T, class ...Rest> void write(T x, Rest ... rest) { cout << x << ' '; write(rest...); }void writeln() {}template <class T, class ...Rest> void writeln(T x, Rest ... rest) { cout << x << '\n'; writeln(rest...); }#define esc(...) writeln(__VA_ARGS__), exit(0)namespace updater {template <class T> static void add(T &x, const T &y) { x += y; }template <class T> static void ext_add(T &x, const T &y, size_t w) { x += y * w; }template <class T> static void mul(T &x, const T &y) { x *= y; }template <class T> static void ext_mul(T &x, const T &y, size_t w) { x *= (T)pow(y,w); }template <class T> static bool chmax(T &x, const T &y) { return x < y ? x = y,true : false; }template <class T> static bool chmin(T &x, const T &y) { return x > y ? x = y,true : false; }};using updater::chmax;using updater::chmin;template <class T> T minf(const T &x, const T &y) { return min(x,y); }template <class T> T mixf(const T &x, const T &y) { return max(x,y); }bool bit(i64 n, uint8_t e) { return (n >> e) & 1; }i64 mask(i64 n, uint8_t e) { return n & ((1 << e) - 1); }int ilog(uint64_t x, uint64_t b = 2) { return x ? 1 + ilog(x / b,b) : -1; }template <class F> i64 binry(i64 ok, i64 ng, const F &fn) {while (abs(ok - ng) > 1) {i64 mid = (ok + ng) / 2;(fn(mid) ? ok : ng) = mid;}return ok;}template <class A, size_t N, class T> void init(A (&array)[N], const T &val) { fill((T*)array,(T*)(array + N),val); }template <class A> void cmprs(A ary[], size_t n) {vector<A> tmp(ary,ary + n);tmp.erase(unique(begin(tmp),end(tmp)), end(tmp));for(A *i = ary; i != ary + n; ++i) *i = l_bnd(all(tmp),*i) - begin(tmp);}template <class T> void cmprs(vector<T> &v) {vector<T> tmp = v; sort(begin(tmp),end(tmp));tmp.erase(unique(begin(tmp),end(tmp)), end(tmp));for(auto i = begin(v); i != end(v); ++i) *i = l_bnd(all(tmp),*i) - begin(tmp);}template <class F> void for_subset(uint_fast64_t s, const F &fn) {uint_fast64_t tmp = s;do { fn(tmp); } while((--tmp &= s) != s);}namespace Calcfn {#ifndef mod#define mod 1000000007LL#endifstruct Modint {int x;constexpr Modint() : x(0) {}constexpr Modint(uint_fast64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}constexpr Modint &operator+=(const Modint &p) {if((x += p.x) >= mod) x -= mod;return *this;}constexpr Modint &operator-=(const Modint &p) {if((x += mod - p.x) >= mod) x -= mod;return *this;}constexpr Modint &operator*=(const Modint &p) {x = (int) (1LL * x * p.x % mod);return *this;}constexpr Modint &operator/=(const Modint &p) {*this *= inverse(p);return *this;}constexpr Modint operator-() { return Modint(-x); }constexpr Modint operator+(const Modint &p) { return Modint(*this) += p; }constexpr Modint operator-(const Modint &p) { return Modint(*this) -= p; }constexpr Modint operator*(const Modint &p) { return Modint(*this) *= p; }constexpr Modint operator/(const Modint &p) { return Modint(*this) /= p; }constexpr bool operator==(const Modint &p) { return x == p.x; }constexpr bool operator!=(const Modint &p) { return x != p.x; }constexpr bool operator!() { return !x; }constexpr bool operator>(const Modint &p) { return x > p.x; }constexpr bool operator<(const Modint &p) { return x < p.x; }constexpr bool operator>=(const Modint &p) { return x >= p.x; }constexpr bool operator<=(const Modint &p) { return x <= p.x; }constexpr static Modint inverse(const Modint &p) {int a = p.x, b = mod, u = 1, v = 0;while(b > 0) {int t = a / b;a -= t * b;a ^= b ^= a ^= b;u -= t * v;u ^= v ^= u ^= v;}return Modint(u);}constexpr static Modint pow(Modint p, uint_fast64_t e) {Modint ret(1);while(e) {if(e & 1) ret *= p;p *= p;e >>= 1;}return ret;}friend ostream &operator<<(ostream &s, const Modint &p) { return s << p.x; }friend istream &operator>>(istream &s, Modint &p) {uint_fast64_t x;p = Modint((s >> x,x));return s;}};constexpr static unsigned int N = 100007;struct impl {uint_fast64_t fact_[N + 1],invfact_[N + 1],inv_[N + 1];constexpr impl() : fact_(),invfact_(),inv_() {fact_[0] = 1;for(int i = 1; i <= N; ++i) fact_[i] = fact_[i - 1] * i % mod;inv_[1] = 1;for(int i = 2; i <= N; ++i) inv_[i] = mod - inv_[mod % i] * (mod / i) % mod;invfact_[0] = 1;for(int i = 1; i <= N; ++i) invfact_[i] = invfact_[i - 1] * inv_[i] % mod;}};constexpr static impl impl_exe;constexpr static Modint fact(int x) {return x >= 0 ? impl_exe.fact_[x] : 0;}constexpr static Modint invfact(int x) {return x >= 0 ? impl_exe.invfact_[x] : 0;}constexpr static Modint comb(int x, int y) {return fact(x) * invfact(y) * invfact(x - y);}constexpr static Modint perm(int x, int y) {return comb(x,y) * fact(y);}constexpr static int_fast64_t gcd(int_fast64_t a, int_fast64_t b) {if(!b) return a > 0 ? a : -a; return gcd(b, a % b);}constexpr static int_fast64_t lcm(int_fast64_t a, int_fast64_t b) {if(a | b) return a / gcd(a, b) * b; return 0;}constexpr static uint_fast64_t ext_gcd(uint_fast64_t a, uint_fast64_t b, int_fast64_t &x, int_fast64_t &y) {uint_fast64_t d = a;if (b) d = ext_gcd(b, a % b, y, x), y -= (a / b) * x;else x = 1, y = 0;return d;}constexpr static Modint modinv(uint_fast64_t x) {int_fast64_t z = 0,y = 0;ext_gcd(x,mod,z,y);return Modint(z);}constexpr static Modint modpow(Modint x, uint_fast64_t e) {if(!e) return 1;if(!x) return 0;return modpow(x * x, e >> 1) * (e & 1 ? x : 1);}}using Calcfn::Modint;using Calcfn::fact;using Calcfn::invfact;using Calcfn::comb;int n,qry;Modint fib[1<<20];struct trp {Modint p,q,r;};auto lazy_opr=[](trp &x,trp y){trp tmp;tmp.p=x.p*y.p;tmp.q=x.q*y.p+y.q;tmp.r=x.r*y.p+y.r;x=tmp;};auto opr=[](trp x,trp y) {return (trp){x.p+y.p,x.q+y.q,x.r+y.r};};auto updopr=[](trp &x,trp y) {x.p=x.p*y.p+x.q*y.q+x.r*y.r;};struct segtr{const static int N=1<<20;trp dat[N<<1],lazy[N<<1];bool lazyflag[N<<1]={};segtr() {fill(all(dat),(trp){0,0,0});fill(all(lazy),(trp){1,0,0});fib[0]=0; fib[1]=1;rep(i,1000010) fib[i+2]=fib[i]+fib[i+1];for(int i=0; i<n; ++i) dat[i+N].q=fib[i],dat[i+N].r=1;for(int i=N-1; i; --i) dat[i]=opr(dat[i*2],dat[i*2+1]);}void eval(int k,int l,int r) {if(!lazyflag[k]) return;updopr(dat[k],lazy[k]);if(r - l > 1) {lazy_opr(lazy[k * 2],lazy[k]);lazy_opr(lazy[k * 2 + 1],lazy[k]);lazyflag[k * 2] = lazyflag[k * 2 + 1] = true;}lazy[k] = {1,0,0};lazyflag[k] = false;}void update(int a,int b,trp val,int k=1,int l=0,int r=N) {eval(k,l,r);if(b <= l || r <= a) return;if(a <= l && r <= b) {lazy_opr(lazy[k],val);lazyflag[k] = true;eval(k,l,r);} else {update(a,b,val,k * 2,l,l + r >> 1);update(a,b,val,k * 2 + 1,l + r >> 1,r);dat[k] = opr(dat[k * 2],dat[k * 2 + 1]);}}trp query(int a,int b,int k=1,int l=0,int r=N) {if(b <= l || r <= a) return (trp){0,0,0};eval(k,l,r);if(a <= l && r <= b) return dat[k];return opr(query(a,b,k * 2,l,l + r >> 1),query(a,b,k * 2 + 1,l + r >> 1,r));}};signed main() {cin>>n>>qry;segtr sg;while(qry--) {int q,l,r,k; cin>>q>>l>>r>>k;if(q) {trp tmp;switch (q){case 1:tmp={0,0,k};break;case 2:tmp={1,0,k};break;case 3:tmp={k,0,0};break;case 4:tmp={1,k,0};break;default:break;}sg.update(l,r+1,tmp);//cout<<sg.query(l,r+1).p<<endl;} else {cout<<sg.query(l,r+1).p*k<<endl;}}}