[Ynoi2004] tars2 的题解

· · 个人记录

大概是要支持平面上一个蛇皮正方形加，矩形和查询。

仔细分析一下修改操作，发现加的权值跟正方形里一个点与中心的切比雪夫距离有关，分类讨论一下可以拆成 8 个等腰RT三角形：

注意一下退化情况，d=1,2 分别只有 1,7 个三角形。

我们可以选一个舒适的角度进行二维扫描线

可以发现权值是从右至左严格递增的，然后查询也可以拆成 4 个。设三角形直角顶点坐标为 (a,b) 边长为 d 个格子，系数为 w，查询为 (x,y) 表示查询所有横坐标 \leq x，纵坐标 \leq y 的点权之和。进行毁天灭地的分类讨论得到：

  1. 当 x+y\geq a+b-d+1, x\leq a, y\leq b 时

令 p=-a-b+d,q=-b+d+1,r=3q-2p-1

则产生的贡献为

\frac{1}{6}w((x+y)^2(y-2x)+r(x+y)^2+(2p+1)(x+y)(y-2x)+(2p+1)r(x+y)+p(p+1)(y-2x)+p(p+1)r)
  1. 当 a-d+1\leq x \leq a, y>b 时

令 p=-a+d,q=d+1,r=3q-2p-1

则产生的贡献为

\frac{1}{6}w(-2x^3+(r-2(2p+1))x^2+((2p+1)r-2p(p+1))x+p(p+1)r)
  1. 当 b-d+1\leq y \leq b,x>a 时

令 p=-b+d,q=-b+d+1,r=3q-2p-1

则产生的贡献为

\frac{1}{6}w(y^3+(2p+r+1)y^2+(p(p+1)+(2p+1)r)y+p(p+1)r)
  1. 当 x>a,y>b 时

产生的贡献为

\frac{1}{6}w(d(d+1)(d+2))

有一个问题，发现所有贡献都带系数 \frac{1}{6} 但是在模 2^{30} 下没有逆元。我们可以定义一个类，用 6a+b（a\in [0,2^{30}), b\in[0,6)）来表示一个数。

通过 FutaRimeWoawaSete 的学长的提示，其实可以直接 unsigned int 然后先除以二再除以三。

CDQ 维护动态二维扫描线即可，时间 O(n \log^2 n)（超级大常数！），空间 O(n)。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned int ui;

const int MAXN=1e5;

inline int Read()
{
    int ret=0,sgn=1;char c;
    while(1) {c=getchar();if('0'<=c && c<='9') {ret=c-'0';break;}}
    while(1) {c=getchar();if('0'<=c && c<='9') ret=ret*10+c-'0';else break;}
    return sgn*ret;
}

int dsc[4*MAXN+5],dnum;//离散化 
struct BIT
{
    ui sum[4*MAXN+5];int Edit[4*MAXN+5],New;
    inline int lowbit(int x) {return x&-x;}
    inline void upd(int x) {if(Edit[x]<New) Edit[x]=New,sum[x]=0;}
    inline void Clean() {++New;}
    inline void Plus(int x,ui v) {for(;x<=dnum;x+=lowbit(x)) upd(x),sum[x]+=v;}
    inline ui Ask(int x)
    {
        ui ret=0;
        for(;x>0;x-=lowbit(x)) upd(x),ret+=sum[x];
        return ret;
    }
}mapn[6];

inline int Search(int x)
{
    for(int L=1,R=dnum,mid;1;)
    {
        mid=(L+R)>>1;
        if(dsc[mid]==x) return mid;
        if(dsc[mid]<x) L=mid+1;
        else R=mid-1;
    }
    return 0;
}

int n;
ui ans[MAXN+5];int anum;

struct Query
{
    int opt,a,b,c,d,ID;//查询编号 
    inline void Scan() {opt=Read(),a=Read(),b=Read(),c=Read(),d=Read();}
}qry[MAXN+5];

struct Ope
{
    int x,y;//y 离散化后结果 
    ui val[6];
    int ID,Time;//0 修改 >0 查询编号，Time 时间戳 
}ope[4*MAXN+5],lef[2*MAXN+5],rig[2*MAXN+5];int onum,lnum,rnum;
inline bool cmp(Ope a,Ope b) {return (a.x==b.x ? a.ID<b.ID : a.x<b.x);}

void CDQ(int L,int R,int lim)
{
    //斜线：0~5 水平：6~11
    if(L==R) return;
    int mid=(L+R)>>1;
    CDQ(L,mid,lim),CDQ(mid+1,R,lim);
    lnum=rnum=0;
    for(int i=L;i<=mid;i++) lef[++lnum]=ope[i];
    for(int i=mid+1;i<=R;i++) rig[++rnum]=ope[i];
    for(int i=L,j=1,k=1;i<=R;i++)
        if(j<=lnum && k<=rnum)
        {
            if(cmp(lef[j],rig[k])) ope[i]=lef[j++];
            else ope[i]=rig[k++];
        }
        else if(j<=lnum) ope[i]=lef[j++];
        else ope[i]=rig[k++];
    for(int i=0;i<lim;i++) mapn[i].Clean();
    for(int i=L;i<=R;i++)
        if(!ope[i].ID && ope[i].Time<=mid)
            for(int j=0;j<lim;j++) mapn[j].Plus(ope[i].y,ope[i].val[j]);
        else if(ope[i].ID && ope[i].Time>mid)
            for(int j=0;j<lim;j++) ans[ope[i].ID]+=ope[i].val[j]*mapn[j].Ask(ope[i].y);
}

struct msg {int x,y,d,w,ID;}trg[4*MAXN+5];int tnum;
inline void Discre()
{
    for(int i=1;i<=onum;i++) dsc[i]=ope[i].y;
    sort(dsc+1,dsc+onum+1),dnum=unique(dsc+1,dsc+onum+1)-dsc-1;
    for(int i=1;i<=onum;i++) ope[i].y=Search(ope[i].y);
}
Ope Copy[4*MAXN+5];
inline void Solve()//解决一组三角形覆盖二位前缀和查询
{
    //情况一，斜线贡献 
    onum=0;
    for(int i=1;i<=tnum;i++)
        if(trg[i].ID)//查询
        {
            ui xy=trg[i].x+trg[i].y,yx=trg[i].y-2*trg[i].x;

            ope[++onum].x=trg[i].x;
            ope[onum].y=trg[i].x+trg[i].y;
            ope[onum].val[0]=xy*xy*yx;
            ope[onum].val[1]=xy*xy;
            ope[onum].val[2]=xy*yx;
            ope[onum].val[3]=xy;
            ope[onum].val[4]=yx;
            ope[onum].val[5]=1;
            if(trg[i].w<0) for(int j=0;j<6;j++) ope[onum].val[j]*=-1;
            ope[onum].ID=trg[i].ID;
            ope[onum].Time=onum;
        }
        else//修改 
        {
            ui p=-trg[i].x-trg[i].y+trg[i].d,q=-trg[i].y+trg[i].d+1;
            ui r=3*q-2*p-1,p1=2*p+1,pp=p*(p+1);

            ope[++onum].x=trg[i].x-trg[i].d+1;
            ope[onum].y=trg[i].x+trg[i].y-trg[i].d+1;
            ope[onum].val[0]=trg[i].w;
            ope[onum].val[1]=trg[i].w*r;
            ope[onum].val[2]=trg[i].w*p1;
            ope[onum].val[3]=trg[i].w*p1*r;
            ope[onum].val[4]=trg[i].w*pp;
            ope[onum].val[5]=trg[i].w*pp*r;
            ope[onum].ID=0;
            ope[onum].Time=onum;

            ++onum,ope[onum]=ope[onum-1];
            ope[onum].x=trg[i].x+1;
            for(int j=0;j<6;j++) ope[onum].val[j]*=-1;
            ope[onum].Time=onum; 
        }
    for(int i=1;i<=onum;i++) Copy[i]=ope[i];
    Discre(),CDQ(1,onum,6);
    //情况一，水平贡献
    onum=0;
    for(int i=1;i<=tnum;i++)
        if(trg[i].ID)
        {
            ++onum,ope[onum]=Copy[onum];
            ope[onum].y=trg[i].y;
        }
        else 
        {
            ++onum,ope[onum]=Copy[onum];
            ope[onum].x=trg[i].x+1;
            ope[onum].y=trg[i].y+1;

            ++onum,ope[onum]=Copy[onum];
            ope[onum].x=trg[i].x-trg[i].d+1;
            ope[onum].y=trg[i].y+1;
        }
    Discre(),CDQ(1,onum,6);
    //情况二
    onum=0;
    for(int i=1;i<=tnum;i++)
        if(trg[i].ID)
        {
            ui x=trg[i].x;

            ope[++onum].x=trg[i].x;
            ope[onum].y=trg[i].y;
            ope[onum].val[0]=x*x*x;
            ope[onum].val[1]=x*x;
            ope[onum].val[2]=x;
            ope[onum].val[3]=1;
            if(trg[i].w<0) for(int j=0;j<4;j++) ope[onum].val[j]*=-1;
            ope[onum].ID=trg[i].ID;
            ope[onum].Time=onum;
        }
        else
        {
            ui p=-trg[i].x+trg[i].d,q=trg[i].d+1;
            ui r=3*q-2*p-1,p1=2*p+1,pp=p*(p+1);

            ope[++onum].x=trg[i].x-trg[i].d+1;
            ope[onum].y=trg[i].y+1;
            ope[onum].val[0]=trg[i].w*(-2);
            ope[onum].val[1]=trg[i].w*(r-2*p1);
            ope[onum].val[2]=trg[i].w*(p1*r-2*pp);
            ope[onum].val[3]=trg[i].w*pp*r;
            ope[onum].ID=0;
            ope[onum].Time=onum;

            ++onum,ope[onum]=ope[onum-1];
            ope[onum].x=trg[i].x+1;
            for(int j=0;j<4;j++) ope[onum].val[j]*=-1;
            ope[onum].Time=onum;
        }
    Discre(),CDQ(1,onum,4);
    //情况三
    onum=0;
    for(int i=1;i<=tnum;i++)
        if(trg[i].ID)
        {
            ui y=trg[i].y;

            ope[++onum].x=trg[i].x;
            ope[onum].y=trg[i].y;
            ope[onum].val[0]=y*y*y;
            ope[onum].val[1]=y*y;
            ope[onum].val[2]=y;
            ope[onum].val[3]=1;
            if(trg[i].w<0) for(int j=0;j<4;j++) ope[onum].val[j]*=-1;
            ope[onum].ID=trg[i].ID;
            ope[onum].Time=onum;
        }
        else
        {
            ui p=-trg[i].y+trg[i].d,q=-trg[i].y+trg[i].d+1;
            ui r=3*q-2*p-1,p1=2*p+1,pp=p*(p+1);

            ope[++onum].x=trg[i].x+1;
            ope[onum].y=trg[i].y-trg[i].d+1;
            ope[onum].val[0]=trg[i].w;
            ope[onum].val[1]=trg[i].w*(r+p1);
            ope[onum].val[2]=trg[i].w*(pp+p1*r);
            ope[onum].val[3]=trg[i].w*pp*r;
            ope[onum].ID=0;
            ope[onum].Time=onum;

            ++onum,ope[onum]=ope[onum-1];
            ope[onum].y=trg[i].y+1;
            for(int j=0;j<4;j++) ope[onum].val[j]*=-1;
            ope[onum].Time=onum;
        }
    Discre(),CDQ(1,onum,4);
    //情况四
    onum=0;
    for(int i=1;i<=tnum;i++)
        if(trg[i].ID)
        {
            ope[++onum].x=trg[i].x;
            ope[onum].y=trg[i].y;
            ope[onum].val[0]=trg[i].w;
            ope[onum].ID=trg[i].ID;
            ope[onum].Time=onum;
        }
        else
        {
            ope[++onum].x=trg[i].x+1;
            ope[onum].y=trg[i].y+1;
            ope[onum].val[0]=trg[i].w*trg[i].d*(trg[i].d+1)*(trg[i].d+2);
            ope[onum].ID=0;
            ope[onum].Time=onum;
        }
    Discre(),CDQ(1,onum,1);
}

int main()
{
    n=Read();
    for(int i=1;i<=n;i++)
    {
        qry[i].Scan();
        if(qry[i].opt==2) qry[i].ID=++anum;
    }
    //1.上下颠倒
    tnum=0;
    for(int i=1;i<=n;i++)
        if(qry[i].opt==1)//修改
        {
            if(qry[i].c<2) continue;
            trg[++tnum]=msg{qry[i].a+qry[i].c-1,-(qry[i].b+1),qry[i].c-1,qry[i].d,0};
        }
        else
        {
            trg[++tnum]=msg{qry[i].b,-qry[i].c,0,1,qry[i].ID};
            trg[++tnum]=msg{qry[i].a-1,-qry[i].c,0,-1,qry[i].ID};
            trg[++tnum]=msg{qry[i].b,-qry[i].d-1,0,-1,qry[i].ID};
            trg[++tnum]=msg{qry[i].a-1,-qry[i].d-1,0,1,qry[i].ID};
        }
    Solve();
    //2.顺时针 90 度 
    tnum=0;
    for(int i=1;i<=n;i++)
        if(qry[i].opt==1)
        {
            if(qry[i].c<3) continue;
            //(a+1,b+c-1)
            trg[++tnum]=msg{qry[i].b+qry[i].c-1,-(qry[i].a+1),qry[i].c-2,qry[i].d,0};
        }
        else
        {
            trg[++tnum]=msg{qry[i].d,-qry[i].a,0,1,qry[i].ID};
            trg[++tnum]=msg{qry[i].c-1,-qry[i].a,0,-1,qry[i].ID};
            trg[++tnum]=msg{qry[i].d,-qry[i].b-1,0,-1,qry[i].ID};
            trg[++tnum]=msg{qry[i].c-1,-qry[i].b-1,0,1,qry[i].ID};
        }
    Solve();
    //3.顺时针 90 度，上下颠倒 
    tnum=0;
    for(int i=1;i<=n;i++)
        if(qry[i].opt==1)
        {
            if(qry[i].c<2) continue;
            trg[++tnum]=msg{qry[i].b+qry[i].c-1,qry[i].a,qry[i].c-1,qry[i].d,0};
        }
        else
        {
            trg[++tnum]=msg{qry[i].d,qry[i].b,0,1,qry[i].ID};
            trg[++tnum]=msg{qry[i].c-1,qry[i].b,0,-1,qry[i].ID};
            trg[++tnum]=msg{qry[i].d,qry[i].a-1,0,-1,qry[i].ID};
            trg[++tnum]=msg{qry[i].c-1,qry[i].a-1,0,1,qry[i].ID};
        }
    Solve();
    //4.上下左右颠倒
    tnum=0;
    for(int i=1;i<=n;i++)
        if(qry[i].opt==1)
        {
            if(qry[i].c<2) continue;
            trg[++tnum]=msg{-(qry[i].a-qry[i].c+1),-(qry[i].b+1),qry[i].c-1,qry[i].d,0};
        }
        else
        {
            trg[++tnum]=msg{-qry[i].a,-qry[i].c,0,1,qry[i].ID};
            trg[++tnum]=msg{-qry[i].b-1,-qry[i].c,0,-1,qry[i].ID};
            trg[++tnum]=msg{-qry[i].a,-qry[i].d-1,0,-1,qry[i].ID};
            trg[++tnum]=msg{-qry[i].b-1,-qry[i].d-1,0,1,qry[i].ID};
        }
    Solve();
    //5.左右颠倒
    tnum=0;
    for(int i=1;i<=n;i++)
        if(qry[i].opt==1) trg[++tnum]=msg{-(qry[i].a-qry[i].c+1),qry[i].b,qry[i].c,qry[i].d,0};
        else
        {
            trg[++tnum]=msg{-qry[i].a,qry[i].d,0,1,qry[i].ID};
            trg[++tnum]=msg{-qry[i].b-1,qry[i].d,0,-1,qry[i].ID};
            trg[++tnum]=msg{-qry[i].a,qry[i].c-1,0,-1,qry[i].ID};
            trg[++tnum]=msg{-qry[i].b-1,qry[i].c-1,0,1,qry[i].ID};
        }
    Solve();
    //6.逆时针 90 度 
    tnum=0;
    for(int i=1;i<=n;i++)
        if(qry[i].opt==1)
        {
            if(qry[i].c<2) continue;
            //(a,b-c+1)
            trg[++tnum]=msg{-(qry[i].b-qry[i].c+1),qry[i].a,qry[i].c-1,qry[i].d,0};
        }
        else
        {
            trg[++tnum]=msg{-qry[i].c,qry[i].b,0,1,qry[i].ID};
            trg[++tnum]=msg{-qry[i].d-1,qry[i].b,0,-1,qry[i].ID};
            trg[++tnum]=msg{-qry[i].c,qry[i].a-1,0,-1,qry[i].ID};
            trg[++tnum]=msg{-qry[i].d-1,qry[i].a-1,0,1,qry[i].ID};
        }
    Solve();
    //7.逆时针 90 度，左右颠倒 
    tnum=0;
    for(int i=1;i<=n;i++)
        if(qry[i].opt==1)
        {
            if(qry[i].c<2) continue;
            //(a+1,b-c+1)
            trg[++tnum]=msg{-(qry[i].b-qry[i].c+1),-(qry[i].a+1),qry[i].c-1,qry[i].d,0};
        }
        else
        {
            trg[++tnum]=msg{-qry[i].c,-qry[i].a,0,1,qry[i].ID};
            trg[++tnum]=msg{-qry[i].d-1,-qry[i].a,0,-1,qry[i].ID};
            trg[++tnum]=msg{-qry[i].c,-qry[i].b-1,0,-1,qry[i].ID};
            trg[++tnum]=msg{-qry[i].d-1,-qry[i].b-1,0,1,qry[i].ID};
        }
    Solve();
    //8.不变
    tnum=0;
    for(int i=1;i<=n;i++)
        if(qry[i].opt==1)
        {
            if(qry[i].c<2) continue;
            trg[++tnum]=msg{qry[i].a+qry[i].c-1,qry[i].b,qry[i].c-1,qry[i].d,0};
        }
        else
        {
            trg[++tnum]=msg{qry[i].b,qry[i].d,0,1,qry[i].ID};
            trg[++tnum]=msg{qry[i].a-1,qry[i].d,0,-1,qry[i].ID};
            trg[++tnum]=msg{qry[i].b,qry[i].c-1,0,-1,qry[i].ID};
            trg[++tnum]=msg{qry[i].a-1,qry[i].c-1,0,1,qry[i].ID};
        }
    Solve();
    for(int i=1;i<=anum;i++)
    {
        ll res=ans[i]&((1ll<<31)-1);
        res>>=1;
        printf("%lld\n",(res*715827883)&((1<<30)-1));
    }
    return 0;
}