关于循环展开优化
- 板块P7453 [THUSCH2017] 大魔法师
- 楼主_ChongYun_
- 当前回复2
- 已保存回复2
- 发布时间2025/2/7 11:16
- 上次更新2025/2/7 14:28:42
查看原帖
被骇客银狼阻止的越权访问保存失败
关于循环展开优化
为什么循环展开优化对此题这么有用（
无循环展开优化45pts：
/* ChongYun */
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*f;
}
const int mod=998244353;
int n,q;
struct Matrix{
int A[4][4];
void clear(){ memset(A,0,sizeof(A)); }
void init(){ clear(),A[0][0]=A[1][1]=A[2][2]=A[3][3]=1; }
Matrix operator + (const Matrix &qwq)const{
Matrix now; now.clear();
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
now.A[i][j]=(A[i][j]+qwq.A[i][j]%mod)%mod;
}
}
return now;
}
Matrix operator * (const Matrix &qwq)const{
Matrix now; now.clear();
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
now.A[i][j]=(now.A[i][j]+1ll*A[i][k]*qwq.A[k][j]%mod)%mod;
}
}
}
return now;
}
}Rhy[250005],upd[6];
struct SegTree{
int l,r;
Matrix sum;
}tree[1000005];
Matrix lazy[1000005];
void pushup(int p){
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
return ;
}
void pushdown(int p){
tree[p<<1].sum=tree[p<<1].sum*lazy[p];
tree[p<<1|1].sum=tree[p<<1|1].sum*lazy[p];
lazy[p<<1]=lazy[p<<1]*lazy[p];
lazy[p<<1|1]=lazy[p<<1|1]*lazy[p];
lazy[p].init();
return ;
}
void build(int p,int l,int r){
lazy[p].init();
tree[p].l=l,tree[p].r=r;
if(l==r){
tree[p].sum=Rhy[l];
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
return ;
}
void update(int p,int l,int r,Matrix val){
if(l<=tree[p].l&&tree[p].r<=r){
tree[p].sum=tree[p].sum*val;
lazy[p]=lazy[p]*val;
return ;
}
pushdown(p);
int mid=(tree[p].l+tree[p].r)>>1;
if(l<=mid) update(p<<1,l,r,val);
if(r>mid) update(p<<1|1,l,r,val);
pushup(p);
return ;
}
Matrix query(int p,int l,int r){
if(l<=tree[p].l&&tree[p].r<=r) return tree[p].sum;
pushdown(p);
Matrix qans; qans.clear();
int mid=(tree[p].l+tree[p].r)>>1;
if(l<=mid) qans=qans+query(p<<1,l,r);
if(r>mid) qans=qans+query(p<<1|1,l,r);
return qans;
}
signed main(){
n=read();
upd[0].init(),upd[1].init(),upd[2].init();
upd[0].A[1][0]=upd[1].A[2][1]=upd[2].A[0][2]=1;
upd[3].init(),upd[4].init(),upd[5].init();
upd[5].A[2][2]=0;
for(int i=1;i<=n;i++) Rhy[i].clear();
for(int i=1;i<=n;i++){
Rhy[i].A[0][0]=read();
Rhy[i].A[0][1]=read();
Rhy[i].A[0][2]=read();
Rhy[i].A[0][3]=1;
}
build(1,1,n);
q=read();
while(q--){
int op=read();
int l=read(),r=read();
if(op<=3) update(1,l,r,upd[op-1]);
else if(op<=6){
upd[3].A[3][0]=upd[4].A[1][1]=upd[5].A[3][2]=read();
update(1,l,r,upd[op-1]);
}else{
Matrix ans=query(1,l,r);
printf("%d %d %d\n",ans.A[0][0],ans.A[0][1],ans.A[0][2]);
}
}
return 0;
}
一层循环展开优化60pts:
/* ChongYun */
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*f;
}
const int mod=998244353;
int n,q;
struct Matrix{
int A[4][4];
void clear(){ memset(A,0,sizeof(A)); }
void init(){ clear(),A[0][0]=A[1][1]=A[2][2]=A[3][3]=1; }
Matrix operator + (const Matrix &qwq)const{
Matrix now; now.clear();
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
now.A[i][j]=(A[i][j]+1ll*qwq.A[i][j]%mod)%mod;
}
}
return now;
}
Matrix operator * (const Matrix &qwq)const{
Matrix now; now.clear();
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
now.A[i][j]=1ll*(now.A[i][j]+1ll*A[i][0]*qwq.A[0][j]%mod)%mod;
now.A[i][j]=1ll*(now.A[i][j]+1ll*A[i][1]*qwq.A[1][j]%mod)%mod;
now.A[i][j]=1ll*(now.A[i][j]+1ll*A[i][2]*qwq.A[2][j]%mod)%mod;
now.A[i][j]=1ll*(now.A[i][j]+1ll*A[i][3]*qwq.A[3][j]%mod)%mod;
}
}
return now;
}
}Rhy[250005],upd[6];
struct SegTree{
int l,r;
Matrix sum;
}tree[1000005];
Matrix lazy[1000005];
void pushup(int p){
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
return ;
}
void pushdown(int p){
tree[p<<1].sum=tree[p<<1].sum*lazy[p];
tree[p<<1|1].sum=tree[p<<1|1].sum*lazy[p];
lazy[p<<1]=lazy[p<<1]*lazy[p];
lazy[p<<1|1]=lazy[p<<1|1]*lazy[p];
lazy[p].init();
return ;
}
void build(int p,int l,int r){
lazy[p].init();
tree[p].l=l,tree[p].r=r;
if(l==r){
tree[p].sum=Rhy[l];
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
return ;
}
void update(int p,int l,int r,Matrix val){
if(l<=tree[p].l&&tree[p].r<=r){
tree[p].sum=tree[p].sum*val;
lazy[p]=lazy[p]*val;
return ;
}
pushdown(p);
int mid=(tree[p].l+tree[p].r)>>1;
if(l<=mid) update(p<<1,l,r,val);
if(r>mid) update(p<<1|1,l,r,val);
pushup(p);
return ;
}
Matrix query(int p,int l,int r){
if(l<=tree[p].l&&tree[p].r<=r) return tree[p].sum;
pushdown(p);
Matrix qans; qans.clear();
int mid=(tree[p].l+tree[p].r)>>1;
if(l<=mid) qans=qans+query(p<<1,l,r);
if(r>mid) qans=qans+query(p<<1|1,l,r);
return qans;
}
signed main(){
n=read();
upd[0].init(),upd[1].init(),upd[2].init();
upd[0].A[1][0]=upd[1].A[2][1]=upd[2].A[0][2]=1;
upd[3].init(),upd[4].init(),upd[5].init();
upd[5].A[2][2]=0;
for(int i=1;i<=n;i++) Rhy[i].clear();
for(int i=1;i<=n;i++){
Rhy[i].A[0][0]=read();
Rhy[i].A[0][1]=read();
Rhy[i].A[0][2]=read();
Rhy[i].A[0][3]=1;
}
build(1,1,n);
q=read();
while(q--){
int op=read();
int l=read(),r=read();
if(op<=3) update(1,l,r,upd[op-1]);
else if(op<=6){
upd[3].A[3][0]=upd[4].A[1][1]=upd[5].A[3][2]=read();
update(1,l,r,upd[op-1]);
}else{
Matrix ans=query(1,l,r);
printf("%d %d %d\n",ans.A[0][0],ans.A[0][1],ans.A[0][2]);
}
}
return 0;
}
双层循环展开优化[70,80]pts:
/* ChongYun */
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*f;
}
const int mod=998244353;
int n,q;
struct Matrix{
int A[4][4];
void clear(){ memset(A,0,sizeof(A)); }
void init(){ clear(),A[0][0]=A[1][1]=A[2][2]=A[3][3]=1; }
Matrix operator + (const Matrix &qwq)const{
Matrix now; now.clear();
now.A[0][0]=(A[0][0]+qwq.A[0][0]%mod)%mod;
now.A[0][1]=(A[0][1]+qwq.A[0][1]%mod)%mod;
now.A[0][2]=(A[0][2]+qwq.A[0][2]%mod)%mod;
now.A[0][3]=(A[0][3]+qwq.A[0][3]%mod)%mod;
now.A[1][0]=(A[1][0]+qwq.A[1][0]%mod)%mod;
now.A[1][1]=(A[1][1]+qwq.A[1][1]%mod)%mod;
now.A[1][2]=(A[1][2]+qwq.A[1][2]%mod)%mod;
now.A[1][3]=(A[1][3]+qwq.A[1][3]%mod)%mod;
now.A[2][0]=(A[2][0]+qwq.A[2][0]%mod)%mod;
now.A[2][1]=(A[2][1]+qwq.A[2][1]%mod)%mod;
now.A[2][2]=(A[2][2]+qwq.A[2][2]%mod)%mod;
now.A[2][3]=(A[2][3]+qwq.A[2][3]%mod)%mod;
now.A[3][0]=(A[3][0]+qwq.A[3][0]%mod)%mod;
now.A[3][1]=(A[3][1]+qwq.A[3][1]%mod)%mod;
now.A[3][2]=(A[3][2]+qwq.A[3][2]%mod)%mod;
now.A[3][3]=(A[3][3]+qwq.A[3][3]%mod)%mod;
return now;
}
Matrix operator * (const Matrix &qwq)const{
Matrix now; now.clear();
for(int i=0;i<4;i++){
now.A[i][0]=(now.A[i][0]+1ll*A[i][0]*qwq.A[0][0]%mod)%mod;
now.A[i][0]=(now.A[i][0]+1ll*A[i][1]*qwq.A[1][0]%mod)%mod;
now.A[i][0]=(now.A[i][0]+1ll*A[i][2]*qwq.A[2][0]%mod)%mod;
now.A[i][0]=(now.A[i][0]+1ll*A[i][3]*qwq.A[3][0]%mod)%mod;
now.A[i][1]=(now.A[i][1]+1ll*A[i][0]*qwq.A[0][1]%mod)%mod;
now.A[i][1]=(now.A[i][1]+1ll*A[i][1]*qwq.A[1][1]%mod)%mod;
now.A[i][1]=(now.A[i][1]+1ll*A[i][2]*qwq.A[2][1]%mod)%mod;
now.A[i][1]=(now.A[i][1]+1ll*A[i][3]*qwq.A[3][1]%mod)%mod;
now.A[i][2]=(now.A[i][2]+1ll*A[i][0]*qwq.A[0][2]%mod)%mod;
now.A[i][2]=(now.A[i][2]+1ll*A[i][1]*qwq.A[1][2]%mod)%mod;
now.A[i][2]=(now.A[i][2]+1ll*A[i][2]*qwq.A[2][2]%mod)%mod;
now.A[i][2]=(now.A[i][2]+1ll*A[i][3]*qwq.A[3][2]%mod)%mod;
now.A[i][3]=(now.A[i][3]+1ll*A[i][0]*qwq.A[0][3]%mod)%mod;
now.A[i][3]=(now.A[i][3]+1ll*A[i][1]*qwq.A[1][3]%mod)%mod;
now.A[i][3]=(now.A[i][3]+1ll*A[i][2]*qwq.A[2][3]%mod)%mod;
now.A[i][3]=(now.A[i][3]+1ll*A[i][3]*qwq.A[3][3]%mod)%mod;
}
return now;
}
}Rhy[250001],upd[6];
struct SegTree{
int l,r;
Matrix sum;
}tree[1000001];
Matrix lazy[1000001];
void pushup(int p){
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
return ;
}
void pushdown(int p){
tree[p<<1].sum=tree[p<<1].sum*lazy[p];
tree[p<<1|1].sum=tree[p<<1|1].sum*lazy[p];
lazy[p<<1]=lazy[p<<1]*lazy[p];
lazy[p<<1|1]=lazy[p<<1|1]*lazy[p];
lazy[p].init();
return ;
}
void build(int p,int l,int r){
lazy[p].init();
tree[p].l=l,tree[p].r=r;
if(l==r){
tree[p].sum=Rhy[l];
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
return ;
}
void update(int p,int l,int r,Matrix val){
if(l<=tree[p].l&&tree[p].r<=r){
tree[p].sum=tree[p].sum*val;
lazy[p]=lazy[p]*val;
return ;
}
pushdown(p);
int mid=(tree[p].l+tree[p].r)>>1;
if(l<=mid) update(p<<1,l,r,val);
if(r>mid) update(p<<1|1,l,r,val);
pushup(p);
return ;
}
Matrix query(int p,int l,int r){
if(l<=tree[p].l&&tree[p].r<=r) return tree[p].sum;
pushdown(p);
Matrix qans; qans.clear();
int mid=(tree[p].l+tree[p].r)>>1;
if(l<=mid) qans=qans+query(p<<1,l,r);
if(r>mid) qans=qans+query(p<<1|1,l,r);
return qans;
}
signed main(){
n=read();
upd[0].init(),upd[1].init(),upd[2].init();
upd[0].A[1][0]=upd[1].A[2][1]=upd[2].A[0][2]=1;
upd[3].init(),upd[4].init(),upd[5].init();
upd[5].A[2][2]=0;
for(int i=1;i<=n;i++) Rhy[i].clear();
for(int i=1;i<=n;i++){
Rhy[i].A[0][0]=read();
Rhy[i].A[0][1]=read();
Rhy[i].A[0][2]=read();
Rhy[i].A[0][3]=1;
}
build(1,1,n);
q=read();
while(q--){
int op=read();
int l=read(),r=read();
if(op<=3) update(1,l,r,upd[op-1]);
else if(op<=6){
upd[3].A[3][0]=upd[4].A[1][1]=upd[5].A[3][2]=read();
update(1,l,r,upd[op-1]);
}else{
Matrix ans=query(1,l,r);
printf("%d %d %d\n",ans.A[0][0],ans.A[0][1],ans.A[0][2]);
}
}
return 0;
}
三层循环展开优化100pts：
/* ChongYun */
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*f;
}
const int mod=998244353;
int n,q;
struct Matrix{
int A[4][4];
void clear(){ memset(A,0,sizeof(A)); }
void init(){ clear(),A[0][0]=A[1][1]=A[2][2]=A[3][3]=1; }
Matrix operator + (const Matrix &qwq)const{
Matrix now; now.clear();
now.A[0][0]=(A[0][0]+qwq.A[0][0]%mod)%mod;
now.A[0][1]=(A[0][1]+qwq.A[0][1]%mod)%mod;
now.A[0][2]=(A[0][2]+qwq.A[0][2]%mod)%mod;
now.A[0][3]=(A[0][3]+qwq.A[0][3]%mod)%mod;
now.A[1][0]=(A[1][0]+qwq.A[1][0]%mod)%mod;
now.A[1][1]=(A[1][1]+qwq.A[1][1]%mod)%mod;
now.A[1][2]=(A[1][2]+qwq.A[1][2]%mod)%mod;
now.A[1][3]=(A[1][3]+qwq.A[1][3]%mod)%mod;
now.A[2][0]=(A[2][0]+qwq.A[2][0]%mod)%mod;
now.A[2][1]=(A[2][1]+qwq.A[2][1]%mod)%mod;
now.A[2][2]=(A[2][2]+qwq.A[2][2]%mod)%mod;
now.A[2][3]=(A[2][3]+qwq.A[2][3]%mod)%mod;
now.A[3][0]=(A[3][0]+qwq.A[3][0]%mod)%mod;
now.A[3][1]=(A[3][1]+qwq.A[3][1]%mod)%mod;
now.A[3][2]=(A[3][2]+qwq.A[3][2]%mod)%mod;
now.A[3][3]=(A[3][3]+qwq.A[3][3]%mod)%mod;
return now;
}
Matrix operator * (const Matrix &qwq)const{
Matrix now; now.clear();
now.A[0][0]=(now.A[0][0]+1ll*A[0][0]*qwq.A[0][0]%mod)%mod;
now.A[0][0]=(now.A[0][0]+1ll*A[0][1]*qwq.A[1][0]%mod)%mod;
now.A[0][0]=(now.A[0][0]+1ll*A[0][2]*qwq.A[2][0]%mod)%mod;
now.A[0][0]=(now.A[0][0]+1ll*A[0][3]*qwq.A[3][0]%mod)%mod;
now.A[0][1]=(now.A[0][1]+1ll*A[0][0]*qwq.A[0][1]%mod)%mod;
now.A[0][1]=(now.A[0][1]+1ll*A[0][1]*qwq.A[1][1]%mod)%mod;
now.A[0][1]=(now.A[0][1]+1ll*A[0][2]*qwq.A[2][1]%mod)%mod;
now.A[0][1]=(now.A[0][1]+1ll*A[0][3]*qwq.A[3][1]%mod)%mod;
now.A[0][2]=(now.A[0][2]+1ll*A[0][0]*qwq.A[0][2]%mod)%mod;
now.A[0][2]=(now.A[0][2]+1ll*A[0][1]*qwq.A[1][2]%mod)%mod;
now.A[0][2]=(now.A[0][2]+1ll*A[0][2]*qwq.A[2][2]%mod)%mod;
now.A[0][2]=(now.A[0][2]+1ll*A[0][3]*qwq.A[3][2]%mod)%mod;
now.A[0][3]=(now.A[0][3]+1ll*A[0][0]*qwq.A[0][3]%mod)%mod;
now.A[0][3]=(now.A[0][3]+1ll*A[0][1]*qwq.A[1][3]%mod)%mod;
now.A[0][3]=(now.A[0][3]+1ll*A[0][2]*qwq.A[2][3]%mod)%mod;
now.A[0][3]=(now.A[0][3]+1ll*A[0][3]*qwq.A[3][3]%mod)%mod;
now.A[1][0]=(now.A[1][0]+1ll*A[1][0]*qwq.A[0][0]%mod)%mod;
now.A[1][0]=(now.A[1][0]+1ll*A[1][1]*qwq.A[1][0]%mod)%mod;
now.A[1][0]=(now.A[1][0]+1ll*A[1][2]*qwq.A[2][0]%mod)%mod;
now.A[1][0]=(now.A[1][0]+1ll*A[1][3]*qwq.A[3][0]%mod)%mod;
now.A[1][1]=(now.A[1][1]+1ll*A[1][0]*qwq.A[0][1]%mod)%mod;
now.A[1][1]=(now.A[1][1]+1ll*A[1][1]*qwq.A[1][1]%mod)%mod;
now.A[1][1]=(now.A[1][1]+1ll*A[1][2]*qwq.A[2][1]%mod)%mod;
now.A[1][1]=(now.A[1][1]+1ll*A[1][3]*qwq.A[3][1]%mod)%mod;
now.A[1][2]=(now.A[1][2]+1ll*A[1][0]*qwq.A[0][2]%mod)%mod;
now.A[1][2]=(now.A[1][2]+1ll*A[1][1]*qwq.A[1][2]%mod)%mod;
now.A[1][2]=(now.A[1][2]+1ll*A[1][2]*qwq.A[2][2]%mod)%mod;
now.A[1][2]=(now.A[1][2]+1ll*A[1][3]*qwq.A[3][2]%mod)%mod;
now.A[1][3]=(now.A[1][3]+1ll*A[1][0]*qwq.A[0][3]%mod)%mod;
now.A[1][3]=(now.A[1][3]+1ll*A[1][1]*qwq.A[1][3]%mod)%mod;
now.A[1][3]=(now.A[1][3]+1ll*A[1][2]*qwq.A[2][3]%mod)%mod;
now.A[1][3]=(now.A[1][3]+1ll*A[1][3]*qwq.A[3][3]%mod)%mod;
now.A[2][0]=(now.A[2][0]+1ll*A[2][0]*qwq.A[0][0]%mod)%mod;
now.A[2][0]=(now.A[2][0]+1ll*A[2][1]*qwq.A[1][0]%mod)%mod;
now.A[2][0]=(now.A[2][0]+1ll*A[2][2]*qwq.A[2][0]%mod)%mod;
now.A[2][0]=(now.A[2][0]+1ll*A[2][3]*qwq.A[3][0]%mod)%mod;
now.A[2][1]=(now.A[2][1]+1ll*A[2][0]*qwq.A[0][1]%mod)%mod;
now.A[2][1]=(now.A[2][1]+1ll*A[2][1]*qwq.A[1][1]%mod)%mod;
now.A[2][1]=(now.A[2][1]+1ll*A[2][2]*qwq.A[2][1]%mod)%mod;
now.A[2][1]=(now.A[2][1]+1ll*A[2][3]*qwq.A[3][1]%mod)%mod;
now.A[2][2]=(now.A[2][2]+1ll*A[2][0]*qwq.A[0][2]%mod)%mod;
now.A[2][2]=(now.A[2][2]+1ll*A[2][1]*qwq.A[1][2]%mod)%mod;
now.A[2][2]=(now.A[2][2]+1ll*A[2][2]*qwq.A[2][2]%mod)%mod;
now.A[2][2]=(now.A[2][2]+1ll*A[2][3]*qwq.A[3][2]%mod)%mod;
now.A[2][3]=(now.A[2][3]+1ll*A[2][0]*qwq.A[0][3]%mod)%mod;
now.A[2][3]=(now.A[2][3]+1ll*A[2][1]*qwq.A[1][3]%mod)%mod;
now.A[2][3]=(now.A[2][3]+1ll*A[2][2]*qwq.A[2][3]%mod)%mod;
now.A[2][3]=(now.A[2][3]+1ll*A[2][3]*qwq.A[3][3]%mod)%mod;
now.A[3][0]=(now.A[3][0]+1ll*A[3][0]*qwq.A[0][0]%mod)%mod;
now.A[3][0]=(now.A[3][0]+1ll*A[3][1]*qwq.A[1][0]%mod)%mod;
now.A[3][0]=(now.A[3][0]+1ll*A[3][2]*qwq.A[2][0]%mod)%mod;
now.A[3][0]=(now.A[3][0]+1ll*A[3][3]*qwq.A[3][0]%mod)%mod;
now.A[3][1]=(now.A[3][1]+1ll*A[3][0]*qwq.A[0][1]%mod)%mod;
now.A[3][1]=(now.A[3][1]+1ll*A[3][1]*qwq.A[1][1]%mod)%mod;
now.A[3][1]=(now.A[3][1]+1ll*A[3][2]*qwq.A[2][1]%mod)%mod;
now.A[3][1]=(now.A[3][1]+1ll*A[3][3]*qwq.A[3][1]%mod)%mod;
now.A[3][2]=(now.A[3][2]+1ll*A[3][0]*qwq.A[0][2]%mod)%mod;
now.A[3][2]=(now.A[3][2]+1ll*A[3][1]*qwq.A[1][2]%mod)%mod;
now.A[3][2]=(now.A[3][2]+1ll*A[3][2]*qwq.A[2][2]%mod)%mod;
now.A[3][2]=(now.A[3][2]+1ll*A[3][3]*qwq.A[3][2]%mod)%mod;
now.A[3][3]=(now.A[3][3]+1ll*A[3][0]*qwq.A[0][3]%mod)%mod;
now.A[3][3]=(now.A[3][3]+1ll*A[3][1]*qwq.A[1][3]%mod)%mod;
now.A[3][3]=(now.A[3][3]+1ll*A[3][2]*qwq.A[2][3]%mod)%mod;
now.A[3][3]=(now.A[3][3]+1ll*A[3][3]*qwq.A[3][3]%mod)%mod;
return now;
}
}Rhy[250001],upd[6];
struct SegTree{
int l,r;
Matrix sum;
}tree[1000001];
Matrix lazy[1000001];
void pushup(int p){
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
return ;
}
void pushdown(int p){
tree[p<<1].sum=tree[p<<1].sum*lazy[p];
tree[p<<1|1].sum=tree[p<<1|1].sum*lazy[p];
lazy[p<<1]=lazy[p<<1]*lazy[p];
lazy[p<<1|1]=lazy[p<<1|1]*lazy[p];
lazy[p].init();
return ;
}
void build(int p,int l,int r){
lazy[p].init();
tree[p].l=l,tree[p].r=r;
if(l==r){
tree[p].sum=Rhy[l];
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
return ;
}
void update(int p,int l,int r,Matrix val){
if(l<=tree[p].l&&tree[p].r<=r){
tree[p].sum=tree[p].sum*val;
lazy[p]=lazy[p]*val;
return ;
}
pushdown(p);
int mid=(tree[p].l+tree[p].r)>>1;
if(l<=mid) update(p<<1,l,r,val);
if(r>mid) update(p<<1|1,l,r,val);
pushup(p);
return ;
}
Matrix query(int p,int l,int r){
if(l<=tree[p].l&&tree[p].r<=r) return tree[p].sum;
pushdown(p);
Matrix qans; qans.clear();
int mid=(tree[p].l+tree[p].r)>>1;
if(l<=mid) qans=qans+query(p<<1,l,r);
if(r>mid) qans=qans+query(p<<1|1,l,r);
return qans;
}
signed main(){
n=read();
upd[0].init(),upd[1].init(),upd[2].init();
upd[0].A[1][0]=upd[1].A[2][1]=upd[2].A[0][2]=1;
upd[3].init(),upd[4].init(),upd[5].init();
upd[5].A[2][2]=0;
for(int i=1;i<=n;i++) Rhy[i].clear();
for(int i=1;i<=n;i++){
Rhy[i].A[0][0]=read();
Rhy[i].A[0][1]=read();
Rhy[i].A[0][2]=read();
Rhy[i].A[0][3]=1;
}
build(1,1,n);
q=read();
while(q--){
int op=read();
int l=read(),r=read();
if(op<=3) update(1,l,r,upd[op-1]);
else if(op<=6){
upd[3].A[3][0]=upd[4].A[1][1]=upd[5].A[3][2]=read();
update(1,l,r,upd[op-1]);
}else{
Matrix ans=query(1,l,r);
printf("%d %d %d\n",ans.A[0][0],ans.A[0][1],ans.A[0][2]);
}
}
return 0;
}
加载中...