算法1
这个题的关键是将差分转化为区间
我们很容易想到:(以下 ti代表差分值,sum代表区间和)
sum[n]=t1+t1+t2+t1+t2+t3+…+tn;
化简成:sum[n]=nt1+(n-1)t2+..+(n-i+1)ti i~n;
由于这个题的常数随着i和n的变化而改变我们很难进行模拟,像这种有规律的累加我们最好用矩阵这样容易查找规律
sum[n]:
t1
t1 t2
t1 t2 t3
....
t1 t2 t3 t4…
我们求的就转化为上面的矩阵和了
将矩阵补全我们查找的值就变为了sum[n]=(t1+…+tn)*n-(t2+2t3+..+(n-1)tn);
只有一个变量n与区间和有关了这样就好进行程序模拟了
时间复杂度 mlogn;
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
typedef long long LL;
LL t[N],t2[N],a[N];// t tn,t2代标 (n-1)tn
int n;
int lowbit(int x) //求第一个前导1和后面的0代表的数
{
return x&-x;
}
void add(LL c,int k) //t的插入
{
for(int i=k;i<=n;i+=lowbit(i)) t[i]+=c;
}
void add2(LL c,int k) //t2的插入
{
for(int i=k;i<=n;i+=lowbit(i)) t2[i]+=c;
}
LL rsk(int k) //求和
{
LL res=0;
for(int i=k;i>0;i-=lowbit(i)) res+=t[i];//这里求和前往别写成>=0不然会卡死因为0的lowbit也是0会一直重复
return res;
}
LL rsk2(int k)
{
LL res=0;
for(int i=k;i>0;i-=lowbit(i)) res+=t2[i];
return res;
}
int main()
{
int m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
add(a[i]-a[i-1],i);add2((a[i]-a[i-1])*(i-1),i);
}
for(int i=1;i<=m;i++)
{
char c;
cin>>c;
if(c=='Q')
{
int l,r;
cin>>l>>r;
cout<<(rsk(r)*r-rsk2(r))-(rsk(l-1)*(l-1)-rsk2(l-1))<<endl;
}
else
{
int l,r,c;
cin>>l>>r>>c;
add(c,l);add2(c*(l-1),l);
add(-c,r+1);add2(-c*r,r+1); //这里插入也要乘上n-
}
}
}
同问,算法2呢
同问,算法二呢
算法2呢??