题目描述
Description
Input
Output
输出 q 行，第 i 行表示数据 Di 的答案。
Sample Input
4 3 2
1 1 2 4
2 1 2
1 1 3 5
2 2 3
Sample Output
0
4
14
22
Data Constraint
题解
显然cdq+线段树，计算加上每个操作的贡献
修改取决于之后的询问，询问取决于之前的修改
然而线段树会T，所以用树状数组差分一下
开两个树状数组，询问1~t表示成s1+s2*t，修改t就在t处的s1减(t-1)*s,在s2加s
code
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define low(x) (x&-(x))
using namespace std;
struct type{
int type,l,r,s,t,id;
} a[200001];
long long ans[200001];
long long tr[200001];
long long Tr[200001]; //*t
bool bz[200001];
int d[200001];
int n,Q,i,j,k,l,t,len;
bool cmp(type a,type b)
{
return a.t<b.t;
}
bool Cmp(type a,type b)
{
return a.id<b.id;
}
void Change(int t,int s)
{
long long S=(long long)(t-1)*s;
while (t<=n)
{
tr[t]-=S;
Tr[t]+=s;
if (!bz[t])
bz[t]=1,d[++len]=t;
t+=low(t);
}
}
void change(int l,int r,int s)
{
Change(l,s);
Change(r+1,-s);
}
long long Find(int t)
{
long long T=t,ans=0,s=0;
while (t)
{
ans+=tr[t];
s+=Tr[t];
t-=low(t);
}
return ans+s*T;
}
long long find(int l,int r)
{
return Find(r)-Find(l-1);
}
void clear()
{
int i;
fo(i,1,len)
tr[d[i]]=0,Tr[d[i]]=0,bz[d[i]]=0;
len=0;
}
void work(int L,int R)
{
int i,Mid=(L+R)/2;
if (L==R) return;
work(L,Mid);
work(Mid+1,R);
sort(a+L,a+R+1,Cmp);
fo(i,L,R)
if (a[i].t<=Mid && a[i].type==1)
change(a[i].l,a[i].r,a[i].s);
else
if (a[i].t>Mid && a[i].type==2)
ans[a[i].t]+=find(a[i].l,a[i].r);
clear();
fd(i,R,L)
if (a[i].t<=Mid && a[i].type==2)
change(a[i].l,a[i].r,1);
else
if (a[i].t>Mid && a[i].type==1)
ans[a[i].t]+=find(a[i].l,a[i].r)*a[i].s;
clear();
}
int main()
{
freopen("generator.in","r",stdin);
freopen("generator.out","w",stdout);
scanf("%d%d",&n,&Q);
fo(i,1,Q-1)
{
scanf("%d",&j);
a[j].t=i;
}
fo(i,1,Q)
{
scanf("%d",&a[i].type);
if (a[i].type==1)
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].s);
else
scanf("%d%d",&a[i].l,&a[i].r);
a[i].id=i;
++a[i].t;
}
sort(a+1,a+Q+1,cmp);
work(1,Q);
fo(i,1,Q)
{
ans[i]+=ans[i-1];
printf("%lld\n",ans[i]);
}
fclose(stdin);
fclose(stdout);
return 0;
}