COGS 2633. [HZOI 2016] 数列操作e

【题目描述】

一个长度为n的序列，一开始序列数的权值都是0,有m次操作

支持两种操作，

1 L R x，给区间[L,R]内,第一个数加x,第二个数加2^{2⋅x,第三个数加3}2⋅x...第R-L+1个数加(R−L+1)^2⋅x

2 L R 查询区间[L,R]内的权值和

每次询问的答案对264取模

【输入格式】

第一行两个数n，m，表示序列长度和操作次数

接下来m行，每行描述一个操作，有如下两种情况：

1 L R x，给区间[L,R]内,第一个数加x,第二个数加2^{2⋅x,第三个数加3}2⋅x...第R-L+1个数加(R−L+1)^2⋅x

2 L R 查询区间[L,R]内的权值和

【输出格式】

为了减少输出，你只需要输出所有答案对2^64取膜之后的异或和。

【样例输入】

5 5

1 3 4 1

2 1 5

2 2 2

1 3 3 1

1 2 4 1

【样例输出】

5

【提示】

对于10%的数据 n，m<=2000

对于30%的数据 n,m<=10000

对于100%的数据，n，m<=100000,1<=L<=R<=n,0<=x<=109

小技巧：对2^64取膜可以使用unsigned long long 的自然溢出

为了卡上榜使用标记永久化

我们先拆开(i-(L-1))^2⋅x，变成

i^2x - 2i(l+1)x + (L-1)^2*x

再变成

i^2x + 2i(1-l)x + (L-1)^2*x

接着，我们发现，第三项是一个常数项

第二项i的次数是1，第一项i的次数是2

我们就预处理i的前缀和和i*i的前缀和

于是我们开3个lazy数组，第一个保存 x ,第二个保存 2(1-l)x ，第三个保存常数(L-1)^2*x

在查询的时候，把lazy1的数字乘上i*i的前缀和，第二个乘上i的前缀和，第三个直接乘区间长度

由于是标记永久化，我们计算完标记的贡献之后还要加上两个儿子的贡献

解。

#include<bits/stdc++.h>

#define ll unsigned long long

#define inf 0x7fffffff

#define maxn 200009

#define mid ((l+r)>>1)

using namespace std;

int n,m,cnt;

int ls[maxn],rs[maxn];

ll S1[maxn],S2[maxn];

ll ans=0;

ll lz0[maxn],lz1[maxn],lz2[maxn],sum[maxn];

void Build(int &rt,int l,int r)

{

	if(rt==0)rt=++cnt;

	if(l==r)return;

	Build(ls[rt],l,mid),Build(rs[rt],mid+1,r);

}

void Add(int rt,int l,int r,int s,int t,ll x2,ll x1,ll x0)

{

	if(s>r||t<l)return;

	if(s<=l&&r<=t)

	{

		lz2[rt]+=x2,lz1[rt]+=x1,lz0[rt]+=x0;

		sum[rt]=sum[ls[rt]]+sum[rs[rt]]+lz2[rt]*(S2[r]-S2[l-1])+lz1[rt]*(S1[r]-S1[l-1])+lz0[rt]*(r-l+1);

		return;

	}

	Add(ls[rt],l,mid,s,t,x2,x1,x0);

	Add(rs[rt],mid+1,r,s,t,x2,x1,x0);

	sum[rt]=sum[ls[rt]]+sum[rs[rt]]+lz2[rt]*(S2[r]-S2[l-1])+lz1[rt]*(S1[r]-S1[l-1])+lz0[rt]*(r-l+1);

}

ll Sum(int rt,int l,int r,int s,int t)

{

	if(s>r||t<l)return 0;

	if(s<=l&&r<=t)return sum[rt];

	int LL=max(l,s),RR=min(r,t);//交叉区间

	return Sum(ls[rt],l,mid,s,t)+Sum(rs[rt],mid+1,r,s,t)+lz2[rt]*(S2[RR]-S2[LL-1])+lz1[rt]*(S1[RR]-S1[LL-1])+lz0[rt]*(RR-LL+1);

}

int RT;

signed main()

{

	freopen("rneaty.in","r",stdin);

	freopen("rneaty.out","w",stdout);

	scanf("%d%d",&n,&m);

	Build(RT,1,n);

	for(int i=1;i<=n;i++)S1[i]=S1[i-1]+i,S2[i]=S2[i-1]+i*1ull*i;

	while(m--)

	{

		int cz,l,r;

		scanf("%d%d%d",&cz,&l,&r);

		if(cz==1)

		{

			ll x;

			scanf("%llu",&x);

			Add(1,1,n,l,r,x,x*2*(1ull-l),(l-1)*x*(l-1));

			//i^2*x  + i*2(1-L)*x  +(L-1)^2*x

		}else

		{

			ans^=Sum(1,1,n,l,r);

		}

	}

	printf("%llu\n",ans);

	return 0;

}

巴特西

COGS 2633. [HZOI 2016] 数列操作e

最新文章

热门文章