The 2021 ICPC Asia Nanjing Regional Contest E.Paimon Segment Tree 区间合并线段树/维护矩阵乘法
题目大意
给定长度为的序列
,要求支持区间加操作,同时对操作记录历史版本,查询问区间
操作
中的每个数的平方之和。
题目思路
推了一会,发现线段树合并硬写很凌乱,然后队友告诉是线段树维护矩阵乘法,那么就考虑怎么维护:
设:
,区间长度
,区间和
,区间平方和
,区间历史平方和
考虑每次区间加,那么考虑各个数字的变化:
- 对于区间和,变化量就是
- 对于区间平方和:
那么就有:
把上面的式子整理一下,就可以用矩阵乘法维护,转移矩阵:
看了看题解,说“设置了一个让不需要任何矩乘优化就可勉强通过的时限”,说明有卡常?
但并没有卡到(
Code
#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 10, MOD = 1e9 + 7;
int a[N], ans[N];
namespace ffastIO {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (!isdigit(c))b ^= c == '-', c = fetch();
while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
return b ? a : -a;
}
}
using ffastIO::read;
struct Mat{
static const int M = 4;
int v[M][M];
Mat() { memset(v ,0 ,sizeof(v)); }
Mat(int k){
v[0][0] = v[1][1] = v[2][2] = v[3][3] = v[2][3] = 1;
v[0][1] = k;
v[0][2] = v[0][3] = k * k % MOD;
v[1][2] = v[1][3] = 2 * k % MOD;
v[1][0] = v[2][0] = v[2][1] = v[3][0] = v[3][1] = v[3][2] = 0;
}
void eye() { for(int i = 0; i < M; i++) for(int j = 0; j < M; j++) v[i][j] = (i == j); }
int * operator [] (int x) { return v[x]; }
const int *operator [] (int x) const { return v[x]; }
Mat operator * (const Mat& B) {
const Mat &A = *this;
Mat ret;
for(int k = 0; k < M; k++){
for(int i = 0; i < M; i++)
for(int j = 0; j < M; j++){
ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % MOD;
}
}
return ret;
}
Mat operator + (const Mat& B) {
const Mat &A = *this;
Mat ret;
for(int i = 0; i < M; i++)
for(int j = 0; j < M; j++)
ret[i][j] = (A[i][j] + B[i][j]) % MOD;
return ret;
}
Mat pow(int n) const {
Mat A = *this, ret; ret.eye();
for(; n; n >>= 1, A = A * A) if(n & 1) ret = ret * A;
return ret;
}
};
namespace SegTree{
#define ls rt << 1
#define rs rt << 1 | 1
#define lson ls, l,
#define rson rs, mid + 1,
struct Info{
int val[4];
Info () {}
Info (int x){ val[0] = 1, val[1] = x, val[2] = val[3] = x * x % MOD; }
Info operator+ (Info b){
Info res;
for(int i = 0; i < 4; i++){ res.val[i] = (val[i] + b.val[i]) % MOD; }
return res;
}
Info operator* (Mat b){
int res[4] = {0, 0, 0, 0};
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++) res[j] = (res[j] + val[i] * b[i][j]) % MOD;
}
for(int i = 0; i < 4; i++) val[i] = res[i];
return *this;
}
} tree[N << 2];
Mat lazy[N << 2];
inline void push_up(int rt){ tree[rt] = tree[ls] + tree[rs]; }
inline void push(int rt, Mat k){ tree[rt] = tree[rt] * k, lazy[rt] = lazy[rt] * k; }
inline void push_down(int rt){
push(ls, lazy[rt]), push(rs, lazy[rt]);
lazy[rt].eye();
}
void build(int rt, int l, int r){
lazy[rt].eye();
if(l == r) return (void)(tree[rt] = Info(a[l]));
int mid = l + r >> 1;
build(lson), build(rson);
push_up(rt);
}
void update(int rt, int l, int r, int L, int R, int val){
if(r < L || l > R || (l >= L && r <= R)) return push(rt, Mat((l >= L && r <= R) * val));
push_down(rt);
int mid = l + r >> 1;
update(lson, L, R, val), update(rson, L, R, val);
push_up(rt);
}
Info query(int rt, int l, int r, int L, int R){
if(l >= L && r <= R) return tree[rt];
push_down(rt);
int mid = l + r >> 1;
if(mid >= L && mid < R) return query(lson, L, R) + query(rson, L, R);
if(mid >= L) return query(lson, L, R);
if(mid < R) return query(rson, L, R);
return Info(1);
}
}
struct modify{ int l, r, val; }op[N];
struct query{
int op, id, x, l, r;
const bool operator< (const query &s) const { return x < s.x; }
}que[N];
#define SEGRG 1, 1,
inline void solve(){
int n = read(), m = read(), q = read();
for(int i = 1; i <= n; i++) a[i] = (read() + MOD) % MOD;
SegTree::build(1, 1, n);
for(int i = 1; i <= m; i++) op[i] = {read(), read(), (read() + MOD) % MOD};
for(int i = 1; i <= q; i++){
int l = read(), r = read(), x = read(), y = read();
que[i * 2 - 1] = query{-1, i, x - 1, l, r};
que[i * 2] = query{1, i, y, l, r};
}
sort(que + 1, que + 1 + 2 * q);
int now = 1; // while(now <= 2 * q && que[now].x == -1) now++;
for(; now <= 2 * q && que[now].x == -1; now++);
for(int i = 0; i <= m; i++){
if(i) SegTree::update(SEGRG, op[i].l, op[i].r, op[i].val);
for(; now <= 2 * q && que[now].x == i; now++){
ans[que[now].id] += que[now].op * SegTree::query(SEGRG, que[now].l, que[now].r).val[3] % MOD;
}
}
for(int i = 1; i <= q; i++) printf("%d\n", (ans[i] + MOD) % MOD);
}
signed main(){
solve();
return 0;
}