Problem

boshi 是 Rayment 的好朋友。

Rayment 最近迷上了一个叫 $Just~Shapes~\&~Beats$的音游，于是就推荐给了 boshi(网易云上也有这个游戏部分音乐的歌单)。可 boshi 有点着迷于游戏音乐难以集中精神，有时反应慢了半拍，导致他在第二关就挂了一回。忍无可忍的 boshi 摘下了耳机，他决定用个更科学的方法来通过这一关。

这首歌的名字就叫做 $Logic~Gatekeeper$，如果条件允许的话你也可以一边听歌一边切这道题目。

游戏的不同关卡攻击方式都不一样，但这关的攻击方式比较简单。形式化地来说，攻击可以被具象化为对一个矩阵的攻击，也就是说如果你待在这个矩阵的范围内，你就会受到 1 的攻击。

游戏界面可以认为是一个 n×m 的矩阵，而游戏角色恰好占一个方格的位置。boshi 会进行不断地进行预测某个子矩阵的攻击概率升高或降低了一定数值，同时为了评估某一个子矩阵的安全性，他也要知道如果他随机待在子矩阵内的一个位置，受到攻击的期望是多少。当然，初始时整个游戏界面任意一个位置的攻击概率为 0。

为了避免小数产生的误差，boshi 给出的所有的概率都是在模 $998244353$意义下的值，因此你在输出期望的时候也应该对 $998244353$取模。

Rayment 听得脑袋都晕了，boshi 只好请你来帮他过了这关，不受一点攻击才能拿到 S 评定。

$1\leq n,m\leq 10^6,1\leq q\leq 10^5$

$1\leq a\leq c\leq n,1\leq b\leq d\leq m,0\leq k < 998244353$

Solution

显然用二维树状数组空间上也是吃不消的。

如果把操作按点拆成 4 个，那么由于其中有两对点的 x 坐标相等，所以最终总会被放在一起，且操作有一部分相互抵消，那么不妨合并他们。把操作拆成两个，即询问 (0,0) 到 (x,y) 的，拆成修改左方的子矩阵。但是为了方便，这里需要把坐标都偏移一格。

我们考虑拆分区间，考虑跨立区间的贡献。

先对 x 轴进行排序，然后 cdq 的时候对时间进行排序。

按照 x 轴划分区间之后，左边的修改对右边的询问有影响，右边的修改对左边的询问也有贡献。

由于线段树的常数比较大，而且操作的次数很多，我们用树状数组维护 y 轴上的贡献，左边的数组修改的时候，应该改 val*x 即可，因为右边的询问 x 必定比左边大。而右边的改则只需要改 val，询问时乘 x，因为右边 x 比较大。

时间复杂度 $O(q\log q\log m)$。

Code

#include <algorithm>
#include <cstdio>
#define rg register
#define lowbit(x) ((x)&(-(x)))
using namespace std;
typedef long long ll;
const int maxn=1000010,maxm=100010,mod=998244353;
template <typename Tp> inline void getmin(Tp &x,Tp y){if(y<x) x=y;}
template <typename Tp> inline void getmax(Tp &x,Tp y){if(y>x) x=y;}
template <typename Tp> inline void read(Tp &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') f=1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    if(f) x=-x;
}
struct data{
    int tp,t,x,y,id,y2;
    bool operator < (const data &p){return x<p.x;}
}q[maxm<<2],tmp[maxm<<2];
int n,m,k,tot,qc,top,ans[maxm],res[maxm],id[maxm<<2];
inline int pls(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
struct BIT{
    int a[maxn],a2[maxn];
    void add(int p,int v)
    {
        for(int i=p;i<=m;i+=lowbit(i))
          a[i]=pls(a[i],v),a2[i]=pls(a2[i],(ll)p*v%mod);
    }
    int query(int p)
    {
        int res=0;
        for(int i=p;i;i-=lowbit(i)) res=pls(res,dec((ll)(p+1)*a[i]%mod,a2[i]));
        return res;
    }
}a,b;
int power(int x,int y)
{
    int res=1;
    for(;y;y>>=1,x=(ll)x*x%mod)
      if(y&1)
        res=(ll)res*x%mod;
    return res;
}
void input()
{
    int op,x,y,s,t,val;
    read(n);read(m);read(k);m++;tot=k<<1;
    for(rg int i=1;i<=k;i++)
    {
        read(op);read(x);read(y);read(s);read(t);
        x++;y++;s++;t++;
        if(op==1)
        {
            read(val);
            q[(i<<1)-1]=(data){0,i,s,t,val,y};
            q[i<<1]=(data){0,i,x-1,t,mod-val,y};
        }
        else
        {
            q[(i<<1)-1]=(data){1,i,s,t,++qc,y};
            q[i<<1]=(data){2,i,x-1,t,qc,y};
            res[qc]=power((ll)(s-x+1)*(t-y+1)%mod,mod-2);
        }
    }
    sort(q+1,q+tot+1);
}
void cdq(const int &l,const int &r)
{
    int mid=(l+r)>>1;
    if(l<mid) cdq(l,mid);
    if(mid+1<r) cdq(mid+1,r);
    rg int i=l,j=mid+1;top=0;
    while(i<=mid&&j<=r)
    {
        if(q[i].t<=q[j].t) tmp[++top]=q[i++],id[top]=0;
        else tmp[++top]=q[j++],id[top]=1;
    }
    while(i<=mid) tmp[++top]=q[i++],id[top]=0;
    while(j<=r) tmp[++top]=q[j++],id[top]=1;
    for(i=1;i<=top;i++)
    {
        if(id[i])//r
        {
            if(tmp[i].tp==1)
              ans[tmp[i].id]=pls(ans[tmp[i].id],dec(a.query(tmp[i].y),a.query(tmp[i].y2-1)));
            else if(tmp[i].tp==2)
              ans[tmp[i].id]=dec(ans[tmp[i].id],dec(a.query(tmp[i].y),a.query(tmp[i].y2-1)));
            else b.add(tmp[i].y2,tmp[i].id),b.add(tmp[i].y+1,mod-tmp[i].id);
        }
        else
        {
            if(tmp[i].tp==1)
              ans[tmp[i].id]=pls(ans[tmp[i].id],(ll)tmp[i].x*dec(b.query(tmp[i].y),b.query(tmp[i].y2-1))%mod);
            else if(tmp[i].tp==2)
              ans[tmp[i].id]=dec(ans[tmp[i].id],(ll)tmp[i].x*dec(b.query(tmp[i].y),b.query(tmp[i].y2-1))%mod);
            else a.add(tmp[i].y2,(ll)tmp[i].id*tmp[i].x%mod),a.add(tmp[i].y+1,(ll)(mod-tmp[i].id)*tmp[i].x%mod);
        }
    }
    for(i=1;i<=top;i++)
    {
        if(!tmp[i].tp)
        {
            if(id[i]) b.add(tmp[i].y2,mod-tmp[i].id),b.add(tmp[i].y+1,tmp[i].id);
            else a.add(tmp[i].y2,mod-(ll)tmp[i].id*tmp[i].x%mod),a.add(tmp[i].y+1,(ll)tmp[i].id*tmp[i].x%mod);
        }
        q[l+i-1]=tmp[i];
    }
}
int main()
{
    input();
    cdq(1,tot);
    for(rg int i=1;i<=qc;i++) printf("%lld\n",(ll)ans[i]*res[i]%mod);
    return 0;
}