版权属于舒老师，想要引用此题（包括题面）的朋友请联系博主
分析：
这道题是舒老师的原创题（版权声明~）
神题啊，毒瘤题啊
正解
首先，我们可以先忽略 n(n+1)2 n ( n + 1 ) 2 中的 2 2 ，最后再处理即可
我们将 n(n+1) n ( n + 1 ) 展开，得到 n2+n n 2 + n
我们可以把一个操作拆成两个：
① 对 [l,r] [ l , r ] 每个点加 dis2 d i s 2 （ dis d i s 为该点到l的距离+1）
② 对 [l,r] [ l , r ] 每个点加 dis d i s
（操作②这就让我想起一道题，相当于加上一条直线）
我们从简单的开始
操作②
在区间 [l,r] [ l , r ] 上加上一个等差数列： a1=1,d=1 a 1 = 1 , d = 1
在线段树众维护等差数列的首项和公差
在pushdown的时候，左儿子直接继承父结点的首项和公差，右儿子继承公差，计算一下首项即可
如果打标记时发生了标记覆盖，直接：首项1+首项2，公差1+公差2
操作①
显然我们没法合并 x2 x 2 的标记，考虑差分
n2−(n−1)2=2n−1 n 2 − ( n − 1 ) 2 = 2 n − 1
等差数列： a1=1,d=2 a 1 = 1 , d = 2 ，在线段树中维护首项和公差
如果是单点查询的话，我们查询前缀和即可（差分的运用）
如果是区间 [l,r],ans=∑ri=li2 [ l , r ] , a n s = ∑ i = l r i 2
设 a[i]=2i−1 a [ i ] = 2 i − 1
由上图（等高线地形图？？？）就可以看出：
a[1]−a[l] a [ 1 ] − a [ l ] 计算了 r−l+1 r − l + 1 次
a[l+1] a [ l + 1 ] 计算了 r−l r − l 次
... . . .
a[r] a [ r ] 计算了 1 1 次
我们定义C(l,r)C(l,r)
C(l,r)= C ( l , r ) =
a[l]+a[l+1]+a[l+2]+...a[r]+ a [ l ] + a [ l + 1 ] + a [ l + 2 ] + . . . a [ r ] +
a[l+1]+a[l+2]+...a[r]+ a [ l + 1 ] + a [ l + 2 ] + . . . a [ r ] +
a[l+2]+...a[r]+ a [ l + 2 ] + . . . a [ r ] +
... . . .
a[r] a [ r ]
那么 ans=∑ri=li2=∑l−1i=1a[i]∗(r−l+1)+C(l,r) a n s = ∑ i = l r i 2 = ∑ i = 1 l − 1 a [ i ] ∗ ( r − l + 1 ) + C ( l , r )
维护 C(l,r) C ( l , r )
update： C(l,r)=C(l,mid)+C(mid+1,r)+∑midi=la[i]∗(r−mid) C ( l , r ) = C ( l , m i d ) + C ( m i d + 1 , r ) + ∑ i = l m i d a [ i ] ∗ ( r − m i d )
方便起见，我们可以标记永久化
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
const int N=;
const ll p=e9+;
ll inv2,s1[N],s2[N];
int n,type,L,R,m,lastans=;
ll KSM(ll a,ll b) {
ll t=;
while (b) {
if (b&) t=(t*a)%p;
a=(a*a)%p;
b>>=;
}
return t%p;
}
void change_lr() {
L=(L+lastans-)%n+;
R=(R+lastans-)%n+;
if (L>R) swap(L,R);
}
struct node1{ //维护等差数列
struct tree1{
ll a,b,sum;
}t[N<<];
void update(int bh,int l,int r) {
t[bh].sum=t[bh<<].sum+t[bh<<|].sum; t[bh].sum%=p;
if (!t[bh].a&&!t[bh].b) return;
ll n=r-l+; //有标记就维护一下值
t[bh].sum+=(t[bh].a*n%p+t[bh].b*s1[n]%p)%p; t[bh].sum%=p;
}
void change(int bh,int l,int r,int L,int R,int a,int b) {
if (l>=L&&r<=R) {
t[bh].a+=a; t[bh].a%=p;
t[bh].b+=b; t[bh].b%=p;
update(bh,l,r);
return;
}
int mid=(l+r)>>;
if (L<=mid) change(bh<<,l,mid,L,R,a,b);
if (R>mid) change(bh<<|,mid+,r,L,R,(a+max(mid-max(l,L)+,)*b%p)%p,b);
update(bh,l,r);
}
ll ask(int bh,int l,int r,int L,int R,ll a,ll b) { //标记永久化的a和b
if (l>=L&&r<=R) {
return (t[bh].sum+a*(r-l+)%p+b*(s1[r-l+])%p)%p;
}
int mid=(l+r)>>;
a=(a+t[bh].a)%p; b=(b+t[bh].b)%p;
//标记永久化
ll ans=;
if (L<=mid) ans=(ans+ask(bh<<,l,mid,L,R,a,b)%p)%p;
if (R>mid) ans=(ans+ask(bh<<|,mid+,r,L,R,(a+(mid-l+)*b%p)%p,b)%p)%p;
//a+(mid-l+)*b 右儿子新首项
return ans;
}
};
node1 T1;
struct node2{
struct tree2{
ll a,b,sum,sum_2;
//sum sum(a[l]~a[r])
//sum_2 C(l,r)
}t[N<<];
void update(int bh,int l,int r) {
int mid=(l+r)>>;
int lc=bh<<;
int rc=bh<<|;
t[bh].sum=t[lc].sum+t[rc].sum; t[bh].sum%=p;
t[bh].sum_2=t[lc].sum_2+t[rc].sum_2; t[bh].sum_2%=p;
t[bh].sum_2+=t[lc].sum*(ll)(r-mid)%p; t[bh].sum_2%=p;
if (!t[bh].a&&!t[bh].b) return; //有标记就维护一下值
ll n=r-l+;
t[bh].sum+=(t[bh].a*n%p+t[bh].b*s1[n]%p)%p; t[bh].sum%=p;
t[bh].sum_2+=t[bh].a*s1[n]%p+t[bh].b*s1[n]%p*(n+)%p-s2[n]*t[bh].b%p;
//注意sum_2的维护
t[bh].sum_2%=p;
}
void change(int bh,int l,int r,int L,int R,ll a,ll b) {
if (l>=L&&r<=R) {
t[bh].a+=a; t[bh].a%=p;
t[bh].b+=b; t[bh].b%=p;
update(bh,l,r);
return;
}
int mid=(l+r)>>;
if (L<=mid) change(bh<<,l,mid,L,R,a,b);
if (R>mid) change(bh<<|,mid+,r,L,R,(a+max(mid-max(l,L)+,)*b%p)%p,b);
update(bh,l,r);
}
ll ask(int bh,int l,int r,int L,int R,ll s,ll a,ll b) {
if (l>=L&&r<=R) {
ll n=r-l+;
return (s*n%p+t[bh].sum_2+a*s1[n]%p+b*s1[n]%p*(n+)%p-b*s2[n]%p);
}
int mid=(l+r)>>;
a=(a+t[bh].a)%p; b=(b+t[bh].b)%p;
//标记永久化
ll ans=;
if (L<=mid) ans=(ans+ask(bh<<,l,mid,L,R,s,a,b))%p;
if (R>mid) ans=(ans+ask(bh<<|,mid+,r,L,R,(s+t[bh<<].sum+a*(mid-l+)%p+b*s1[mid-l+]%p)%p,(a+b*(mid-l+)%p)%p,b)%p)%p;
return ans%p;
}
};
node2 T2;
int main() {
char s[];
scanf("%d%d",&n,&type);
scanf("%d",&m);
inv2=KSM(,p-);
for (int i=;i<=n;i++) {
s1[i]=(s1[i-]+(ll)i)%p;
s2[i]=(s2[i-]+(ll)i*i)%p;
}
for (int i=;i<=m;i++) {
scanf("%s%d%d",s,&L,&R);
if (type) change_lr();
if (s[]=='C') {
T1.change(,,n,L,R,,); //a= b=
T2.change(,,n,L,R,-,); //a=- b=
if (R!=n) {
ll nn=R-L+;
T2.change(,,n,R+,R+,-nn*nn%p,);
}
}
else {
ll ans=(T1.ask(,,n,L,R,,)+T2.ask(,,n,L,R,,,))%p;
ans=(ans*inv2%p+p)%p;
lastans=ans%p;
printf("%lld\n",ans);
}
}
return ;
}
Enzymii解
预处理 mul[j]=∑ji=1i∗(i+1)2 m u l [ j ] = ∑ i = 1 j i ∗ ( i + 1 ) 2
分块（有点像块状链表）
code看不大懂，总的来说也是维护等差数列的首项和公差
zyz解
首先我们观察一下 i(i+1)2 i ( i + 1 ) 2 ，并且差分一下
有兴趣的可以看一下差分序列的相关资料
1 3 6 10 15
2 3 4 5
1 1 1
可以发现， i(i+1)2 i ( i + 1 ) 2 是一个二阶等差数列
我们用线段树维护一阶首项，二阶首项，二阶公差
如果打标记时发生了标记覆盖，直接对应相加即可
看一下如何计算序列中的第 pos p o s 项：
a1+b1∗pos+pos(pos−1)2∗d a 1 + b 1 ∗ p o s + p o s ( p o s − 1 ) 2 ∗ d