好，这是一个线段树模板。
#include <cstdio>
using namespace std;
const long long int N=;
long long int sum[N],tag1[N],tag2[N],mo; void build(int l,int r,int o)
{
tag1[o]=;
if(l==r)
{
scanf ("%d",&sum[o]);
return;
}
int mid=(l+r)>>;
build(l,mid,o<<);
build(mid+,r,o<<|);
sum[o]=(sum[o<<]+sum[o<<|])%mo;
return;
}
void down(int l,int r,int o)
{
tag1[o<<]=tag1[o<<]*tag1[o]%mo;
tag1[o<<|]=tag1[o<<|]*tag1[o]%mo;
tag2[o<<]=(tag2[o<<]*tag1[o]+tag2[o])%mo;
tag2[o<<|]=(tag2[o<<|]*tag1[o]+tag2[o])%mo;
int mid=(l+r)>>;
sum[o<<]=(sum[o<<]*tag1[o]+tag2[o]*(mid-l+))%mo;
sum[o<<|]=(sum[o<<|]*tag1[o]+tag2[o]*(r-mid))%mo;
tag1[o]=;
tag2[o]=;
return;
} void add(int L,int R,int v,int l,int r,int o)
{
if(L<=l && r<=R)
{
tag2[o]=(tag2[o]+v)%mo;
sum[o]=(sum[o]+v*(r-l+))%mo;
return;
}
if(r<L || R<l) return;
down(l,r,o);
int mid=(l+r)>>;
if(L<=mid) add(L,R,v,l,mid,o<<);
if(mid<R) add(L,R,v,mid+,r,o<<|);
sum[o]=(sum[o<<]+sum[o<<|])%mo;
return;
}
void mul(int L,int R,int v,int l,int r,int o)
{
if(L<=l && r<=R)
{
tag1[o]=tag1[o]*v%mo;
tag2[o]=tag2[o]*v%mo;
sum[o]=sum[o]*v%mo;
return;
}
if(r<L || R<l) return;
down(l,r,o);
int mid=(l+r)>>;
if(L<=mid) mul(L,R,v,l,mid,o<<);
if(mid<R) mul(L,R,v,mid+,r,o<<|);
sum[o]=(sum[o<<]+sum[o<<|])%mo;
return;
}
long long int ask_sum(int L,int R,int l,int r,int o)
{
if(L<=l && r<=R) return sum[o];
if(r<L || R<l) return ;
int mid=(l+r)>>;
down(l,r,o);
long long int ans=ask_sum(L,R,l,mid,o<<);
ans=ans+ask_sum(L,R,mid+,r,o<<|)%mo;
sum[o]=(sum[o<<]+sum[o<<|])%mo;
return ans%mo;
}
int main()
{
int n,m;
scanf ("%d%d%d",&n,&m,&mo);
build(,n,);
while(m--)
{
int flag,x,y,c;
scanf ("%d",&flag);
if(flag==)
{
scanf ("%d%d%d",&x,&y,&c);
mul(x,y,c,,n,);
}
else if(flag==)
{
scanf ("%d%d%d",&x,&y,&c);
add(x,y,c,,n,);
}
else
{
scanf ("%d%d",&x,&y);
printf("%lld\n",ask_sum(x,y,,n,));
}
}
return ;
}
模板在此
就这样。
2018.06.16
今天心血来潮准备打个线段树模板玩，结果调了TM一个多小时...
一交先是RE(我明明开足了4倍空间)，然后又T(你在打我脸)，最后加个快读终于A了，气死我了。
#include <cstdio>
typedef long long LL;
const int N = ; LL MO; inline void Read(LL &x) {
x = ;
char c = getchar();
while(c < '' || c > '') {
c = getchar();
}
while(c <= '' && c >= '') {
x = (x << ) + (x << ) + c - ;
c = getchar();
}
return;
} struct SegmentTree {
LL sum[N << ], tag1[N << ], tag2[N << ];
int l[N << ], r[N << ]; inline void update(int o) {
sum[o] = sum[o << ] + sum[o << | ] % MO;
return;
}
inline void pushdown(int o) {
if(!tag2[o] && tag1[o] == ) {
return;
} int ls = o << ;
int rs = ls | ;
int mid = (l[o] + r[o]) >> ; tag1[ls] = tag1[ls] * tag1[o] % MO;
tag2[ls] = (tag2[ls] * tag1[o] % MO + tag2[o]) % MO;
sum[ls] = (sum[ls] * tag1[o] % MO + tag2[o] * (mid - l[o] + ) % MO) % MO; tag1[rs] = tag1[rs] * tag1[o] % MO;
tag2[rs] = (tag2[rs] * tag1[o] % MO + tag2[o]) % MO;
sum[rs] = (sum[rs] * tag1[o] % MO + tag2[o] * (r[o] - mid) % MO) % MO; tag1[o] = ;
tag2[o] = ;
return;
}
void build(int o, int _l, int _r) {
l[o] = _l;
r[o] = _r;
tag1[o] = ;
tag2[o] = ;
if(_l == _r) {
Read(sum[o]);
sum[o] %= MO;
return;
}
int ls = o << ;
int rs = ls | ;
int mid = (_l + _r) >> ;
build(ls, _l, mid);
build(rs, mid + , _r);
update(o);
return;
}
void add(int L, int R, int o, LL v) {
if(L <= l[o] && r[o] <= R) {
tag2[o] = (v + tag2[o]) % MO;
sum[o] = (sum[o] + v * (r[o] - l[o] + ) % MO) % MO;
return;
}
if(r[o] < L || R < l[o]) {
return;
} pushdown(o);
int ls = o << ;
int rs = ls | ;
int mid = (l[o] + r[o]) >> ; if(L <= mid) {
add(L, R, ls, v);
}
if(mid < R) {
add(L, R, rs, v);
}
update(o);
return;
}
void mul(int L, int R, int o, LL v) {
if(L <= l[o] && r[o] <= R) {
tag1[o] = v * tag1[o] % MO;
tag2[o] = v * tag2[o] % MO;
sum[o] = (sum[o] * v) % MO;
return;
}
if(r[o] < L || R < l[o]) {
return;
} pushdown(o);
int ls = o << ;
int rs = ls | ;
int mid = (l[o] + r[o]) >> ; if(L <= mid) {
mul(L, R, ls, v);
}
if(mid < R) {
mul(L, R, rs, v);
}
update(o);
return;
}
LL ask(int L, int R, int o) {
if(L <= l[o] && r[o] <= R) {
return sum[o];
}
if(r[o] < L || R < l[o]) {
return ;
} pushdown(o);
int ls = o << ;
int rs = ls | ;
int mid = (l[o] + r[o]) >> ; LL ans = (ask(L, R, ls) + ask(L, R, rs)) % MO;
return ans;
}
}SegT; int main() {
int n, m;
scanf("%d%d%lld", &n, &m, &MO);
SegT.build(, , n);
for(int i = , x, y, f; i <= m; i++) {
scanf("%d%d%d", &f, &x, &y);
if(f == ) {
printf("%lld\n", SegT.ask(x, y, ));
}
else {
LL k;
scanf("%lld", &k);
if(f == ) {
SegT.mul(x, y, , k);
}
else {
SegT.add(x, y, , k);
}
}
} return ;
}
船新模板(加了快读居然还比上面那个慢)