This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
#include <cstdio>
#include <vector>
#include <climits>
using namespace std;
using ll = long long int;
template<typename Type>
struct SqrtDecomp {
int SIZE;
vector<Type> node, bucket, lazy, need_upd;
Type (*op1) (Type x, Type y, int sz);
Type (*op2) (Type x, Type y);
Type I_op1, I_op2;
SqrtDecomp( vector<Type> vec,
Type (*g_op1) (Type x, Type y, int sz),
Type (*g_op2) (Type x, Type y),
Type X_op1, Type X_op2) {
int N = vec.size();
SIZE = 1; while(SIZE * SIZE < N) SIZE++;
op1 = g_op1, op2 = g_op2;
I_op1 = X_op1, I_op2 = X_op2;
node.resize(SIZE*SIZE, I_op2);
bucket.resize(SIZE, I_op2);
lazy.resize(SIZE, I_op1);
need_upd.resize(SIZE, 0);
for(int i=0; i<SIZE; i++) {
Type rep_val = I_op2;
for(int j=0; j<SIZE && i*SIZE+j<N; j++) {
int idx = (i*SIZE + j);
node[idx] = vec[idx];
rep_val = op2(rep_val, node[idx]);
}
bucket[i] = rep_val;
}
}
void lazy_eval(int k) {
int l = SIZE*k, r = SIZE*(k+1);
if(need_upd[k]) {
Type seg_val = I_op2;
// 該当する下のノードをまず更新
for(int i=l; i<r; i++) {
node[i] = op1(node[i], lazy[k], 1);
seg_val = op2(seg_val, node[i]);
}
// 上のノードを更新
bucket[k] = seg_val;
}
lazy[k] = I_op1;
need_upd[k] = false;
}
void update(int l, int r, Type val) {
int lidx = l / SIZE, ridx = r / SIZE;
// 左端の更新
lazy_eval(lidx);
bucket[lidx] = I_op2;
for(int k=SIZE*lidx; k<SIZE*(lidx+1); k++) {
if(l <= k && k < r) node[k] = op1(node[k], val, 1);
bucket[lidx] = op2(bucket[lidx], node[k]);
}
if(lidx != ridx) {
// 真ん中 (lazy を更新)
for(int k=lidx+1; k<ridx; k++) {
lazy[k] = op1(lazy[k], val, 1);
need_upd[k] = true;
}
if(ridx != SIZE) {
lazy_eval(ridx);
bucket[ridx] = I_op2;
// 右端の更新
for(int k=SIZE*ridx; k<SIZE*(ridx+1); k++) {
if(k < r) node[k] = op1(node[k], val, 1);
bucket[ridx] = op2(bucket[ridx], node[k]);
}
}
}
}
Type query(int l, int r) {
int lidx = l / SIZE, ridx = r / SIZE;
Type ret = I_op2;
// 左端の取得
for(int k=l; k<min(r, SIZE*(lidx+1)); k++) {
lazy_eval(lidx);
ret = op2(ret, node[k]);
}
if(lidx != ridx) {
for(int k=lidx+1; k<ridx; k++) {
// 全体の値と lazy の値を考慮して値を計算
Type val = (need_upd[k] ? op1(bucket[k], lazy[k], SIZE) : bucket[k]);
ret = op2(ret, val);
}
for(int k=SIZE*ridx; k<r; k++) {
lazy_eval(ridx);
ret = op2(ret, node[k]);
}
}
return ret;
}
/*
void print_debug() {
printf("<< node >>\n");
printf("upper bucket:\n");
for(int i=0; i<SIZE; i++) {
int l = SIZE*i, r = SIZE*(i+1);
printf("[%6d, %6d) -> %lld\n", l, r, bucket[i]);
}
printf("lower bucket:\n");
for(int i=0; i<SIZE*SIZE; i++) {
printf("[%6d, %6d) -> %lld\n", i, i+1, node[i]);
}
printf("<< lazy >>\n");
printf("upper bucket:\n");
for(int i=0; i<SIZE; i++) {
int l = SIZE*i, r = SIZE*(i+1);
printf("[%6d, %6d) -> %lld\n", l, r, lazy[i]);
}
printf("\n");
}
*/
};
#line 1 "structure/strc_010_abst_sqrtdecomp.cpp"
#include <cstdio>
#include <vector>
#include <climits>
using namespace std;
using ll = long long int;
template<typename Type>
struct SqrtDecomp {
int SIZE;
vector<Type> node, bucket, lazy, need_upd;
Type (*op1) (Type x, Type y, int sz);
Type (*op2) (Type x, Type y);
Type I_op1, I_op2;
SqrtDecomp( vector<Type> vec,
Type (*g_op1) (Type x, Type y, int sz),
Type (*g_op2) (Type x, Type y),
Type X_op1, Type X_op2) {
int N = vec.size();
SIZE = 1; while(SIZE * SIZE < N) SIZE++;
op1 = g_op1, op2 = g_op2;
I_op1 = X_op1, I_op2 = X_op2;
node.resize(SIZE*SIZE, I_op2);
bucket.resize(SIZE, I_op2);
lazy.resize(SIZE, I_op1);
need_upd.resize(SIZE, 0);
for(int i=0; i<SIZE; i++) {
Type rep_val = I_op2;
for(int j=0; j<SIZE && i*SIZE+j<N; j++) {
int idx = (i*SIZE + j);
node[idx] = vec[idx];
rep_val = op2(rep_val, node[idx]);
}
bucket[i] = rep_val;
}
}
void lazy_eval(int k) {
int l = SIZE*k, r = SIZE*(k+1);
if(need_upd[k]) {
Type seg_val = I_op2;
// 該当する下のノードをまず更新
for(int i=l; i<r; i++) {
node[i] = op1(node[i], lazy[k], 1);
seg_val = op2(seg_val, node[i]);
}
// 上のノードを更新
bucket[k] = seg_val;
}
lazy[k] = I_op1;
need_upd[k] = false;
}
void update(int l, int r, Type val) {
int lidx = l / SIZE, ridx = r / SIZE;
// 左端の更新
lazy_eval(lidx);
bucket[lidx] = I_op2;
for(int k=SIZE*lidx; k<SIZE*(lidx+1); k++) {
if(l <= k && k < r) node[k] = op1(node[k], val, 1);
bucket[lidx] = op2(bucket[lidx], node[k]);
}
if(lidx != ridx) {
// 真ん中 (lazy を更新)
for(int k=lidx+1; k<ridx; k++) {
lazy[k] = op1(lazy[k], val, 1);
need_upd[k] = true;
}
if(ridx != SIZE) {
lazy_eval(ridx);
bucket[ridx] = I_op2;
// 右端の更新
for(int k=SIZE*ridx; k<SIZE*(ridx+1); k++) {
if(k < r) node[k] = op1(node[k], val, 1);
bucket[ridx] = op2(bucket[ridx], node[k]);
}
}
}
}
Type query(int l, int r) {
int lidx = l / SIZE, ridx = r / SIZE;
Type ret = I_op2;
// 左端の取得
for(int k=l; k<min(r, SIZE*(lidx+1)); k++) {
lazy_eval(lidx);
ret = op2(ret, node[k]);
}
if(lidx != ridx) {
for(int k=lidx+1; k<ridx; k++) {
// 全体の値と lazy の値を考慮して値を計算
Type val = (need_upd[k] ? op1(bucket[k], lazy[k], SIZE) : bucket[k]);
ret = op2(ret, val);
}
for(int k=SIZE*ridx; k<r; k++) {
lazy_eval(ridx);
ret = op2(ret, node[k]);
}
}
return ret;
}
/*
void print_debug() {
printf("<< node >>\n");
printf("upper bucket:\n");
for(int i=0; i<SIZE; i++) {
int l = SIZE*i, r = SIZE*(i+1);
printf("[%6d, %6d) -> %lld\n", l, r, bucket[i]);
}
printf("lower bucket:\n");
for(int i=0; i<SIZE*SIZE; i++) {
printf("[%6d, %6d) -> %lld\n", i, i+1, node[i]);
}
printf("<< lazy >>\n");
printf("upper bucket:\n");
for(int i=0; i<SIZE; i++) {
int l = SIZE*i, r = SIZE*(i+1);
printf("[%6d, %6d) -> %lld\n", l, r, lazy[i]);
}
printf("\n");
}
*/
};