結果
| 問題 | No.749 クエリ全部盛り |
| ユーザー |
 pred
|
| 提出日時 | 2021-01-06 19:26:25 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,596 bytes |
| コンパイル時間 | 686 ms |
| コンパイル使用メモリ | 74,500 KB |
| 最終ジャッジ日時 | 2024-11-14 23:57:57 |
| 合計ジャッジ時間 | 1,911 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:178:24: error: 'array' in namespace 'std' does not name a template type
178 | using typeE = std::array<T, 3>;
| ^~~~~
main.cpp:5:1: note: 'std::array' is defined in header '<array>'; did you forget to '#include <array>'?
4 | #include <iomanip>
+++ |+#include <array>
5 |
main.cpp:180:22: error: 'typeE' does not name a type; did you mean 'typeT'?
180 | static constexpr typeE e_e = {1, 0, 0};
| ^~~~~
| typeT
main.cpp:184:35: error: 'typeE' has not been declared
184 | static typeT func_te(typeT a, typeE b, int w){
| ^~~~~
main.cpp:187:12: error: 'typeE' does not name a type; did you mean 'typeT'?
187 | static typeE func_ee(typeE a, typeE b){
| ^~~~~
| typeT
main.cpp: In static member function 'static RsummodQ_RaffineQ<T, MOD>::typeT RsummodQ_RaffineQ<T, MOD>::func_te(typeT, int, int)':
main.cpp:185:43: error: invalid types 'int[int]' for array subscript
185 | return std::make_pair((a.first * b[0] + b[1] * (long long)w + a.second * b[2]) % MOD, a.second);
| ^
main.cpp:185:50: error: invalid types 'int[int]' for array subscript
185 | return std::make_pair((a.first * b[0] + b[1] * (long long)w + a.second * b[2]) % MOD, a.second);
| ^
main.cpp:185:83: error: invalid types 'int[int]' for array subscript
185 | return std::make_pair((a.first * b[0] + b[1] * (long long)w + a.second * b[2]) % MOD, a.second);
| ^
main.cpp: In instantiation of 'class segment_tree<RsummodQ_RaffineQ<long long int, 1000000007> >':
main.cpp:204:59: required from here
main.cpp:10:11: error: no type named 'typeE' in 'struct RsummodQ_RaffineQ<long long int, 1000000007>'
10 | using
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
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 = U::e_t){
_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";
}
};
template <typename T, long long MOD>
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((a.first * b[0] + b[1] * (long long)w + a.second * b[2]) % 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};
}
};
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
const long long mod = 1e9 + 7;
long long n, q, op, x, y, z;
std::cin >> n >> q;
std::vector<std::pair<long long, long long>> vec(n, {0, 1});
vec[0].second = 0;
for(int i = 2; i < n; i++) vec[i].second = (vec[i-1].second + vec[i-2].second) % mod;
segment_tree<RsummodQ_RaffineQ<long long, mod>> st(vec);
while(q--){
std::cin >> op >> x >> y >> z;
if(op == 0){
std::cout << (st.find(x, y + 1).first * z) % mod << "\n";
}
else if(op == 1){
st.apply(x, y + 1, {0, z, 0});
}
else if(op == 2){
st.apply(x, y + 1, {1, z, 0});
}
else if(op == 3){
st.apply(x, y + 1, {z, 0, 0});
}
else if(op == 4){
st.apply(x, y + 1, {1, 0, z});
}
}
}