题意
对于100%的数据，(n,m leq 10^5)
分析
考场上打挂了。
- 最大值就是后半部分和减前半部分和。
- 最小是就是奇偶相减。
- 方案数类似进出栈序，就是catalan数
线段树维护即可，时间复杂度(O(n log n+m log n))
代码
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<complex>
#define rg register
#define il inline
#define co const
#pragma GCC optimize ("O0")
using namespace std;
template<class T> il T read()
{
T data=0;
int w=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')
w=-1;
ch=getchar();
}
while(isdigit(ch))
data=10*data+ch-'0',ch=getchar();
return data*w;
}
template<class T> il T read(T&x)
{
return x=read<T>();
}
typedef long long ll;
const int INF=0x7fffffff;
const int MAXN=1e6+7,mod=1e9+7;
int a[MAXN],fac[MAXN],inv[MAXN];
il int catalan(rg int x)
{
return (ll)fac[2*x]*inv[x]%mod*inv[x]%mod*a[x+1]%mod;
}
struct node
{
int len;
int sumv[3]; // edit 1
// 0 1 2
// odd,even,all
il node()=default;
il node operator+(rg co node&rhs)const
{
rg node res;
res.len=len+rhs.len;
res.sumv[0]=(sumv[0]+rhs.sumv[len&1])%mod;
res.sumv[1]=(sumv[1]+rhs.sumv[!(len&1)])%mod;
res.sumv[2]=(sumv[2]+rhs.sumv[2])%mod;
return res;
}
il void add(rg int v)
{
(sumv[0]+=(ll)(len+1)/2*v%mod)%=mod;
(sumv[1]+=(ll)len/2*v%mod)%=mod; // edit 2
(sumv[2]+=(ll)len*v%mod)%=mod;
}
};
int ql,qr,v;
struct SegTree
{
node data[MAXN<<2];
int addv[MAXN<<2];
#define lson (now<<1)
#define rson (now<<1|1)
il void build(rg int now,rg int l,rg int r)
{
if(l==r)
{
data[now].len=1;
data[now].sumv[0]=data[now].sumv[2]=read<int>();
return;
}
rg int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
data[now]=data[lson]+data[rson];
}
il void pushdown(rg int now)
{
if(addv[now])
{
data[lson].add(addv[now]);
(addv[lson]+=addv[now])%=mod;
data[rson].add(addv[now]);
(addv[rson]+=addv[now])%=mod;
addv[now]=0;
}
}
il void add(rg int now,rg int l,rg int r)
{
// fprintf(stderr,"a %d %d %d
",now,l,r);
if(ql<=l&&r<=qr)
{
data[now].add(v);
(addv[now]+=v)%=mod;
return;
}
pushdown(now);
rg int mid=(l+r)>>1;
if(ql<=mid)
add(lson,l,mid);
if(qr>=mid+1)
add(rson,mid+1,r);
data[now]=data[lson]+data[rson];
}
il node query(rg int now,rg int l,rg int r)
{
// fprintf(stderr,"q %d %d %d
",now,l,r);
if(ql<=l&&r<=qr)
{
return data[now];
}
pushdown(now);
rg int mid=(l+r)>>1;
if(qr<=mid)
return query(lson,l,mid);
if(ql>=mid+1)
return query(rson,mid+1,r);
return query(lson,l,mid)+query(rson,mid+1,r);
}
}T;
int main()
{
freopen("sort.in","r",stdin);
freopen("sort.out","w",stdout);
rg int n=read<int>(),m=read<int>();
n*=2;
a[1]=1,fac[1]=1,inv[1]=1;
a[0]=1,fac[0]=1,inv[0]=1;
for(rg int i=2;i<=n;++i)
{
a[i]=((ll)-(mod/i)*a[mod%i]%mod+mod)%mod;
fac[i]=(ll)fac[i-1]*i%mod;
inv[i]=(ll)inv[i-1]*a[i]%mod;
// fprintf(stderr,"%d a=%d fac=%d inv=%d
",i,a[i],fac[i],inv[i]);
}
T.build(1,1,n);
// fprintf(stderr,"build end
");
while(m--)
{
rg int opt,l,r;
read(opt);
if(opt==1)
{
read(l);read(r);
rg int mid=(l+r)>>1;
ql=l,qr=mid;
rg int le=T.query(1,1,n).sumv[2];
// fprintf(stderr,"le=%d
",le);
ql=mid+1,qr=r;
rg int ri=T.query(1,1,n).sumv[2];
// fprintf(stderr,"ri=%d
",ri);
ql=l,qr=r;
node ans=T.query(1,1,n);
// fprintf(stderr,"odd=%d even=%d
",ans.sumv[0],ans.sumv[1]);
printf("%d %d %d
",(ri+mod-le)%mod,(ans.sumv[1]+mod-ans.sumv[0])%mod,catalan((qr-ql+1)/2));
}
else if(opt==0)
{
read(ql);read(qr);read(v);
T.add(1,1,n);
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}