【题目描述】
一个长度为n的序列，一开始序列数的权值都是0,有m次操作
支持两种操作，
1 L R x，给区间[L,R]内,第一个数加x,第二个数加22⋅x,第三个数加32⋅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,第二个数加22⋅x,第三个数加32⋅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
",ans);
return 0;
}