题解：P11621 [Ynoi Easy Round 2025] TEST_139

Seauy · 2025-01-28 03:48:59 · 题解

这题是 tars2 的非常阉割版。

修改范围就是个直角边上有 d 个点的等腰直角三角形，这个限制没办法直接上 CDQ 分治所以要拆成若干只有两维限制的范围。发现等腰直角三角形少一条边，比如变成 Y\geq y,X+Y< x+y+d 的范围就能 CDQ 了。设少一条边的三角形的顶点（右下角）为 (x,y)，那假设我把查询拆成四个 X\geq a,Y\geq b 的求和，大力推式子得：

当 a+b\leq x+y,b\geq y 时，贡献为

\frac{1}{2}w(x+y-a-b+1)(x+y-a-b+2)\\ =\frac{1}{2}w((a+b)^2+(-2x-2y-3)(a+b)+(x+y+1)(x+y+2))

要维护 (a+b)^2,a+b 和常数项的系数。

当 a\leq x,b\leq y-1 时，贡献为

\frac{1}{2}w(x-a+1)(x-a+2)\\ =\frac{1}{2}w(a^2+(-2x-3)a+(x+1)(x+2))

要维护 a^2,a 和常数项的系数。

所以 X\geq x,Y\geq y,X+Y<x+y+d 可以拆成右下角为 (x+d-1,y) 的向左无限延伸的三角形，减右下角为 (x-1,y+d) 的向左无限延伸的三角形，还要再减 (x-1,y+d-1) 左下角区域，并加上 (x-1,y-1) 左下角区域。设左下角区域顶点为 (x,y)，那贡献为：

当 a\leq x,b\leq y 时，

w(x-a+1)(y-b+1)\\ =\frac{1}{2}w(2ab+(-2y-2)a+(-2x-2)b+2(x+1)(y+1))

要维护 ab,a,b 和常数项的系数。

所以时间 O(m\log^2 m) 空间 O(m)，但是写的时候可能要注意常数，比方离散化需要排序的数并没有那么多。

最后关于对 2^{30} 取模，我们可以不管 \frac{1}{2} 的系数先 unsigned int 算出两倍答案，直接右位移是模 2^{31} 的结果，再去掉最高位即可，所以写法可以是先左移一位再右移两位。

参考代码：

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

typedef unsigned int ui;

const int MAXM=2e5,SIZE=4*MAXM;

int Read()
{
    int res=0;char c;
    while(!isdigit(c=getchar()));
    while(isdigit(c)) res=res*10+c-'0',c=getchar();
    return res;
}
void Print(ui x)
{
    if(x<10) {putchar('0'+x);return;}
    ui y=x/10;
    Print(y);
    putchar('0'+x-y*10);
}

int m,opt[MAXM+5]; ui X1[MAXM+5],X2[MAXM+5],Y1[MAXM+5],Y2[MAXM+5];
ui ans[MAXM+5];
int Q[SIZE+5],ID[SIZE+5],tot; ui X[SIZE+5],Y[SIZE+5],val[SIZE+5][4];

ui dsc[SIZE+5];int dnum;
struct BIT
{
    ui sum[SIZE+5];
    int lowbit(int x) {return x&-x;}
    void Plus(int x,ui v) {for(;x;x-=lowbit(x)) sum[x]+=v;}
    ui Ask(int x) {ui res=0; for(;x<=dnum;x+=lowbit(x)) res+=sum[x]; return res;}
}mapn[4];

int tmp[SIZE+5];
void CDQ(int L,int R,int t)
{
    if(L==R) return;
    int mid=(L+R)>>1;
    CDQ(L,mid,t),CDQ(mid+1,R,t);
    int Head=L,lef=L,rig=mid+1;
    while(1)
        if(X[Q[lef]]>=X[Q[rig]]) {tmp[Head++]=Q[lef++]; if(lef>mid) break;}
        else {tmp[Head++]=Q[rig++]; if(rig>R) break;}
    while(lef<=mid) tmp[Head++]=Q[lef++];
    while(rig<=R) tmp[Head++]=Q[rig++];
    for(int i=L;i<=R;i++)
    {
        Q[i]=tmp[i];
        if(ID[Q[i]]>0 && Q[i]>mid)
            for(int j=0;j<=t;j++) ans[ID[Q[i]]]+=val[Q[i]][j]*mapn[j].Ask(Y[Q[i]]);
        else if(ID[Q[i]]<0 && Q[i]<=mid)
            for(int j=0;j<=t;j++) mapn[j].Plus(Y[Q[i]],val[Q[i]][j]);
    }
    for(int i=L;i<=R;i++)
        if(ID[Q[i]]<0 && Q[i]<=mid)
            for(int j=0;j<=t;j++) mapn[j].Plus(Y[Q[i]],-val[Q[i]][j]);
}

int main()
{
    m=Read();
    for(int i=1;i<=m;i++)
    {
        opt[i]=Read(),X1[i]=Read(),X2[i]=Read(),Y1[i]=Read(),Y2[i]=Read();
        if(opt[i]==1) --Y1[i];
    }
    for(int i=1;i<=m;i++)
        if(opt[i]==1)
        {
            //x y d w
            ui x=X1[i]+Y1[i],y=X2[i];
            ID[++tot]=-1,X[tot]=x+y,Y[tot]=-y;
            val[tot][0]=Y2[i];
            val[tot][1]=Y2[i]*(-2*x-2*y-3);
            val[tot][2]=Y2[i]*(x+y+1)*(x+y+2);
            dsc[++dnum]=Y[tot];

            x=X1[i]-1,y=X2[i]+Y1[i]+1;
            ID[++tot]=-1,X[tot]=x+y,Y[tot]=-y;
            val[tot][0]=-Y2[i];
            val[tot][1]=-Y2[i]*(-2*x-2*y-3);
            val[tot][2]=-Y2[i]*(x+y+1)*(x+y+2);
            dsc[++dnum]=Y[tot];
        }
        else
        {
            ui x=X1[i],y=Y1[i];
            ID[++tot]=i,X[tot]=x+y,Y[tot]=-y;
            val[tot][0]=(x+y)*(x+y);
            val[tot][1]=x+y;
            val[tot][2]=1;
            dsc[++dnum]=Y[tot];

            x=X2[i]+1,y=Y1[i];
            ID[++tot]=i,X[tot]=x+y,Y[tot]=-y;
            val[tot][0]=-(x+y)*(x+y);
            val[tot][1]=-(x+y);
            val[tot][2]=-1;

            x=X1[i],y=Y2[i]+1;
            ID[++tot]=i,X[tot]=x+y,Y[tot]=-y;
            val[tot][0]=-(x+y)*(x+y);
            val[tot][1]=-(x+y);
            val[tot][2]=-1;
            dsc[++dnum]=Y[tot];

            x=X2[i]+1,y=Y2[i]+1;
            ID[++tot]=i,X[tot]=x+y,Y[tot]=-y;
            val[tot][0]=(x+y)*(x+y);
            val[tot][1]=x+y;
            val[tot][2]=1;
        }
    sort(dsc+1,dsc+dnum+1),dnum=unique(dsc+1,dsc+dnum+1)-dsc-1;
    tot=0;
    for(int i=1;i<=m;i++)
        if(opt[i]==1)
        {
            ++tot,Y[tot]=lower_bound(dsc+1,dsc+dnum+1,Y[tot])-dsc;
            ++tot,Y[tot]=lower_bound(dsc+1,dsc+dnum+1,Y[tot])-dsc;
        }
        else
        {
            tot+=2,Y[tot-1]=Y[tot]=lower_bound(dsc+1,dsc+dnum+1,Y[tot])-dsc;
            tot+=2,Y[tot-1]=Y[tot]=lower_bound(dsc+1,dsc+dnum+1,Y[tot])-dsc;
        }
    for(int i=1;i<=tot;i++) Q[i]=i;
    CDQ(1,tot,2);
    tot=dnum=0;
    for(int i=1;i<=m;i++)
        if(opt[i]==1)
        {
            //x y d w
            ui x=X1[i]+Y1[i],y=X2[i];
            ID[++tot]=-1,X[tot]=x,Y[tot]=y-1;
            val[tot][0]=Y2[i];
            val[tot][1]=Y2[i]*(-2*x-3);
            val[tot][2]=Y2[i]*(x+1)*(x+2);
            dsc[++dnum]=Y[tot];

            x=X1[i]-1,y=X2[i]+Y1[i]+1;
            ID[++tot]=-1,X[tot]=x,Y[tot]=y-1;
            val[tot][0]=-Y2[i];
            val[tot][1]=-Y2[i]*(-2*x-3);
            val[tot][2]=-Y2[i]*(x+1)*(x+2);
            dsc[++dnum]=Y[tot];
        }
        else
        {
            ui x=X1[i],y=Y1[i];
            ID[++tot]=i,X[tot]=x,Y[tot]=y;
            val[tot][0]=x*x;
            val[tot][1]=x;
            val[tot][2]=1;
            dsc[++dnum]=Y[tot];

            x=X2[i]+1,y=Y1[i];
            ID[++tot]=i,X[tot]=x,Y[tot]=y;
            val[tot][0]=-x*x;
            val[tot][1]=-x;
            val[tot][2]=-1;

            x=X1[i],y=Y2[i]+1;
            ID[++tot]=i,X[tot]=x,Y[tot]=y;
            val[tot][0]=-x*x;
            val[tot][1]=-x;
            val[tot][2]=-1;
            dsc[++dnum]=Y[tot];

            x=X2[i]+1,y=Y2[i]+1;
            ID[++tot]=i,X[tot]=x,Y[tot]=y;
            val[tot][0]=x*x;
            val[tot][1]=x;
            val[tot][2]=1;
        }
    sort(dsc+1,dsc+dnum+1),dnum=unique(dsc+1,dsc+dnum+1)-dsc-1;
    tot=0;
    for(int i=1;i<=m;i++)
        if(opt[i]==1)
        {
            ++tot,Y[tot]=lower_bound(dsc+1,dsc+dnum+1,Y[tot])-dsc;
            ++tot,Y[tot]=lower_bound(dsc+1,dsc+dnum+1,Y[tot])-dsc;
        }
        else
        {
            tot+=2,Y[tot-1]=Y[tot]=lower_bound(dsc+1,dsc+dnum+1,Y[tot])-dsc;
            tot+=2,Y[tot-1]=Y[tot]=lower_bound(dsc+1,dsc+dnum+1,Y[tot])-dsc;
        }
    for(int i=1;i<=tot;i++) Q[i]=i;
    CDQ(1,tot,2);
    tot=dnum=0;
    for(int i=1;i<=m;i++)
        if(opt[i]==1)
        {
            //x y d w
            ui x=X1[i]-1,y=X2[i]+Y1[i];
            ID[++tot]=-1,X[tot]=x,Y[tot]=y;
            val[tot][0]=-Y2[i]*2;
            val[tot][1]=-Y2[i]*(-2*y-2);
            val[tot][2]=-Y2[i]*(-2*x-2);
            val[tot][3]=-Y2[i]*2*(x+1)*(y+1);
            dsc[++dnum]=Y[tot];

            x=X1[i]-1,y=X2[i]-1;
            ID[++tot]=-1,X[tot]=x,Y[tot]=y;
            val[tot][0]=Y2[i]*2;
            val[tot][1]=Y2[i]*(-2*y-2);
            val[tot][2]=Y2[i]*(-2*x-2);
            val[tot][3]=Y2[i]*2*(x+1)*(y+1);
            dsc[++dnum]=Y[tot];
        }
        else
        {
            ui x=X1[i],y=Y1[i];
            ID[++tot]=i,X[tot]=x,Y[tot]=y;
            val[tot][0]=x*y;
            val[tot][1]=x;
            val[tot][2]=y;
            val[tot][3]=1;
            dsc[++dnum]=Y[tot];

            x=X2[i]+1,y=Y1[i];
            ID[++tot]=i,X[tot]=x,Y[tot]=y;
            val[tot][0]=-x*y;
            val[tot][1]=-x;
            val[tot][2]=-y;
            val[tot][3]=-1;

            x=X1[i],y=Y2[i]+1;
            ID[++tot]=i,X[tot]=x,Y[tot]=y;
            val[tot][0]=-x*y;
            val[tot][1]=-x;
            val[tot][2]=-y;
            val[tot][3]=-1;
            dsc[++dnum]=Y[tot];

            x=X2[i]+1,y=Y2[i]+1;
            ID[++tot]=i,X[tot]=x,Y[tot]=y;
            val[tot][0]=x*y;
            val[tot][1]=x;
            val[tot][2]=y;
            val[tot][3]=1;
        }
    sort(dsc+1,dsc+dnum+1),dnum=unique(dsc+1,dsc+dnum+1)-dsc-1;
    tot=0;
    for(int i=1;i<=m;i++)
        if(opt[i]==1)
        {
            ++tot,Y[tot]=lower_bound(dsc+1,dsc+dnum+1,Y[tot])-dsc;
            ++tot,Y[tot]=lower_bound(dsc+1,dsc+dnum+1,Y[tot])-dsc;
        }
        else
        {
            tot+=2,Y[tot-1]=Y[tot]=lower_bound(dsc+1,dsc+dnum+1,Y[tot])-dsc;
            tot+=2,Y[tot-1]=Y[tot]=lower_bound(dsc+1,dsc+dnum+1,Y[tot])-dsc;
        }
    for(int i=1;i<=tot;i++) Q[i]=i;
    CDQ(1,tot,3);
    for(int i=1;i<=m;i++) if(opt[i]==2) Print((ans[i]<<1)>>2),putchar('\n');
    return 0;
}