3188: [Coci 2011]Upit
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 72 Solved: 24
[Submit][Status]
Description
你需要维护一个序列，支持以下4种操作。一，将区间(u,v)的数覆盖为C；二，
将区间(u,v)的数依次加上一个以C为首项、C为公差的等差数列；三，将数C插入
第i个位置；四，查询区间(u,v)的数的和。序列最初有n个数，一共会有Q次操
作。保证结果在longlong范围内。
Input
Output
Sample Input
5 5
1 2 3 4 5
1 5 5 0
4 4 5
4 5 5
2 1 5 1
4 1 5
1 2 3 4 5
1 5 5 0
4 4 5
4 5 5
2 1 5 1
4 1 5
Sample Output
4
0
25
0
25
HINT
n, Q <= 100,000.
Source
题解：
问题主要在操作2
如果我们给l-r加上一个以x为首项，y为公差的等差数列，v[k]和sum[k]都很容易计算。
我们发现两次的操作是可以合并的 加上以x1为首项，y1为公差，再加上x2为首项，y2为公差，相当于加上了一个以x1+x2为首项，以y1+y2为公差的等差数列，这样我们就可以打lazy了！
然后剩下的就是注意两个lazy的下传顺序了。
代码：
问题主要在操作2
如果我们给l-r加上一个以x为首项，y为公差的等差数列，v[k]和sum[k]都很容易计算。
我们发现两次的操作是可以合并的 加上以x1为首项，y1为公差，再加上x2为首项，y2为公差，相当于加上了一个以x1+x2为首项，以y1+y2为公差的等差数列，这样我们就可以打lazy了！
然后剩下的就是注意两个lazy的下传顺序了。
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 500000+5
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,q,rt,t1,t2,tot,fa[maxn],c[maxn][];
ll s[maxn],sum[maxn],v[maxn],tag[maxn][];
inline void pushup(int x)
{
int l=c[x][],r=c[x][];
s[x]=s[l]+s[r]+;
sum[x]=sum[l]+sum[r]+v[x];
}
inline void rotate(int x,int &k)
{
int y=fa[x],z=fa[y],l=c[y][]==x,r=l^;
if(y!=k)c[z][c[z][]==y]=x;else k=x;
fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
pushup(y);pushup(x);
}
inline void splay(int x,int &k)
{
while(x!=k)
{
int y=fa[x],z=fa[y];
if(y!=k)
{
if(c[z][]==y^c[y][]==x)rotate(x,k);else rotate(y,k);
}
rotate(x,k);
}
}
inline void change(int x,ll z)
{
sum[x]=s[x]*z;v[x]=z;
tag[x][]=;tag[x][]=z;
tag[x][]=tag[x][]=;
}
inline void update(int x,ll y,ll z)
{
int l=c[x][],r=c[x][];
v[x]+=y+s[l]*z;
sum[x]+=s[x]*y+s[x]*(s[x]-)/(ll)*z;
tag[x][]+=y;tag[x][]+=z;
}
inline void pushdown(int x)
{
int l=c[x][],r=c[x][];
if(tag[x][]){change(l,tag[x][]);change(r,tag[x][]);tag[x][]=;}
if(tag[x][]||tag[x][])
{
update(l,tag[x][],tag[x][]);
update(r,tag[x][]+(s[l]+)*tag[x][],tag[x][]);
tag[x][]=tag[x][]=;
}
}
inline int find(int x,int k)
{
pushdown(x);
int l=c[x][],r=c[x][];
if(s[l]+==k)return x;
else if(s[l]>=k)return find(l,k);
else return find(r,k-s[l]-);
}
inline void split(int l,int r)
{
t1=find(rt,l);t2=find(rt,r);
splay(t1,rt);splay(t2,c[t1][]);
}
inline void build(int l,int r,int f)
{
if(l>r)return;
int x=(l+r)>>;
fa[x]=f;c[f][x>f]=x;
if(l==r){s[x]=;sum[x]=v[x];return;}
build(l,x-,x);build(x+,r,x);
pushup(x);
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();q=read();
for2(i,,n+)v[i]=read();tot=n+;rt=(+n+)>>;
build(,n+,);
while(q--)
{
int ch=read();
if(ch==){int x=read();split(x,x+);fa[c[t2][]=++tot]=t2;sum[tot]=v[tot]=read();s[tot]=;}
else
{
int x=read(),y=read();
split(x,y+);
if(ch==)change(c[t2][],read());
else if(ch==)printf("%lld\n",sum[c[t2][]]);
else
{
ll z=read();update(c[t2][],z,z);
}
}
pushup(t2);pushup(t1);
}
return ;
}