区间历史版本和(矩阵板子)
cpp
struct Matrix{
int x00,x02,x03,x11,x12,x13,x22,x23,x33,x40,x41,x42,x43,x44;
};
struct Vec{
int x00,x01,x02,x03,x04;
};
Matrix operator*(const Matrix &a,const Matrix &b){
Matrix res;
res.x00=a.x00*b.x00;
res.x02=a.x00*b.x02+a.x02*b.x22;
res.x03=a.x00*b.x03+a.x02*b.x23+a.x03*b.x33;
res.x11=a.x11*b.x11;
res.x12=a.x11*b.x12+a.x12*b.x22;
res.x13=a.x11*b.x13+a.x12*b.x23+a.x13*b.x33;
res.x22=a.x22*b.x22;
res.x23=a.x22*b.x23+a.x23*b.x33;
res.x33=a.x33*b.x33;
res.x40=a.x40*b.x00+a.x44*b.x40;
res.x41=a.x41*b.x11+a.x44*b.x41;
res.x42=a.x40*b.x02+a.x41*b.x12+a.x42*b.x22+a.x44*b.x42;
res.x43=a.x40*b.x03+a.x41*b.x13+a.x42*b.x23+a.x43*b.x33+a.x44*b.x43;
res.x44=a.x44*b.x44;
return res;
}
Vec operator * (const Vec &a,const Matrix &b){
Vec res;
res.x00=a.x00*b.x00+a.x04*b.x40;
res.x01=a.x01*b.x11+a.x04*b.x41;
res.x02=a.x00*b.x02+a.x01*b.x12+a.x02*b.x22+a.x04*b.x42;
res.x03=a.x00*b.x03+a.x01*b.x13+a.x02*b.x23+a.x03*b.x33+a.x04*b.x43;
res.x04=a.x04*b.x44;
return res;
}
Vec operator +(const Vec &a,const Vec &b){
return {
a.x00+b.x00,
a.x01+b.x01,
a.x02+b.x02,
a.x03+b.x03,
a.x04+b.x04
};
}
Matrix I={1,0,0,1,0,0,1,0,1,0,0,0,0,1};
Matrix C={1,0,0,1,0,0,1,1,1,0,0,0,0,1};
Matrix getA(int k){
return Matrix{1,0,0,1,k,0,1,0,1,k,0,0,0,1};
}
Matrix getB(int k){
return Matrix{1,k,0,1,0,0,1,0,1,0,k,0,0,1};
}
vector<int> a,b;
struct SegmentTree{
struct Node{
Vec v;
Matrix tag=I;
bool lazy=0;
};
vector<Node> t;
void init(int n){
t=vector<Node>(n<<2);
build(1,1,n);
}
void pushup(int p){
t[p].v=t[p<<1].v+t[p<<1|1].v;
}
void pushtag(int p,const Matrix &m){
t[p].v=t[p].v*m;
t[p].tag=t[p].tag*m;
t[p].lazy=1;
}
void pushdown(int p){
if(t[p].lazy){
pushtag(p<<1,t[p].tag);
pushtag(p<<1|1,t[p].tag);
t[p].lazy=0;
t[p].tag=I;
}
}
void build(int p,int l,int r){
if(l==r){
t[p].v={a[l],b[l],a[l]*b[l],0,1};
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void modify(int p,int l,int r,int ql,int qr,const Matrix &x){
if(ql<=l&&r<=qr){
pushtag(p,x);
return;
}
pushdown(p);
int mid=l+r>>1;
if(ql<=mid)modify(p<<1,l,mid,ql,qr,x);
if(qr>mid)modify(p<<1|1,mid+1,r,ql,qr,x);
pushup(p);
}
int query(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return t[p].v.x03;
pushdown(p);
int res=0,mid=l+r>>1;
if(ql<=mid)res+=query(p<<1,l,mid,ql,qr);
if(qr>mid)res+=query(p<<1|1,mid+1,r,ql,qr);
return res;
}
} t;
void solve(){
int n,m;
cin>>m>>n;
vector<int> sta(n+1),stb(n+1);
a.assign(n+1,0);
b.assign(n+1,0);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
t.init(n);
cin>>m;
vector<PII> Que[n+1];
for(int i=0;i<m;i++){
int l,r;
cin>>l>>r;
Que[r].emplace_back(l,i);
}
vector<int> ans(m);
int at=0,bt=0;
for(int i=1;i<=n;i++){
while(at&&a[sta[at]]<a[i]){
t.modify(1,1,n,sta[at-1]+1,sta[at],getA(a[i]-a[sta[at]]));
--at;
}sta[++at]=i;
while(bt&&b[stb[bt]]<b[i]){
t.modify(1,1,n,stb[bt-1]+1,stb[bt],getB(b[i]-b[stb[bt]]));
--bt;
}stb[++bt]=i;
t.modify(1,1,n,1,i,C);
for(auto [l,id]:Que[i]){
ans[id]=t.query(1,1,n,l,i);
}
}
for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
}打表代码
cpp
void solve(){
vector<vector<int>> f={
{1,0,1,0,0},
{0,1,1,0,0},
{0,0,1,1,0},
{0,0,0,1,0},
{1,1,0,0,1}
};
const int n=f.size();
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)f[i][j]|=f[i][k]&f[k][j];
}
}
string s="int ";
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(f[i][j])s+="x"+to_string(i)+to_string(j)+",";
}
}
s.pop_back();
s+=";\n";
s+="\n\nMatrix * Matrix:\n";
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(!f[i][j])continue;
s+="res.x"+to_string(i)+to_string(j)+"=";
for(int k=0;k<n;k++){
if(f[i][k]&f[k][j])s+="a.x"+to_string(i)+to_string(k)+"*b.x"+to_string(k)+to_string(j)+"+";
}
s.pop_back();
s+=";\n";
}
}
s+="\n\nVec * Matrix:\n";
for(int i=0;i<n;i++){
s+="res.x0"+to_string(i)+"=";
for(int j=0;j<n;j++){
if(f[j][i]){
s+="a.x0"+to_string(j)+"*b.x"+to_string(j)+to_string(i)+"+";
}
}
s.pop_back();
s+=";\n";
}
s.pop_back();
cout<<s;
}