15011418730 LV 7 @ 2025-8-24 23:08:54

自动搬运

来自洛谷，原作者为

	Seauy I remember your song, sung by centuries of wind.

搬运于2025-08-24 23:08:54，当前版本为作者最后更新于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;
}

ID

11396

时间

3000ms

内存

512MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

[Ynoi Easy Round 2025] TEST_139

信息

1 条题解

自动搬运

以下是正文

[Ynoi Easy Round 2025] TEST_139

信息

还没有账户？

登录