区间加区间历史版本和

fangzichang · 2024-11-09 16:02:22 · 算法·理论

众所周知，区间加区间历史版本和可以用线段树维护矩阵乘法做。
只需要用一个 1\times 3 的向量存下区间和、区间长度、区间历史和，就可以转移。

为啥我喜欢用行向量。好像是今年六月份最后推了一次然后一直复制粘贴的。
然后你学会了，去写一个什么 10^6 线段树，写完发现它好像没跑出来。
过一会跑出来了。

Process exited after 41.56 seconds with return value 0 (3.925e+04 ms cpu time, 430100 KB mem used).

好吧。你发现你没开 O2。

Process exited after 28.61 seconds with return value 0 (2.644e+04 ms cpu time, 430128 KB mem used).

然后卡常。critnos 老师告诉我说，只要你愿意卡，它总是能过的。
所以把有用的转移打表打出来展开。
具体地，你只需要写个程序枚举所有转移打出来，并且把加上零的情况去掉，然后把没用的取模去掉，就好了。

    J operator*(const J&b)const{
        J res(2,n);
//      for(int i=0;i<n;i++)
//          for(int j=0;j<b.m;j++)
//              for(int k=0;k<m;k++)
//                  res[i][j]=(res[i][j]+a[i][k]*1ll*b.a[k][j]%mod)%mod;
        res[0][0]=(a[0][0]*1ll*b.a[0][0]%mod+a[0][1]*1ll*b.a[1][0]%mod)%mod;
        res[0][1]=a[0][1]*1ll*b.a[1][1]%mod;
        res[0][2]=((a[0][0]*1ll*b.a[0][2]%mod+a[0][1]*1ll*b.a[1][2]%mod)%mod+a[0][2]*1ll*b.a[2][2]%mod)%mod;
        res[1][0]=(a[1][0]*1ll*b.a[0][0]%mod+a[1][1]*1ll*b.a[1][0]%mod)%mod;
        res[1][1]=a[1][1]*1ll*b.a[1][1]%mod;
        res[1][2]=((a[1][0]*1ll*b.a[0][2]%mod+a[1][1]*1ll*b.a[1][2]%mod)%mod+a[1][2]*1ll*b.a[2][2]%mod)%mod;
        res[2][0]=(a[2][0]*1ll*b.a[0][0]%mod+a[2][1]*1ll*b.a[1][0]%mod)%mod;
        res[2][1]=a[2][1]*1ll*b.a[1][1];
        res[2][2]=((a[2][0]*1ll*b.a[0][2]%mod+a[2][1]*1ll*b.a[1][2]%mod)%mod+a[2][2]*1ll*b.a[2][2]%mod)%mod;
        return res;
    }
    void merge0(const J&b){
        J res(2,1);
        res[0][0]=((a[0][0]*1ll*b.a[0][0]%mod+a[0][1]*1ll*b.a[1][0]%mod)%mod+a[0][2]*1ll*b.a[2][0]%mod)%mod;
        res[0][1]=a[0][1];
        res[0][2]=((a[0][0]*1ll*b.a[0][2]%mod+a[0][1]*1ll*b.a[1][2]%mod)%mod+a[0][2]*1ll*b.a[2][2]%mod)%mod;
        (*this)=res;
    }
    void merge1(){
        a[0][2]=(a[0][0]+a[0][2])%mod;
        a[1][2]=(a[1][0]+a[1][2])%mod;
        a[2][2]=(a[2][0]+a[2][2])%mod;
    }

然后跑了一下。

Process exited after 18.75 seconds with return value 0 (1.657e+04 ms cpu time, 430108 KB mem used).

很轻松进步了十秒啊。一看时限四秒半。
诅咒了出题人之后你开摆了，最后取得了 28 pts 高分。
赛后发现好像其他人过了一车。
发现标算和你不一样！标算写了个吉司机状物，和你历史和无关。
仔细思考了一下，发现你好像可以用几个标记维护所有信息。
具体的，设当前版本号为 t，分别维护区间 v=hsum-t\times sum 和 sum。
然后区间加 c 对前者的贡献是 -c\times(r-l+1)\times t，对后者的贡献是 c\times(r-l+1)。
查询时容易计算 hsum=v+t\times sum。
然后写了一个支持区间加区间求和的线段树。

Process exited after 12.39 seconds with return value 0 (1.006e+04 ms cpu time, 118192 KB mem used).

交上去取得了 68pts 高分！！
然后卡卡常数，卡不动了。
同学告诉你这个就是个线段树一，你发现你会一个很快的树状数组三。

Process exited after 8.23 seconds with return value 0 (6115 ms cpu time, 84592 KB mem used).

然后就通过了。
笑点解析：std 跑不过去。
std 的吉司机状势能分析我至今没有明白。

有人好像要完整代码。

struct Mod{
    using u128=__uint128_t;
    using ull=unsigned long long;
    void in(){cin(p),*this=p;}Mod(ull mod=998244353){*this=mod;}
    explicit operator ull&(){return p;}ull&operator()(){return p;}
    Mod&operator=(const ull&mod){return m=((ull)-1)/mod+1,p=mod,*this;}ull m,p;
    friend ull operator%(const u128&x,const Mod&self){return x-(((u128)x*(self.m))>>64)*self.p;}
};
Mod mod;
struct Fenwick{
    int n,t1[N],t2[N];inline int lowbit(const int&x){return x&(-x);}
    int ask(int x){int res=0;for(int i=x;i;i-=lowbit(i))res=(res+x*1ll*t1[i]+mod()-t2[i])%mod;return res;}
    void add(int x,int v){for(int i=x;i<=n;i+=lowbit(i))t1[i]=(t1[i]+v)%mod,t2[i]=(t2[i]+v*1ll*(x-1))%mod;}
    void add(int l,int r,int v){add(l,v),add(r+1,mod()-v);}
    int ask(int l,int r){return ask(r)-ask(l-1);}
};
struct SegmentTree{
    Fenwick p,q;
    void build(int l,int r){p.n=q.n=r-l+1;}
    void modify(int l,int r,int v,int ti){
        p.add(l,r,v),q.add(l,r,mod()-v*1ll*ti%mod);}
    int query(int l,int r,int ti){
        return (p.ask(l,r)*1ll*ti+q.ask(l,r))%mod;}
};
SegmentTree t;
int ti,res[N];
struct ODTNode{
    int l,r,v,ls;
    bool operator<(const ODTNode&p)const{return l<p.l;}
};
struct ODT:set<ODTNode>{
#define iter ODT::iterator
    int n;void init(int _n){insert({1,n=_n,0,0});}
    iter find(int x){return prev(upper_bound({x,0,0,0}));}
    void upd(iter&it){
        if(it->v)
            res[it->v]=(res[it->v]+t.query(it->l,it->r,ti)-it->ls+mod())%mod;
        erase(it++);
    }
    iter spilt(int x){
        if(x>n)return end();
        iter it=find(x);
        if(it->l==x)return it;
        int l=it->l,r=it->r,v=it->v;
        upd(it),insert({l,x-1,v,t.query(l,x-1,ti)});
        return insert({x,r,v,t.query(x,r,ti)}).x;
    }
    void assign(int l,int r,int v){
        iter itr=spilt(r+1),itl=spilt(l);
        for(iter it=itl;it!=itr;)upd(it);
        insert({l,r,v,t.query(l,r,ti)});
    }
#undef iter
};
int C,n,q;
ODT ot;
int main(){
#ifdef local
    freopen("cube/cube6.in","r",stdin);
#else
    freopen("cube.in","r",stdin);
#endif
    freopen("cube.out","w",stdout);
    cin(C,n,q),mod.in(),t.build(1,n),ot.init(n);
    for(int i=1,x;i<=n;i++)
        cin(x),ot.assign(i,i,x);
    for(int&i=ti=1,o,l,r,v;i<=q;i++){
        cin(o,l,r,v);
        if(o==1)
            t.modify(l,r,v,i);
        else
            ot.assign(l,r,v);
    }
    for(auto it=ot.begin();it!=ot.end();)ot.upd(it);
    for(int i=1;i<=n;i++)
        print(res[i]==0?0:mod()-res[i]),pc(" \n"[i==n]);
    return 0;
}

笑点解析：sunrise1024 加了快读之后比我加快读要快，但是他只是写了两棵线段树。