求助,过了样例,一分没有
查看原帖
求助,过了样例,一分没有
437398
EastIsRed楼主2023/7/28 19:27
#include<cstdio>
#include<iostream>
using namespace std;

//debug using function
void print_martix(int martix[][4])
{
    for(int i=0;i<4;putchar('\n'),i++)
        for(int j=0;j<4;j++)
            printf("%d ",martix[i][j]);
}

const int MAXN=250086,mod=993244353;
int n,m,a[MAXN],b[MAXN],c[MAXN];
struct node{
    int l,r;
    int val[4];
    bool has_lzd;int lzd[4][4];
    void print()
    {
        printf("node covers segment from %d to %d,with values as follows:\n",l,r);
        for(int i=0;i<4;i++)
            printf("%d ",val[i]);
    }
}tr[MAXN<<2];
int oper1[4][4]={{1,0,1,0},
                 {1,1,0,0},
                 {0,1,1,0},
                 {0,0,0,1} };
int oper2[4][4]={{1,0, 0,0},
                 {0,-1, 0,0},
                 {0, 0, 0,0},
                 {-1,0,-1,1}};//pos with value 1 will be reset when doing operation 2
inline void push_up(int now)
{
    for(int i=0;i<4;i++)
        tr[now].val[i]=(tr[now<<1].val[i]+tr[now<<1|1].val[i])%mod;
}
inline void martix_reset(int now[][4])
{
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            if(i==j)
                now[i][j]=1;
            else now[i][j]=0;
}
void build(int now,int l,int r)
{
    tr[now].l=l;
    tr[now].r=r;
    tr[now].has_lzd=false;
    martix_reset(tr[now].lzd);
    if(l!=r)
    {
        int mid=l+r>>1;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
        push_up(now);
    }
    else
    {
        tr[now].val[0]=a[l];
        tr[now].val[1]=b[l];
        tr[now].val[2]=c[l];
        tr[now].val[3]=1;
    }
}
inline void updabc(int now,int martix[][4])
{
    static int temp[4];
    for(int i=0;i<4;i++)
    {
        temp[i]=0;
        for(int j=0;j<4;j++)
            temp[i]=(temp[i]+1ll*tr[now].val[j]*martix[j][i]%mod)%mod;
    }
    for(int i=0;i<4;i++)
        tr[now].val[i]=temp[i];
}
inline void domulti(int martix1[][4],int martix2[][4])
{
    static int temp[4][4];
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
        {
            temp[i][j]=0;
            for(int k=0;k<4;k++)
                temp[i][j]=(temp[i][j]+1ll*martix1[i][k]*martix2[k][j]%mod)%mod;
        }
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            martix1[i][j]=temp[i][j];
}
inline void push_down(int now)
{
    if(tr[now].has_lzd)
    {
        updabc(now<<1,tr[now].lzd);
        updabc(now<<1|1,tr[now].lzd);
        domulti(tr[now<<1].lzd,tr[now].lzd);
        domulti(tr[now<<1|1].lzd,tr[now].lzd);
        tr[now<<1].has_lzd=true;
        tr[now<<1|1].has_lzd=true;
        martix_reset(tr[now].lzd);
        tr[now].has_lzd=false;
    }
}
void change(int now,int l,int r,int martix[][4])
{
    if(l<=tr[now].l&&tr[now].r<=r)
    {
        updabc(now,martix);
        domulti(tr[now].lzd,martix);
        tr[now].has_lzd=true;
        tr[now].print();
        putchar('\n');
        return;
    }
    push_down(now);
    int mid=tr[now].l+tr[now].r>>1;
    if(l<=mid)
        change(now<<1,l,r,martix);
    if(mid<r)
        change(now<<1|1,l,r,martix);
    push_up(now);
    tr[now].print();
    putchar('\n');
}
struct result_structure{
    int a,b,c;
    result_structure():a(0),b(0),c(0){}
    result_structure(int _a,int _b,int _c):a(_a),b(_b),c(_c){}
    result_structure operator += (const result_structure& rhs)
    {
        a=(a+rhs.a)%mod;b=(b+rhs.b)%mod;c=(c+rhs.c)%mod;
        return *this;
    }
    void print()const
    {
        printf("%d %d %d",a,b,c);
    }
    friend ostream& operator << (ostream& outstr,const result_structure &res)
    {
        return outstr<<res.a<<' '<<res.b<<' '<<res.c;
    }
};
result_structure getres(int now,int l,int r)
{
    if(l<=tr[now].l&&tr[now].r<=r)
        return result_structure(tr[now].val[0],tr[now].val[1],tr[now].val[2]);
    push_down(now);
    int mid=tr[now].l+tr[now].r>>1;
    result_structure res;
    if(l<=mid)
        res+=getres(now<<1,l,r);
    if(mid<r)
        res+=getres(now<<1|1,l,r);
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",a+i,b+i,c+i);
    build(1,1,n);
    scanf("%d",&m);
    while(m--)
    {
        static int oper_martix[4][4];
        martix_reset(oper_martix);
        int op,l,r;
        putchar('\n');
        scanf("%d%d%d",&op,&l,&r);
        if(op>=1&&op<=3)
        {
            for(int i=0;i<4;i++)
                oper_martix[i][op-1]=oper1[i][op-1];
            printf("use martix as follow to change:\n");
            print_martix(oper_martix);
            putchar('\n');
            change(1,l,r,oper_martix);
        }
        else if(op>=4&&op<=6)
        {
            int x;
            scanf("%d",&x);
            for(int i=0;i<4;i++)
                if(oper2[i][op-4]==-1)
                    oper_martix[i][op-4]=x;
                else oper_martix[i][op-4]=oper2[i][op-4];
            printf("use martix as follow to change:\n");
            print_martix(oper_martix);
            putchar('\n');
            change(1,l,r,oper_martix);
        }
        else cout<<getres(1,l,r)<<endl;
    }
    return 0;
}

部分调试代码未删,自己查了两个小时了,救救孩子吧

2023/7/28 19:27
加载中...