結果

問題 No.749 クエリ全部盛り
ユーザー pazzle1230pazzle1230
提出日時 2018-10-19 23:37:00
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 651 ms / 3,000 ms
コード長 7,611 bytes
コンパイル時間 2,081 ms
コンパイル使用メモリ 189,152 KB
実行使用メモリ 167,444 KB
最終ジャッジ日時 2024-11-18 22:47:23
合計ジャッジ時間 6,403 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;
const double eps = 1e-10;
template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}
template<class ValueMonoid, class OperatorMonoid, class Modifier,
template<class...> class Container=::std::vector>
class LazySegTree{
public:
using value_structure = ValueMonoid;
using value_type = typename value_structure::value_type;
using operator_structure = OperatorMonoid;
using operator_type = typename operator_structure::value_type;
using modifier = Modifier;
using const_reference = const value_type &;
using container_value_type = Container<value_type>;
using container_operator_type = Container<operator_type>;
using size_type = typename container_value_type::size_type;
private:
container_value_type tree;
container_operator_type lazy;
size_type size_, height;
static size_type getsize(const size_type x){
size_type ret = 1;
while(ret < x)
ret <<= 1;
return ret;
}
static size_type getheight(const size_type x){
size_type ret = 0;
while((static_cast<size_type>(1) << ret) < x){
ret++;
}
return ret;
}
inline static value_type calc(const value_type a, const value_type b){
return value_structure::operation(a, b);
}
inline static void apply(operator_type &data, const operator_type a){
data = operator_structure::operation(data, a);
}
inline static value_type reflect(const value_type v, const operator_type o){
return modifier::operation(v, o);
}
void push(const size_type index){
tree[index] = reflect(tree[index], lazy[index]);
apply(lazy[index << 1], lazy[index]);
apply(lazy[index << 1 | 1], lazy[index]);
lazy[index] = operator_structure::identity();
}
void calc_node(const size_type index){
if(tree.size() <= (index << 1 | 1)) return;
assert(0 < index);
tree[index] = calc(reflect(tree[index << 1], lazy[index << 1]),
reflect(tree[index << 1 | 1], lazy[index << 1 | 1]));
}
void build(size_type index){
while(index >>= 1){
calc_node(index);
}
}
void propagate(const size_type index){
for(size_type shift = height; shift ; --shift){
push(index >> shift);
}
}
void rebuild(){
for(size_type i = size_-1;i > 0;--i){
calc_node(i);
}
}
public:
LazySegTree() : size_(0), height(0), tree(), lazy(){}
LazySegTree(const size_type size)
: size_(size), height(getheight(size)),
tree(size << 1, value_structure::initializer()),
lazy(size << 1, operator_structure::identity()){
rebuild();
}
template<class InputIterator>
LazySegTree(InputIterator first, InputIterator last)
: size_(::std::distance(first, last)){
height = getheight(size_);
tree = container_value_type(size_, value_structure::identity());
lazy = container_operator_type(size_ << 1, operator_structure::identity());
tree.insert(tree.end(), first, last);
rebuild();
}
size_type size() const { return size_; }
const_reference operator[](const size_type k){
assert(k < size_);
propagate(k+size_);
tree[k+size_] = reflect(tree[k+size_], lazy[k+size_]);
lazy[k+size_] = operator_structure::identity();
return tree[k+size_];
}
value_type query(size_type l, size_type r){
assert(l <= r);
assert(0 <= l && l < size_);
assert(0 <= r && r <= size_);
value_type retl = value_structure::identity(),
retr = value_structure::identity();
l += size_;
r += size_;
propagate(l);
propagate(r-1);
for(; l < r ; l >>= 1, r >>= 1){
if(l&1){
retl = calc(retl, reflect(tree[l], lazy[l]));
l++;
}
if(r&1){
r--;
retr = calc(reflect(tree[r], lazy[r]), retr);
}
}
return calc(retl, retr);
}
void update(size_type l, size_type r, const operator_type& data){
assert(l <= r);
assert(0 <= l && l < size_);
assert(0 <= r && r <= size_);
l += size_;
r += size_;
propagate(l);
propagate(r - 1);
for(size_type l_ = l, r_ = r; l_ < r_ ; l_ >>= 1, r_ >>= 1){
if(l_ & 1) apply(lazy[l_++], data);
if(r_ & 1) apply(lazy[--r_], data);
}
build(l);
build(r - 1);
}
template<class F>
void update(size_type index, const F& f){
assert(0 <= index && index < size());
index += size_;
propagate(index);
tree[index] = f(::std::move(tree[index]));
lazy[index] = operator_structure::identity();
build(index);
}
/*
template<class F>
size_type search(const F& f) const { // [0, result) is True and [0, result-1) is not.
if(f(value_structure::identity()))
return 0;
if(!f(tree[1]))
return size_+1;
value_type acc = value_structure::identity();
size_type i = 1;
while(i <
}
*/
};
const int64 mod = 1e9+7;
int64 gcd(int64 a, int64 b){
if(b == 0) return a;
return gcd(b, a%b);
}
vector<int64> fib;
struct value{
int64 v;
int64 l, r;
value():v(0), l(0), r(0){}
value(int64 v_, int64 l_, int64 r_){
v = v_; l = l_; r = r_;
}
const value operator+(const value& rhs) const{
return value((v+rhs.v)%mod, l, rhs.r);
};
};
class vmonoid{
public:
using value_type = value;
static value_type identity(){return value(0, 0, 0);}
static value_type initializer(){return value(0, 0, 0);}
static value_type operation(const value_type& a, const value_type& b){
return value((a.v+b.v)%mod, a.l, b.r);
}
};
class omonoid{
public:
using value_type = tuple<int64, int64, int64, int64>;
static value_type identity(){return value_type(0, 1, -1, 0);}
static value_type operation(const value_type& a, const value_type& b){
int64 a0, a1, a2, a3, b0, b1, b2, b3;
tie(a0, a1, a2, a3) = a;
tie(b0, b1, b2, b3) = b;
//printf("(%lld %lld %lld), (%lld %lld %lld), ", a0, a1, a2, b0, b1, b2);
if(b2 > -1){
// printf("(%lld %lld %lld)\n", 0LL, 1LL, b2);
return b;
}
//printf("(%lld %lld %lld)\n", a0*b1+b0, a1*b1, a2);
return value_type((a0*b1%mod+b0)%mod, a1*b1%mod, a2, ((a3*b1)%mod+b3)%mod);
}
};
class modifier{
public:
using vl = vmonoid::value_type;
using op = omonoid::value_type;
static vl operation(const vl& a, const op& b){
int64 a0, a1, a2, a3;
tie(a0, a1, a2, a3) = b;
if(a2 > -1){
return value(((a2*a1%mod+a0)%mod*(a.r-a.l)%mod+((fib[a.r]-fib[a.l]+mod)%mod)*a3%mod)%mod, a.l, a.r);
}
return value(((a.v*a1%mod+a0*(a.r-a.l)%mod)%mod+(fib[a.r]-fib[a.l]+mod)%mod*a3%mod)%mod, a.l, a.r);
}
};
int32 N, Q;
void init(){
fib.resize(N+1, 0);
fib[2] = 1;
FOR(i, 3, N+1){
fib[i] = fib[i-1]+fib[i-2];
fib[i] %= mod;
}
FOR(i, 1, N+1){
fib[i] += fib[i-1];
fib[i] %= mod;
}
}
int main(void){
cin.tie(0);
ios::sync_with_stdio(false);
scanf("%d %d", &N, &Q);
init();
vector<value> v(N);
REP(i, N){
v[i] = value(0, i, i+1);
}
LazySegTree<vmonoid, omonoid, modifier>
lsg(v.begin(), v.end());
REP(i, Q){
int64 q, l, r, k;
scanf("%lld %lld %lld %lld", &q, &l, &r, &k); r++;
if(q == 0){
printf("%lld\n", lsg.query(l, r).v*k%mod);
}else if(q == 1){
lsg.update(l, r, omonoid::value_type(0, 1, k, 0));
}else if(q == 2){
lsg.update(l, r, omonoid::value_type(k, 1, -1, 0));
}else if(q == 3){
lsg.update(l, r, omonoid::value_type(0, k, -1, 0));
}else if(q == 4){
lsg.update(l, r, omonoid::value_type(0, 1, -1, k));
}
/*
REP(i, N){
cout << lsg[i].v << " ";
}
cout << endl;
*/
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0