- 题意 : 四种操作,1. 区间加,2. 区间乘,3. 区间更新为固定值,
4.求区间(p)次方和,(p)取值(1到3) - 思路 : 维护前三种操作的懒标记,注意相互之间的影响.对询问,因为只有三种,直接对三种和都进行维护
#include<bits/stdc++.h>
#define ll long long
#define FOR(i,l,r) for(int i = l ; i <= r ;++i )
#define inf 0x3f3f3f3f
#define EPS (1e-9)
#define ALL(T) T.begin(),T.end()
#define lson(i) i<<1
#define rson(i) (i<<1|1)
#define sum(i,j) seg[i].sum[j]
using namespace std;
const int modp = 10007;
const int maxn = 1e6+50;
ll a[maxn];
ll ans = 0;
struct node{
int l,r;
ll val,add,mul;
ll sum[3];
}seg[maxn*4];
inline void madd(ll &a,ll b){
a = (a+b)%modp;
}
inline void mmul(ll &a,ll b){
a = (a*b)%modp;
}
inline void push_up(int p){
sum(p,0) = (sum(lson(p),0) + sum(rson(p),0))%modp;
sum(p,1) = (sum(lson(p),1) + sum(rson(p),1))%modp;
sum(p,2) = (sum(lson(p),2) + sum(rson(p),2))%modp;
}
inline void push_down(int p){
if(seg[p].val){
seg[lson(p)].val = seg[p].val;
seg[lson(p)].add = 0;
seg[lson(p)].mul = 1;
seg[rson(p)].val = seg[p].val;
seg[rson(p)].add = 0;
seg[rson(p)].mul = 1;
ll len = seg[p].r - seg[p].l + 1 ;
ll lsize = len - len/2 , rsize = len/2;
sum(lson(p),0) = (seg[p].val * lsize)%modp;
sum(rson(p),0) = (seg[p].val * rsize)%modp;
ll qp = (seg[p].val*seg[p].val)%modp;
sum(lson(p),1) = (qp * lsize)%modp;
sum(rson(p),1) = (qp * rsize)%modp;
qp = (qp*seg[p].val)%modp;
sum(lson(p),2) = (qp * lsize)%modp;
sum(rson(p),2) = (qp * rsize)%modp;
seg[p].val = 0;
}
// 乘法标记
if(seg[p].mul!=1){
mmul(seg[lson(p)].mul,seg[p].mul);
mmul(seg[rson(p)].mul,seg[p].mul);
mmul(seg[lson(p)].add,seg[p].mul);
mmul(seg[rson(p)].add,seg[p].mul);
mmul(sum(lson(p),0),seg[p].mul);
mmul(sum(rson(p),0),seg[p].mul);
ll q = (seg[p].mul*seg[p].mul)%modp;
mmul(sum(lson(p),1),q);
mmul(sum(rson(p),1),q);
mmul(q,seg[p].mul);
mmul(sum(lson(p),2),q);
mmul(sum(rson(p),2),q);
seg[p].mul = 1;
}
// 加法标记
if(seg[p].add){
madd(seg[lson(p)].add,seg[p].add);
madd(seg[rson(p)].add,seg[p].add);
ll val = seg[p].add;
ll len = seg[p].r - seg[p].l + 1 ;
ll lsize = len - len/2 , rsize = len/2;
ll q2 =(val*val)%modp,q3 = (q2*val)%modp;
madd(sum(lson(p),2),
(lsize*q3)%modp + 3 * val * ((sum(lson(p),1) + sum(lson(p),0)*val)%modp));
madd(sum(rson(p),2),
(rsize*q3)%modp + 3 * val * ((sum(rson(p),1) + sum(rson(p),0)*val)%modp));
madd(sum(lson(p),1),(lsize*q2)%modp+2*(sum(lson(p),0)*val)%modp);
madd(sum(rson(p),1),(rsize*q2)%modp+2*(sum(rson(p),0)*val)%modp);
madd(sum(lson(p),0),(lsize*val));
madd(sum(rson(p),0),(rsize*val));
seg[p].add = 0;
}
}
void build(int p,int l,int r){
seg[p].l = l;
seg[p].r = r;
seg[p].add = 0;
seg[p].mul = 1;
seg[p].val = 0;
seg[p].sum[0] = seg[p].sum[1] = seg[p].sum[2] = 0;
if(l==r) return;
int mid = (l+r)>>1;
build(lson(p),l,mid);
build(rson(p),mid+1,r);
push_up(p);
}
// 乘法操作
void mul(int i,int l,int r,ll val){
if(seg[i].l >=l && seg[i].r <=r){
// 直接更新当前区间
mmul(seg[i].add,val);
mmul(seg[i].mul,val);
// 乘法 可以提取公因数
mmul(sum(i,0),val);
mmul(sum(i,1),(val*val)%modp);
mmul(sum(i,2),(((val*val)%modp)*val)%modp);
return ;
}
push_down(i);
int mid = (seg[i].l + seg[i].r)>>1;
if(l<=mid) mul(lson(i),l,r,val);
if(r>mid) mul(rson(i),l,r,val);
push_up(i);
}
// 加法操作
void add(int i,int l,int r,ll val){
if(seg[i].l >=l && seg[i].r <=r){
madd(seg[i].add,val);
ll len = seg[i].r-seg[i].l+1;
ll q2 = (val*val)%modp, q3 = (q2*val)%modp;
madd(sum(i,2),q3*len+3*val*(sum(i,1)+sum(i,0)*val));
madd(sum(i,1),(q2*len+2*(sum(i,0)*val)%modp)%modp);
madd(sum(i,0),(len*val)%modp);
return ;
}
push_down(i);
int mid = (seg[i].l + seg[i].r)>>1;
if(l<=mid) add(lson(i),l,r,val);
if(r>mid) add(rson(i),l,r,val);
push_up(i);
}
// 区间更新固定值
void cha(int i,int l,int r,ll val){
if(seg[i].l >=l && seg[i].r <=r){
ll len = seg[i].r - seg[i].l + 1 ;
seg[i].val = val;
sum(i,0) = seg[i].val;
mmul(sum(i,0),len);
sum(i,1) = seg[i].val;
mmul(sum(i,1),sum(i,1));
mmul(sum(i,1),len);
sum(i,2) = sum(i,1);
mmul(sum(i,2),val);
seg[i].add = 0;
seg[i].mul = 1;
return ;
}
push_down(i);
int mid = (seg[i].l + seg[i].r)>>1;
if(l<=mid) cha(lson(i),l,r,val);
if(r>mid) cha(rson(i),l,r,val);
push_up(i);
}
ll query(int i,int l,int r,ll val){
ll res = 0;
if(seg[i].l >= l && seg[i].r <= r){
return sum(i,val-1);
}
push_down(i);
int mid = (seg[i].l+seg[i].r)>>1;
if(l<=mid) madd(res,query(lson(i),l,r,val)) ;
if(r>mid) madd(res,query(rson(i),l,r,val));
return res;
}
int n,m;
void solve(){
build(1,1,n);
ll op,x,y,z;
FOR(i,1,m){
scanf("%lld%lld%lld%lld",&op,&x,&y,&z);
switch(op){
case 1: add(1,x,y,z); break;
case 2: mul(1,x,y,z); break;
case 3: cha(1,x,y,z); break;
case 4: printf("%lld
",query(1,x,y,z));
}
}
}
int main(){
while(cin >> n >> m){
if(n==0 && m == 0) break;
solve();
}
return 0;
}
/*
6 9
3 2 6 10
1 1 2 6
1 2 2 1
2 6 6 7
4 1 2 3
10000 100
2 56 59 100
1 564 1254 10000
2 7 800 2
3 1 600 9999
4 5 10000 3
2 102 5645 9999
4 568 789 3
4 1 2 1
4 500 1000 1
4 500 1000 2
4 500 1000 3
附带数据^_^
*/
调bug调了一下午,这种长度的代码一定要理清思路在写,不然会越写越乱,bug百出QAQ狗屎代码就是恶心自己吧
- 区间加, 对其他两种操作没有影响
- 区间乘, 对区间加有影响,加法标记要乘上乘法标记
- 区间更新固定值, 区间加,乘都不在起作用,直接清零
- 区间和: (sum{a_i})
- +d: (sum_l^r{(a_i+d)} = sum_l^r{a_i}+(r-l+1)*d)
- *d: (sum{(a_i*d)} = d*sum{a_i}) 直接提取公因数
- =d: 因为(a_i = d),所以(sum_l^r{a_i} = d*(r-l+1))
- 区间平方和: (sum{a_i^2})
- +d: 展开和式,(sum_l^r(a_i+d)^2 = sum{a_i^2}+2dsum{a_i}+(r-l+1)*d^2)
- *d: (sum{(a_i*d)^2} = d^2*sum{a_i^2}) 直接提取公因数
- =d: (sum_l^r{a_i^2} = d^2*(r-l+1))
- 区间立方和: (sum{a_i^3})
- +d: 展开和式,(sum_l^r(a_i+d)^3 = sum{a_i^3}+2d(sum{a_i^2}+d*sum{a_i})+(r-l+1)*d^3)
- *d: (sum{(a_i*d)^3} = d^3*sum{a_i^3}) 直接提取公因数
- =d: (sum_l^r{a_i^3} = d^3*(r-l+1))
因为高次项要用到低次项,所以要先更新高次项.
=d时长度只用乘一次,写的时候没注意结果wa哭