Transformation
http://acm.hdu.edu.cn/showproblem.php?pid=4578
题意：
//长度为n的数组 四个操作
//1 x y c [x,y]区间的数都加c
//2 x y c [x, y] 区间的数都乘以c
//3 x y c [x ,y] 区间的数都变为c
//4 x y p [x ,y] 求区间的数的p次方的和
题解：
这道题坑在有三种询问：set , add , mul。所以lazy标记要有三个，如果三个标记同时出现的处理方法——当更新set操作时，就把add标记和mul标记全部取消；当更新mul操作时，如果当前节点add标记存在，就把add标记改为：add * mul。这样的话就可以在PushDown()操作中先执行set，然后mul，最后add。
麻烦在有三种询问：和 , 平方和 , 立方和。对于set和mul操作来说，这三种询问都比较好弄。
对于add操作，和的话就比较好弄，按照正常方法就可以；
平方和这样来推：(a + c)2 = a2 + c2 + 2ac , 即sum2[rt] = sum2[rt] + (r - l + 1) * c * c + 2 * sum1[rt] * c；
立方和这样推：(a + c)3 = a3 + c3 + 3c(a2 + ac) , 即sum3[rt] = sum3[rt] + (r - l + 1) * c * c * c + 3 * c * (sum2[rt] + sum1[rt] * c)；
几个注意点：
- add标记取消的时候是置0，mul标记取消的时候是置1；
- 在PushDown()中也也要注意取消标记，如set操作中取消add和mul，mul操作中更新add；
- 在add操作中要注意sum3 , sum2 , sum1的先后顺序，一定是先sum3 , 然后sum2 , 最后sum1；
- int容易爆，还是用LL要保险一点；
- 最后就是运算较多，不要漏掉东西。
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=10000+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q,p;
int ans,cnt,flag,temp,sum;
ll tree[N<<2];
ll tree2[N<<2];
ll tree3[N<<2];
ll lazy1[N<<2];
ll lazy2[N<<2];
ll lazy3[N<<2];
char str;
struct node{};
ll POW(ll a,int b){
if (b==1) return a%MOD;
if (b==2) return a*a%MOD;
if (b==3) return a*a%MOD*a%MOD;
return 1;
}
void pushup(int rt){
tree[rt]=(tree[rt<<1]+tree[rt<<1|1])%MOD;
tree2[rt]=(tree2[rt<<1]+tree2[rt<<1|1])%MOD;
tree3[rt]=(tree3[rt<<1]+tree3[rt<<1|1])%MOD;
}
void pushdown(int l,int r,int rt){
if(lazy3[rt]){
int mid=(l+r)>>1;
int llen=(mid-l+1);
int rlen=(r-mid);
tree[rt<<1]=(llen*lazy3[rt])%MOD;
tree[rt<<1|1]=(rlen*lazy3[rt])%MOD;
tree2[rt<<1]=(llen*POW(lazy3[rt],2))%MOD;
tree2[rt<<1|1]=(rlen*POW(lazy3[rt],2))%MOD;
tree3[rt<<1]=(llen*POW(lazy3[rt],3))%MOD;
tree3[rt<<1|1]=(rlen*POW(lazy3[rt],3))%MOD;
lazy3[rt<<1|1]=lazy3[rt<<1]=lazy3[rt];
lazy3[rt]=0;
lazy1[rt<<1|1]=lazy1[rt<<1]=1;
lazy2[rt<<1|1]=lazy2[rt<<1]=0;
}
if(lazy1[rt]!=1){
tree[rt<<1]=(tree[rt<<1]*lazy1[rt])%MOD;
tree[rt<<1|1]=(tree[rt<<1|1]*lazy1[rt])%MOD;
tree2[rt<<1]=(tree2[rt<<1]*POW(lazy1[rt],2))%MOD;
tree2[rt<<1|1]=(tree2[rt<<1|1]*POW(lazy1[rt],2))%MOD;
tree3[rt<<1]=(tree3[rt<<1]*POW(lazy1[rt],3))%MOD;
tree3[rt<<1|1]=(tree3[rt<<1|1]*POW(lazy1[rt],3))%MOD;
lazy2[rt<<1]=(lazy2[rt<<1]*lazy1[rt])%MOD;
lazy2[rt<<1|1]=(lazy2[rt<<1|1]*lazy1[rt])%MOD;
lazy1[rt<<1]=(lazy1[rt<<1]*lazy1[rt])%MOD;
lazy1[rt<<1|1]=(lazy1[rt<<1|1]*lazy1[rt])%MOD;
lazy1[rt]=1;
}
if(lazy2[rt]){
int mid=(l+r)>>1;
int llen=(mid-l+1);
int rlen=(r-mid);
tree3[rt<<1]=(tree3[rt<<1]+(llen*POW(lazy2[rt],3))%MOD+3*lazy2[rt]*tree2[rt<<1]%MOD+3*POW(lazy2[rt],2)*tree[rt<<1]%MOD)%MOD;
tree3[rt<<1|1]=(tree3[rt<<1|1]+(rlen*POW(lazy2[rt],3))%MOD+3*lazy2[rt]*tree2[rt<<1|1]%MOD+3*POW(lazy2[rt],2)*tree[rt<<1|1]%MOD)%MOD;
tree2[rt<<1]=(tree2[rt<<1]+(llen*POW(lazy2[rt],2))%MOD+2*tree[rt<<1]*lazy2[rt]%MOD)%MOD;
tree2[rt<<1|1]=(tree2[rt<<1|1]+(rlen*POW(lazy2[rt],2))%MOD+2*tree[rt<<1|1]*lazy2[rt]%MOD)%MOD;
tree[rt<<1]=(tree[rt<<1]+(llen*lazy2[rt])%MOD)%MOD;
tree[rt<<1|1]=(tree[rt<<1|1]+(rlen*lazy2[rt])%MOD)%MOD;
lazy2[rt<<1]=(lazy2[rt<<1]+lazy2[rt])%MOD;
lazy2[rt<<1|1]=(lazy2[rt<<1|1]+lazy2[rt])%MOD;
lazy2[rt]=0;
}
}
void build(int l,int r,int rt){
lazy1[rt]=1;
lazy2[rt]=0;
lazy3[rt]=0;
if(l==r){
//scanf("%lld",&tree[rt]);
tree[rt]=0;
tree2[rt]=0;
tree3[rt]=0;
return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void updata(int l,int r,int rt,int L,int R,ll C,int op){
if(L<=l&&r<=R){
int len=r-l+1;
if(op==1){
tree[rt]=(tree[rt]*C)%MOD;
tree2[rt]=(tree2[rt]*POW(C,2))%MOD;
tree3[rt]=(tree3[rt]*POW(C,3))%MOD;
lazy2[rt]=(lazy2[rt]*C)%MOD;
lazy1[rt]=(lazy1[rt]*C)%MOD;
}else if(op==2){
tree3[rt]=(tree3[rt]+(len*POW(C,3))%MOD+3*C*tree2[rt]%MOD+3*POW(C,2)*tree[rt]%MOD)%MOD;
tree2[rt]=(tree2[rt]+(len*POW(C,2))%MOD+2*tree[rt]*C%MOD)%MOD;
tree[rt]=(tree[rt]+len*C)%MOD;
lazy2[rt]=(lazy2[rt]+C)%MOD;
}else{
tree[rt]=(len*C)%MOD;
tree2[rt]=(len*POW(C,2))%MOD;
tree3[rt]=(len*POW(C,3))%MOD;
lazy1[rt]=1;
lazy2[rt]=0;
lazy3[rt]=C;
}
return;
}
int mid=(l+r)>>1;
pushdown(l,r,rt);
if(L<=mid)updata(l,mid,rt<<1,L,R,C,op);
if(mid<R)updata(mid+1,r,rt<<1|1,L,R,C,op);
pushup(rt);
}
ll query(int l,int r,int rt,int L,int R,int op){
if(L<=l&&r<=R){
if(op==1)return tree[rt];
if(op==2)return tree2[rt];
if(op==3)return tree3[rt];
}
int mid=(l+r)>>1;
ll res=0;
pushdown(l,r,rt);
if(L<=mid)res=(res+query(l,mid,rt<<1,L,R,op))%MOD;
if(mid<R)res=(res+query(mid+1,r,rt<<1|1,L,R,op))%MOD;
return res;
}
void see(int l,int r,int rt){
if(l==r){
printf("%lld%c",tree3[rt]," \n"[r==n]);
return;
}
int mid=(l+r)>>1;
pushdown(l,r,rt);
see(l,mid,rt<<1);
see(mid+1,r,rt<<1|1);
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
while(~scanf("%d%d",&n,&m)&&n+m){
build(1,n,1);
int op;
int l,r;
ll c;
for(int i=1;i<=m;i++){
scanf("%d",&op);
if(op==1){
scanf("%d%d%lld",&l,&r,&c);
updata(1,n,1,l,r,c,2);
}else if(op==2){
scanf("%d%d%lld",&l,&r,&c);
updata(1,n,1,l,r,c,1);
}else if(op==3){
scanf("%d%d%lld",&l,&r,&c);
updata(1,n,1,l,r,c,3);
}else if(op==4){
scanf("%d%d%d",&l,&r,&p);
printf("%lld\n",query(1,n,1,l,r,p));
}
//see(1,n,1);
}
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
题解：
//用线段树维护里面的值都相等的区间 ,那么这个区间的所需答案为(r-l+1)*(tree[v].eq)^q
//对于懒惰操作 mul , eq , add的处理是
//对于每次eq操作可以直接操作tree[v].eq = eq ;tree[v].mul = 1 ; tree[v].add = 0;
//而对于mul ,和add的操作每次push_down(v)的时候保证下面一层的所有懒惰情况都是初始情况
//所以对于mul和add操作时就一直往下push_down知道找到一个可以
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=100010;
#define left v<<1
#define right v<<1|1
#define mod 10007
struct node{
int l,r,value;
int eq,add,mul;
}tree[maxn<<2];
void build(int l,int r,int v){
tree[v].l=l;
tree[v].r=r;
tree[v].add=0;tree[v].mul=1;tree[v].eq=-1;
if(l==r){
tree[v].eq=0;
return;
}
int mid=(l+r)>>1;
build(l,mid,left);
build(mid+1,r,right);
}
void push_down(int v){
if(tree[v].l==tree[v].r)return;
if(tree[v].eq!=-1){//=
tree[left].eq=tree[right].eq=tree[v].eq;
tree[left].add=tree[right].add=0;
tree[left].mul=tree[right].mul=1;
tree[v].eq=-1;
return;
}
if(tree[v].mul!=1){//*
if(tree[left].eq!=-1)
tree[left].eq=(tree[left].eq*tree[v].mul)%mod;
else{
push_down(left);
tree[left].mul=(tree[left].mul*tree[v].mul)%mod;
}
if(tree[right].eq!=-1)
tree[right].eq=(tree[right].eq*tree[v].mul)%mod;
else{
push_down(right);
tree[right].mul=(tree[right].mul*tree[v].mul)%mod;
}
tree[v].mul=1;
}
if(tree[v].add){//+
if(tree[left].eq!=-1)
tree[left].eq=(tree[left].eq+tree[v].add)%mod;
else{
push_down(left);
tree[left].add=(tree[left].add+tree[v].add)%mod;
}
if(tree[right].eq!=-1)
tree[right].eq=(tree[right].eq+tree[v].add)%mod;
else{
push_down(right);
tree[right].add=(tree[right].add+tree[v].add)%mod;
}
tree[v].add=0;
}
}
void update(int l,int r,int v,int op,int c){
if(l<=tree[v].l&&tree[v].r<=r){
if(op==3){
tree[v].add=0;tree[v].mul=1;
tree[v].eq=c;
return;
}
if(tree[v].eq!=-1){
if(op==1)tree[v].eq=(tree[v].eq+c)%mod;
else tree[v].eq=(tree[v].eq*c)%mod;
}else{
push_down(v);
if(op==1)tree[v].add=(tree[v].add+c)%mod;
else tree[v].mul=(tree[v].mul*c)%mod;
}
return;
}
push_down(v);
int mid=(tree[v].l+tree[v].r)>>1;
if(l<=mid)update(l,r,left,op,c);
if(r>mid)update(l,r,right,op,c);
}
int query(int l,int r,int v,int q){
if(tree[v].l>=l&&tree[v].r<=r&&tree[v].eq!=-1){
int ans=1;
for(int i=1;i<=q;i++)
ans=(ans*tree[v].eq)%mod;
return(ans*((tree[v].r-tree[v].l+1)%mod))%mod;
}
push_down(v);
int mid=(tree[v].l+tree[v].r)>>1;
if(l>mid)
return query(l,r,right,q);
else if(r<=mid)
return query(l,r,left,q);
else
return(query(l,mid,left,q)+query(mid+1,r,right,q))%mod;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)&&(n+m)){
int op,x,y,c;
build(1,n,1);
while(m--){
scanf("%d%d%d%d",&op,&x,&y,&c);
if(op==4)
printf("%d\n",(query(x,y,1,c)%mod));
else
update(x,y,1,op,c);
}
}
return 0;
}
C++版本三
///先乘后加的原则，每次更新区间乘法，加法标记就*乘法标记
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define mid int m=l+r>>1
#define debug(x) printf("----Line%s----\n",#x)
#define ls rt<<1
#define rs rt<<1|1
#define mod 10007
using namespace std;
const int N = 1e5+5;
ll add[N<<2],mtag[N<<2];
ll t[N<<2],tt[N<<2],ttt[N<<2];
ll isset[N<<2];
ll Pow(ll a,int b){
if (b==2) return a*a%mod;
if (b==3) return a*a%mod*a%mod;
}
void push_up(int rt)
{
t[rt] = (t[ls] + t[rs])%mod;
tt[rt] = (tt[ls] + tt[rs])%mod;
ttt[rt] = (ttt[ls] + ttt[rs])%mod;
}
void push_down(int rt,int len)
{
if (isset[rt]){
ll x = isset[rt];
isset[ls] = isset[rs] = isset[rt];
isset[rt] = 0;
mtag[ls] = mtag[rs] = 1;
add[ls] = add[rs] = 0;
ttt[ls] = (len-len/2)*Pow(x,3)%mod;
tt[ls] = (len-len/2)*Pow(x,2)%mod;
t[ls] = (len-len/2)*x%mod;
ttt[rs] = (len/2)*Pow(x,3)%mod;
tt[rs] = (len/2)*Pow(x,2)%mod;
t[rs] = (len/2)*x%mod;
}
if (mtag[rt]==1 && add[rt]==0) return ;
ttt[ls] = (ttt[ls]*Pow(mtag[rt],3)%mod + (len-len/2)*Pow(add[rt],3)%mod + 3*tt[ls]*Pow(mtag[rt],2)%mod*add[rt]%mod + 3*t[ls]*mtag[rt]%mod*Pow(add[rt],2)%mod)%mod;
ttt[rs] = (ttt[rs]*Pow(mtag[rt],3)%mod + len/2 *Pow(add[rt],3)%mod + 3*tt[rs]*Pow(mtag[rt],2)%mod*add[rt]%mod + 3*t[rs]*mtag[rt]%mod*Pow(add[rt],2)%mod)%mod;
tt[ls] = (tt[ls]*Pow(mtag[rt],2)%mod + (len-len/2)*Pow(add[rt],2)%mod + 2*t[ls]*add[rt]*mtag[rt])%mod;
tt[rs] = (tt[rs]*Pow(mtag[rt],2)%mod + len/2*Pow(add[rt],2)%mod + 2*t[rs]*add[rt]*mtag[rt])%mod;
t[ls] = (t[ls]*mtag[rt] + (len-len/2)*add[rt])%mod;
t[rs] = (t[rs]*mtag[rt] + (len/2)*add[rt])%mod;
mtag[ls] = (mtag[ls]*mtag[rt])%mod;
mtag[rs] = (mtag[rs]*mtag[rt])%mod;
add[ls] = (add[ls]*mtag[rt]%mod+add[rt])%mod;///这个标记也要先乘后加
add[rs] = (add[rs]*mtag[rt]%mod+add[rt])%mod;
add[rt] = 0;
mtag[rt] = 1;
}
void update(int L,int R,int op,ll x,int rt,int l,int r)
{
if (L<=l && r<=R){
if (op==1){///+
add[rt] = (add[rt]+x)%mod;
ttt[rt] = (ttt[rt] + Pow(x,3)*(r-l+1)%mod + 3*tt[rt]*x%mod + 3*t[rt]*Pow(x,2)%mod)%mod;
tt[rt] = (tt[rt] + Pow(x,2)*(r-l+1) + 2*t[rt]*x)%mod;
t[rt] = (t[rt] + (r-l+1)*x)%mod;
}
if (op==2){///*
mtag[rt] = (mtag[rt]*x)%mod;
add[rt] = (add[rt]*x)%mod;
ttt[rt] = (ttt[rt]*Pow(x,3))%mod;
tt[rt] = (tt[rt]*Pow(x,2))%mod;
t[rt] = (t[rt]*x)%mod;
}
if (op==3){///覆盖
mtag[rt] = 1,add[rt] = 0;
ttt[rt] = (r-l+1)*Pow(x,3)%mod;
tt[rt] = (r-l+1)*Pow(x,2)%mod;
t[rt] = (r-l+1)*x%mod;
isset[rt] = x;
}
return ;
}
mid;
push_down(rt,r-l+1);
if (L<=m) update(L,R,op,x,lson);
if (R>m) update(L,R,op,x,rson);
push_up(rt);
}
ll query(int L,int R,ll x,int rt,int l,int r)
{
if (L<=l && r<=R){
if (x==1) return t[rt];
if (x==2) return tt[rt];
if (x==3) return ttt[rt];
}
push_down(rt,r-l+1);
ll ans = 0;
mid;
if (L<=m) ans = (ans+query(L,R,x,lson))%mod;
if (R>m) ans = (ans+query(L,R,x,rson))%mod;
return ans;
}
void build(int rt,int l,int r)
{
if (l==r){
t[rt] = tt[rt] = ttt[rt] = add[rt] = isset[rt] = 0;
mtag[rt] = 1;
return ;
}
mid;
build(lson);
build(rson);
push_up(rt);
}
int main()
{
int n,q;
while (~scanf("%d %d",&n,&q),n||q){
build(1,1,n);
int op,l,r;
ll x;
while (q--){
scanf("%d %d %d %lld",&op,&l,&r,&x);
if (op!=4){
update(l,r,op,x,1,1,n);
}
else
printf("%lld\n",query(l,r,x,1,1,n)%mod);
}
}
return 0;
} C++版本四
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL __int64
#define eps 1e-8
#define INF INT_MAX
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int MOD = 10007;
const int maxn = 100000 + 5;
const int N = 12;
LL add[maxn << 2] , set[maxn << 2] , mul[maxn << 2];
LL sum1[maxn << 2] , sum2[maxn << 2] , sum3[maxn << 2];
void PushUp(int rt)
{
sum1[rt] = (sum1[rt << 1] + sum1[rt << 1 | 1]) % MOD;
sum2[rt] = (sum2[rt << 1] + sum2[rt << 1 | 1]) % MOD;
sum3[rt] = (sum3[rt << 1] + sum3[rt << 1 | 1]) % MOD;
}
void build(int l , int r , int rt)
{
add[rt] = set[rt] = 0;
mul[rt] = 1;
if(l == r) {
sum1[rt] = sum2[rt] = sum3[rt] = 0;
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
PushUp(rt);
}
void PushDown(int rt , int len)
{
if(set[rt]) {
set[rt << 1] = set[rt << 1 | 1] = set[rt];
add[rt << 1] = add[rt << 1 | 1] = 0; //注意这个也要下放
mul[rt << 1] = mul[rt << 1 | 1] = 1;
LL tmp = ((set[rt] * set[rt]) % MOD) * set[rt] % MOD;
sum1[rt << 1] = ((len - (len >> 1)) % MOD) * (set[rt] % MOD) % MOD;
sum1[rt << 1 | 1] = ((len >> 1) % MOD) * (set[rt] % MOD) % MOD;
sum2[rt << 1] = ((len - (len >> 1)) % MOD) * ((set[rt] * set[rt]) % MOD) % MOD;
sum2[rt << 1 | 1] = ((len >> 1) % MOD) * ((set[rt] * set[rt]) % MOD) % MOD;
sum3[rt << 1] = ((len - (len >> 1)) % MOD) * tmp % MOD;
sum3[rt << 1 | 1] = ((len >> 1) % MOD) * tmp % MOD;
set[rt] = 0;
}
if(mul[rt] != 1) { //这个就是mul[rt] != 1 ， 当时我这里没注意所以TLE了
mul[rt << 1] = (mul[rt << 1] * mul[rt]) % MOD;
mul[rt << 1 | 1] = (mul[rt << 1 | 1] * mul[rt]) % MOD;
if(add[rt << 1]) //注意这个也要下放
add[rt << 1] = (add[rt << 1] * mul[rt]) % MOD;
if(add[rt << 1 | 1])
add[rt << 1 | 1] = (add[rt << 1 | 1] * mul[rt]) % MOD;
LL tmp = (((mul[rt] * mul[rt]) % MOD * mul[rt]) % MOD);
sum1[rt << 1] = (sum1[rt << 1] * mul[rt]) % MOD;
sum1[rt << 1 | 1] = (sum1[rt << 1 | 1] * mul[rt]) % MOD;
sum2[rt << 1] = (sum2[rt << 1] % MOD) * ((mul[rt] * mul[rt]) % MOD) % MOD;
sum2[rt << 1 | 1] = (sum2[rt << 1 | 1] % MOD) * ((mul[rt] * mul[rt]) % MOD) % MOD;
sum3[rt << 1] = (sum3[rt << 1] % MOD) * tmp % MOD;
sum3[rt << 1 | 1] = (sum3[rt << 1 | 1] % MOD) * tmp % MOD;
mul[rt] = 1;
}
if(add[rt]) {
add[rt << 1] += add[rt]; //add是+= ， mul是*=
add[rt << 1 | 1] += add[rt];
LL tmp = (add[rt] * add[rt] % MOD) * add[rt] % MOD; //注意sum3 , sum2 , sum1的先后顺序
sum3[rt << 1] = (sum3[rt << 1] + (tmp * (len - (len >> 1)) % MOD) + 3 * add[rt] * ((sum2[rt << 1] + sum1[rt << 1] * add[rt]) % MOD)) % MOD;
sum3[rt << 1 | 1] = (sum3[rt << 1 | 1] + (tmp * (len >> 1) % MOD) + 3 * add[rt] * ((sum2[rt << 1 | 1] + sum1[rt << 1 | 1] * add[rt]) % MOD)) % MOD;
sum2[rt << 1] = (sum2[rt << 1] + ((add[rt] * add[rt] % MOD) * (len - (len >> 1)) % MOD) + (2 * sum1[rt << 1] * add[rt] % MOD)) % MOD;
sum2[rt << 1 | 1] = (sum2[rt << 1 | 1] + (((add[rt] * add[rt] % MOD) * (len >> 1)) % MOD) + (2 * sum1[rt << 1 | 1] * add[rt] % MOD)) % MOD;
sum1[rt << 1] = (sum1[rt << 1] + (len - (len >> 1)) * add[rt]) % MOD;
sum1[rt << 1 | 1] = (sum1[rt << 1 | 1] + (len >> 1) * add[rt]) % MOD;
add[rt] = 0;
}
}
void update(int L , int R , int c , int ch , int l , int r , int rt)
{
if(L <= l && R >= r) {
if(ch == 3) {
set[rt] = c;
add[rt] = 0;
mul[rt] = 1;
sum1[rt] = ((r - l + 1) * c) % MOD;
sum2[rt] = ((r - l + 1) * ((c * c) % MOD)) % MOD;
sum3[rt] = ((r - l + 1) * (((c * c) % MOD) * c % MOD)) % MOD;
} else if(ch == 2) {
mul[rt] = (mul[rt] * c) % MOD;
if(add[rt])
add[rt] = (add[rt] * c) % MOD;
sum1[rt] = (sum1[rt] * c) % MOD;
sum2[rt] = (sum2[rt] * (c * c % MOD)) % MOD;
sum3[rt] = (sum3[rt] * ((c * c % MOD) * c % MOD)) % MOD;
} else if(ch == 1) {
add[rt] += c;
LL tmp = (((c * c) % MOD * c) % MOD * (r - l + 1)) % MOD; //(r - l + 1) * c^3
sum3[rt] = (sum3[rt] + tmp + 3 * c * ((sum2[rt] + sum1[rt] * c) % MOD)) % MOD;
sum2[rt] = (sum2[rt] + (c * c % MOD * (r - l + 1) % MOD) + 2 * sum1[rt] * c) % MOD;
sum1[rt] = (sum1[rt] + (r - l + 1) * c) % MOD;
}
return;
}
PushDown(rt , r - l + 1);
int m = (l + r) >> 1;
if(L > m)
update(L , R , c , ch , rson);
else if(R <= m)
update(L , R , c , ch , lson);
else {
update(L , R , c , ch , lson);
update(L , R , c , ch , rson);
}
PushUp(rt);
}
LL query(int L , int R , int p , int l , int r , int rt)
{
if(L <= l && R >= r) {
if(p == 1)
return sum1[rt] % MOD;
else if(p == 2)
return sum2[rt] % MOD;
else
return sum3[rt] % MOD;
}
PushDown(rt , r - l + 1);
int m = (l + r) >> 1;
if(L > m)
return query(L , R , p , rson);
else if(R <= m)
return query(L , R , p , lson);
else
return (query(L , R , p , lson) + query(L , R , p , rson)) % MOD;
}
int main()
{
int n , m;
int a , b , c , ch;
while(~scanf("%d %d" , &n , &m))
{
if(n == 0 && m == 0)
break;
build(1 , n , 1);
while(m--) {
scanf("%d %d %d %d" , &ch , &a , &b , &c);
if(ch != 4) {
update(a , b , c , ch , 1 , n , 1);
} else {
printf("%I64d\n" , query(a , b , c , 1 , n , 1));
}
}
}
return 0;
} C++版本五
题解：
我只能说这题很迷，迷之WA，这题我陆陆续续做了4天才AC，其中WA了3页，共计40多次吧，重写代码3次，用各种不同方法写。。最后无奈看着别人的博客照着一个大佬的写就AC了。。吐血，一开始我打算用3个v，3个tag来写，3个v表示区间的一二三次方值，tag分别表示加，乘等于的标记，先处理等，如果有等号标记，区间更新，清除加号和乘号标记，在处理乘和加之前看子区间有没有等号标记，有就先处理子区间的等号标记，然后处理乘，如果同时有加号标记把加的值乘上一个要乘的数，最后处理乘号标记，至于一次方二次方三次方公式是搞数学的老刘推的。。结果就是我样例过了，自己测的几组也过了还是WA，各种迷，怎么修改都是WA，后来看到一个大佬的没有推公式也没有储存三次方。。方法很神奇，而且速度比一般用储存3个值的那种快得多。。
说一下思路：
同样tag1表示加号标记，tag2表示乘，tag3表示等，无疑在向下更新的时候等号的优先级应该最高，先处理等号标记，并把加号和乘号标记置为0和1（初始值），然后重点来了，在处理乘号标记的时候，如果发现子区间有等号标记，直接修改等号标记，否则先将子区间pushdwon一下清空标记，再进行该子区间标记，加号同理，如果子区间有等号标记，就修改等号标记，否则将子区间pushdown清空标记，再将该子区间标记，所有操作完都要清空当前区间标记，然后修改的时候也差不多，先检查该区间有没有等号标记，有的话直接修改等号标记，否则pushdown清空该区间标记，再进行各种标记，查询的时候是整个算法的精髓，他是查询到要查询区间的子区间的等号标记不为初始标记，即为一段相同的数字的时候停止，然后返回该区间的值，进行各个子区间累加，得出答案。。。。一开始我还以为会超时，结果居然比一般的算法快得多，膜拜大佬
#include<algorithm>
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<math.h>
#include<string>
#include<stdio.h>
#include<queue>
#include<stack>
#include<map>
#include<deque>
using namespace std;
#define left k*2
#define right k*2+1
const int N=10007;
struct node
{
int l,r;
int tag1,tag2,tag3;//分别表示加号，乘号，等号标记
}t[100005*4];
int n;
void Build(int l,int r,int k)
{
t[k].l=l;
t[k].r=r;
t[k].tag1=0;
t[k].tag2=1;
t[k].tag3=-1;
if(l==r)
{
t[k].tag3=0;//最底层要赋值为0
return;
};
int mid=(l+r)/2;
Build(l,mid,left);
Build(mid+1,r,right);
}
void pushdown(int k)
{
if(t[k].l==t[k].r)//没有子区间了不用退了
return;
if(t[k].tag3!=-1)//处理等号
{
t[left].tag3=t[right].tag3=t[k].tag3;//更新子区间等号标记
t[left].tag2=t[right].tag2=1;
t[left].tag1=t[right].tag1=0;//清空子区间加乘标记
t[k].tag3=-1;
return;
}
if(t[k].tag2!=1)//处理乘号
{
if(t[left].tag3!=-1)//如果子区间有等号标记，直接修改等号标记
t[left].tag3=(t[left].tag3*t[k].tag2)%N;
else//否则清空该子区间标记，进行子区间标记
{
pushdown(left);
t[left].tag2=(t[left].tag2*t[k].tag2)%N;
}
if(t[right].tag3!=-1)//同理处理右区间
t[right].tag3=(t[right].tag3*t[k].tag2)%N;
else
{
pushdown(right);
t[right].tag2=(t[right].tag2*t[k].tag2)%N;
}
t[k].tag2=1;
}
if(t[k].tag1!=0)//处理加号标记，和上面同理处理
{
if(t[left].tag3!=-1)
t[left].tag3=(t[left].tag3+t[k].tag1)%N;
else
{
pushdown(left);
t[left].tag1=(t[left].tag1+t[k].tag1)%N;
}
if(t[right].tag3!=-1)
t[right].tag3=(t[right].tag3+t[k].tag1)%N;
else
{
pushdown(right);
t[right].tag1=(t[right].tag1+t[k].tag1)%N;
}
t[k].tag1=0;//记得还原
}
}
void update(int l,int r,int v,int d,int k)
{
if(t[k].l==l&&t[k].r==r)
{
if(d==1)
{
if(t[k].tag3!=-1)//如果有等号标记，就直接修改等号标记
{
t[k].tag3=(t[k].tag3+v%N)%N;
}
else
{
pushdown(k);//否则清空该区间，进行标记
t[k].tag1=(t[k].tag1+v%N)%N;
}
}
else if(d==2)//同理
{
if(t[k].tag3!=-1)
{
t[k].tag3=(t[k].tag3*v%N)%N;
}
else
{
pushdown(k);
t[k].tag2=(t[k].tag2*v%N)%N;
}
}
else
{
t[k].tag3=v%N;
t[k].tag1=0;
t[k].tag2=1;
}
return;
}
pushdown(k);//向下更新
int mid=(t[k].l+t[k].r)/2;
if(r<=mid)
update(l,r,v,d,left);
else if(l>mid)
update(l,r,v,d,right);
else
{
update(l,mid,v,d,left);
update(mid+1,r,v,d,right);
}
}
int query(int l,int r,int p,int k)//查询
{
if(t[k].l>=l&&t[k].r<=r&&t[k].tag3!=-1)//查到是查询区间的子区间且一段全为相同的数
{
int temp=1;
for(int i=1;i<=p;i++)
temp=(temp*t[k].tag3)%N;
return ((t[k].r-t[k].l+1)%N*temp)%N;//注意要乘上长度
}
pushdown(k);
int mid=(t[k].l+t[k].r)/2;
if(r<=mid)
return query(l,r,p,left)%N;
else if(l>mid)
return query(l,r,p,right)%N;
else
{
return (query(l,mid,p,left)+query(mid+1,r,p,right))%N;
}
}
int main()
{
int i,j,k,m,d,x,y,c;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0&&m==0)
break;
Build(1,n,1);
for(i=0;i<m;i++)
{
scanf("%d%d%d%d",&d,&x,&y,&c);
if(d>=1&&d<=3)
{
update(x,y,c,d,1);
}
else
{
printf("%d\n",query(x,y,c,1)%N);
}
}
}
return 0;
}
锐捷网络股份有限公司公司福利 349人发布
投递腾讯音乐娱乐集团等公司10个岗位 >
