【题解】[CF718C Sasha and Array]

【题解】CF718C Sasha and Array

对于我这种喜欢写结构体封装起来的选手这道题真是太对胃了\(hhh\)

一句话题解：直接开一颗线段树的矩阵然后暴力维护还要卡卡常数

我们来把\(2 \times 2\)看做之后时间复杂度就是\(O(nlogn)\)。

写了一点点这种线段树维护除了数字之外的东西的题目，一个最大的感受就是递归用\(void\)，传答案什么的一个全局变量，这样比较快。

需要注意的点是\(lazy \ \ tag\)要随着\(seg\)一起初始化一下。

#include<bits/stdc++.h>

using namespace std;typedef long long ll;

#define DRP(t,a,b) for(register int t=(a),edd=(b);t>=edd;--t)

#define RP(t,a,b)  for(register int t=(a),edd=(b);t<=edd;++t)

#define ERP(t,a)   for(register int t=head[a];t;t=e[t].nx)

#define midd register int mid=(l+r)>>1

#define TMP template < class ccf >

#define lef l,mid,pos<<1

#define rgt mid+1,r,pos<<1|1

TMP inline ccf qr(ccf b){

    register char c=getchar();register int q=1;register ccf x=0;

    while(c<48||c>57)q=c==45?-1:q,c=getchar();

    while(c>=48&&c<=57)x=x*10+c-48,c=getchar();

    return q==-1?-x:x;}

TMP inline ccf Max(ccf a,ccf b){return a<b?b:a;}

TMP inline ccf Min(ccf a,ccf b){return a<b?a:b;}

TMP inline ccf Max(ccf a,ccf b,ccf c){return Max(a,Max(b,c));}

TMP inline ccf Min(ccf a,ccf b,ccf c){return Min(a,Min(b,c));}

TMP inline ccf READ(ccf* _arr,int _n){RP(t,1,_n)_arr[t]=qr((ccf)1);}

//----------------------template&IO---------------------------

const int mod=1e9+7;

const int maxn=1e5+5;

struct MTX{

    ll data[2][2];

    MTX(){data[0][0]=data[0][1]=data[1][0]=data[1][1]=0;}

    inline ll* operator[](int x){return data[x];}

    inline void operator *=(MTX a){

    MTX ret;

    RP(k,0,1)RP(i,0,1)RP(t,0,1)ret[t][i]=(ret[t][i]+data[t][k]*a[k][i])%mod;

    *this=ret;}

    inline void unis(){data[0][1]=data[1][0]=data[1][1]=1;data[0][0]=0;}

    inline void cle() {*this=MTX();RP(t,0,1)data[t][t]=1;}

    inline void operator ^=(int x){

    	MTX base=*this,ret;RP(t,0,1) ret[t][t]=1;

    for(register int t=x;t;t>>=1,base*=base)if(t&1)ret*=base;

    *this=ret;}

    inline void operator +=(MTX x){RP(t,0,1)RP(i,0,1)data[t][i]=(data[t][i]+x[t][i])%mod;}

    inline void pr(){RP(t,0,1){RP(i,0,1)cout<<data[t][i]<<' ';cout<<endl;}cout<<endl;}

}seg[maxn<<2],laz[maxn<<2];

bool lz[maxn<<2];

MTX ret,md;

int n,m;

inline void pd(int pos){

    if(not lz[pos]) return;

    seg[pos<<1]*=laz[pos];

    seg[pos<<1|1]*=laz[pos];

    laz[pos<<1]*=laz[pos];

    laz[pos<<1|1]*=laz[pos];

    lz[pos<<1]=lz[pos<<1|1]=1;

    laz[pos].cle();lz[pos]=0;

}

inline void pp(int pos){

    seg[pos]=MTX();

    seg[pos]+=seg[pos<<1];

    seg[pos]+=seg[pos<<1|1];

}

void build(int l,int r,int pos){

    if(l==r){

    seg[pos].unis();

    laz[pos].cle();

    seg[pos]^=qr(1)-1;

    return;

    }

    midd;laz[pos].cle();

    build(lef);build(rgt);

    pp(pos);

}

void upd(int L,int R,int l,int r,int pos){

    if(L<=l&&r<=R){

    laz[pos]*=md;

    seg[pos]*=md;

    lz[pos]=1;

    return;

    }midd;pd(pos);

    if(L<=mid) upd(L,R,lef);

    if(mid< R) upd(L,R,rgt);

    pp(pos);

}

void que(int L,int R,int l,int r,int pos){

    if(L<=l&&r<=R){

    ret+=seg[pos];

    return;

    }midd;pd(pos);

    if(L<=mid) que(L,R,lef);

    if(mid< R) que(L,R,rgt);

    pp(pos);

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("in.in","r",stdin);

    freopen("out.out","w",stdout);

#endif

    n=qr(1);m=qr(1);

    build(1,n,1);

    RP(t,1,m){

    register int t1,t2;

    if(qr(1)==1){

        t1=qr(1);t2=qr(1);

        md.unis();md^=qr(1);

        upd(t1,t2,1,n,1);

    }

    else{

        t1=qr(1);t2=qr(1);

        ret=MTX();

        que(t1,t2,1,n,1);

        printf("%lld\n",(ret[0][0]+ret[0][1])%mod);

    }

    }

    return 0;

}

巴特西

【题解】[CF718C Sasha and Array]

【题解】CF718C Sasha and Array

最新文章

热门文章