题目概述

Paimon Segment Tree

解题报告

首先肯定考虑离线，把询问 $[L,R],[x,y]$ 拆成 $([L,R],[0,y])-([L,R],[0,x-1])$ 。然后我们按顺序进行操作，需要维护一棵线段树，支持维护区间内 $0$ 到 $i$ 操作的前缀平方和。

记 $len$ 表示区间长度，$sum$ 表示区间和，$val$ 表示区间平方和，$pre$ 表示到目前为止的前缀区间平方和，然后我们考虑区间 $+k$ 操作：

$$ x^2\to(x+k)^2=x^2+2kx+k^2\\ len=len'\\ sum=sum'+k\cdot len\\ val=val'+2k\cdot sum'+k^2\cdot len\\ pre=pre'+val'+2k\cdot sum'+k^2\cdot len\\ $$

如果仅记录数值 $tag$ 我们不难发现没有办法进行标记合并，观察上面的式子发现这是一次线性变换，因此我们可以用矩阵来表示：

$$ \begin{bmatrix}len'&sum'&val'&pre'\end{bmatrix}\begin{bmatrix}1&k&k^2&k^2\\0&1&2k&2k\\0&0&1&1\\0&0&0&1\end{bmatrix}=\begin{bmatrix}len&sum&val&pre\end{bmatrix} $$

所以我们可以将这个矩阵记为 $tag$ ，这样就能够标记合并了。

需要注意这样常数很大，由于这个转移矩阵是上三角的，因此矩阵乘法时我们只需要枚举上三角，常数小很多。

实现时需要注意，为了对齐时间（求 $pre$ ），不仅需要对 $[L,R]$ 进行 $+k$ 操作，还需要对 $[1,L-1],[R+1,n]$ 进行 $+0$ 操作。

示例程序

#include<cstdio>
#include<cctype>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn=50000,maxt=maxn<<2,MOD=1e9+7;

int n,m,te,a[maxn+5],l[maxn+5],r[maxn+5],X[maxn+5];
struct giao {int l,r,id,f;};
vector<giao> e[maxn+5];
struct Matrix{
    int s[4][4];
    void zero() {for (int i=0;i<4;i++) for (int j=0;j<4;j++) s[i][j]=0;}
    void unit() {zero();for (int i=0;i<4;i++) s[i][i]=1;}
};
int M[maxt+5][4],cnt[maxt+5];Matrix tag[maxt+5],tem;
int ans[maxn+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
Matrix operator * (const Matrix &a,const Matrix &b){
    static Matrix c;c.zero();
    for (int i=0;i<4;i++)
        for (int j=i;j<4;j++)
            for (int k=i;k<=j;k++)
                c.s[i][j]=ADD(c.s[i][j],MUL(a.s[i][k],b.s[k][j]));
    return c;
}
void Make(int k){
    tem.unit();
    tem.s[0][1]=k;tem.s[0][2]=MUL(k,k);tem.s[0][3]=MUL(k,k);
    tem.s[1][2]=ADD(k,k);tem.s[1][3]=ADD(k,k);
    tem.s[2][3]=1;
}
void Mul(int *a,Matrix &A){
    static int b[4];
    b[0]=b[1]=b[2]=b[3]=0;
    for (int i=0;i<4;i++)
        for (int j=0;j<4;j++)
            b[i]=ADD(b[i],MUL(a[j],A.s[j][i]));
    a[0]=b[0];a[1]=b[1];a[2]=b[2];a[3]=b[3];
}
void Build(int L,int R,int p=1){
    M[p][0]=R-L+1;tag[p].unit();
    if (L==R) {M[p][1]=a[L];M[p][2]=MUL(a[L],a[L]);M[p][3]=M[p][2];return;}
    int mid=L+(R-L>>1);
    Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);
    for (int i=1;i<4;i++) M[p][i]=ADD(M[p<<1][i],M[p<<1|1][i]);
}
inline void Addtag(int p,Matrix &A) {Mul(M[p],A);tag[p]=tag[p]*A;cnt[p]++;}
void Pushdown(int p) {if (cnt[p]) Addtag(p<<1,tag[p]),Addtag(p<<1|1,tag[p]),cnt[p]=0,tag[p].unit();}
void Insert(int L,int R,int l=1,int r=n,int p=1){
    if (L==l && r==R) return Addtag(p,tem);
    int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Insert(L,R,l,mid,p<<1); else if (L>mid) Insert(L,R,mid+1,r,p<<1|1);
    else Insert(L,mid,l,mid,p<<1),Insert(mid+1,R,mid+1,r,p<<1|1);
    for (int i=1;i<4;i++) M[p][i]=ADD(M[p<<1][i],M[p<<1|1][i]);
}
int Ask(int L,int R,int l=1,int r=n,int p=1){
    if (L==l && r==R) return M[p][3];
    int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) return Ask(L,R,l,mid,p<<1); else if (L>mid) return Ask(L,R,mid+1,r,p<<1|1);
    else return ADD(Ask(L,mid,l,mid,p<<1),Ask(mid+1,R,mid+1,r,p<<1|1));
}
int main(){
    readi(n);readi(m);readi(te);
    for (int i=1;i<=n;i++) readi(a[i]),a[i]=ADD(a[i],MOD);
    for (int i=1;i<=m;i++) readi(l[i]),readi(r[i]),readi(X[i]),X[i]=ADD(X[i],MOD);
    for (int i=1,l,r,x,y;i<=te;i++){
        readi(l);readi(r);readi(x);readi(y);
        if (x) e[x-1].push_back((giao){l,r,i,-1});
        e[y].push_back((giao){l,r,i,1});
    }
    Build(1,n);
    for (auto x:e[0]){
        int now=Ask(x.l,x.r);
//        printf("%d:%d %d %d\n",0,x.l,x.r,now);
        ans[x.id]=ADD(ans[x.id],x.f>0?now:MOD-now);
    }
    for (int i=1;i<=m;i++){
        if (l[i]>1) Make(0),Insert(1,l[i]-1);
        Make(X[i]);Insert(l[i],r[i]);
        if (r[i]<n) Make(0),Insert(r[i]+1,n);
        for (auto x:e[i]){
            int now=Ask(x.l,x.r);
//            printf("%d:%d %d %d\n",i,x.l,x.r,now);
            ans[x.id]=ADD(ans[x.id],x.f>0?now:MOD-now);
        }
    }
    for (int i=1;i<=te;i++) printf("%d\n",ans[i]);
    return 0;
}