首页 > 代码库 > hdu-4578-Transformation-线段树
hdu-4578-Transformation-线段树
当一道题目,使用__int64超时,使用int就能A的时候,我想,这个题,不是一个好题。。。。。
add[i]:记录加的lazy标记
mul[i]:记录乘的lazy标记
num[i]:记录数的lazy标记
sum[i][j]:第i段,j次方的和。
除去lazy标记的下放,这完全就是一道水的线段树的题目。。。
lazy标记如何下放呢?
1,首先查看num标记,如果存在,果断下放。
2,然后mul标记和add标记一起下放。
#include<stdio.h> #include<iostream> #include<stdlib.h> #include<string.h> #include<algorithm> #include<vector> using namespace std; #define maxn 110000 #define lmin 1 #define rmax n #define lson l,(l+r)/2,rt<<1 #define rson (l+r)/2+1,r,rt<<1|1 #define root lmin,rmax,1 #define now l,r,rt #define int_now int l,int r,int rt #define INF 99999999 #define LL int #define mod 10007 LL add[maxn*4]; LL mul[maxn*4]; LL num[maxn*4]; LL sum[maxn*4][4]; void push_up(int_now) { for(int i=1; i<=3; i++) sum[rt][i]=(sum[rt<<1][i]+sum[rt<<1|1][i])%mod; } void push_down(int_now) { if(l==r)return; int ll=(r+l)/2-l+1; int rr=r-(r+l)/2; if(num[rt] != 0) { num[rt<<1] = num[rt<<1|1] = num[rt]; add[rt<<1] = add[rt<<1|1] = 0; mul[rt<<1] = mul[rt<<1|1] = 1; sum[rt<<1][1] = (ll)*num[rt<<1]%mod; sum[rt<<1][2] = (ll)*num[rt<<1]%mod*num[rt<<1]%mod; sum[rt<<1][3] = (ll)*num[rt<<1]%mod*num[rt<<1]%mod*num[rt<<1]%mod; sum[(rt<<1)|1][1] = (rr)*num[rt<<1|1]%mod; sum[(rt<<1)|1][2] = (rr)*num[rt<<1|1]%mod*num[rt<<1|1]%mod; sum[(rt<<1)|1][3] = (rr)*num[rt<<1|1]%mod*num[rt<<1|1]%mod*num[rt<<1|1]%mod; num[rt] = 0; } if(add[rt] != 0 || mul[rt] != 1) { add[rt<<1] = ( mul[rt]*add[rt<<1]%mod + add[rt] )%mod; mul[rt<<1] = mul[rt<<1]*mul[rt]%mod; int sum1,sum2,sum3; sum1 = (sum[rt<<1][1]*mul[rt]%mod + (ll)*add[rt]%mod)%mod; sum2 = (mul[rt] * mul[rt] % mod * sum[rt<<1][2] % mod + 2*add[rt]*mul[rt]%mod * sum[rt<<1][1]%mod + (ll)*add[rt]%mod*add[rt]%mod)%mod; sum3 = mul[rt] * mul[rt] % mod * mul[rt] % mod * sum[rt<<1][3] % mod; sum3 = (sum3 + 3*mul[rt] % mod * mul[rt] % mod * add[rt] % mod * sum[rt<<1][2]) % mod; sum3 = (sum3 + 3*mul[rt] % mod * add[rt] % mod * add[rt] % mod * sum[rt<<1][1]) % mod; sum3 = (sum3 + (ll)*add[rt]%mod * add[rt] % mod * add[rt] % mod) % mod; sum[rt<<1][1] = sum1; sum[rt<<1][2] = sum2; sum[rt<<1][3] = sum3; add[rt<<1|1] = ( mul[rt]*add[rt<<1|1]%mod + add[rt] )%mod; mul[rt<<1|1] = mul[rt<<1|1] * mul[rt] % mod; sum1 = (sum[(rt<<1)|1][1]*mul[rt]%mod + (rr)*add[rt]%mod)%mod; sum2 = (mul[rt] * mul[rt] % mod * sum[(rt<<1)|1][2] % mod + 2*add[rt]*mul[rt]%mod * sum[(rt<<1)|1][1]%mod + (rr)*add[rt]%mod*add[rt]%mod)%mod; sum3 = mul[rt] * mul[rt] % mod * mul[rt] % mod * sum[(rt<<1)|1][3] % mod; sum3 = (sum3 + 3*mul[rt] % mod * mul[rt] % mod * add[rt] % mod * sum[(rt<<1)|1][2]) % mod; sum3 = (sum3 + 3*mul[rt] % mod * add[rt] % mod * add[rt] % mod * sum[(rt<<1)|1][1]) % mod; sum3 = (sum3 + (rr)*add[rt]%mod * add[rt] % mod * add[rt] % mod) % mod; sum[(rt<<1)|1][1] = sum1; sum[(rt<<1)|1][2] = sum2; sum[(rt<<1)|1][3] = sum3; add[rt] = 0; mul[rt] = 1; } } void creat(int_now) { add[rt]=0; mul[rt]=1; num[rt]=0; for(int i=1; i<=3; i++)sum[rt][i]=0; if(l!=r) { creat(lson); creat(rson); } } void update(int ll,int rr,int x,int k,int_now) { if(ll>r||rr<l)return; if(ll<=l&&rr>=r) { x=x%mod; if(k==1) { add[rt]=(add[rt]+x)%mod; sum[rt][3]=(sum[rt][3]+3*sum[rt][2]%mod*x%mod+3*sum[rt][1]%mod*x%mod*x%mod+x*x%mod*x%mod*(r-l+1)%mod)%mod; sum[rt][2]=(sum[rt][2]+(r-l+1)*x%mod*x%mod+2*x%mod*sum[rt][1]%mod)%mod; sum[rt][1]=(sum[rt][1]+x*(r-l+1)%mod)%mod; } else if(k==2) { mul[rt]=(mul[rt]*x)%mod; add[rt]=(add[rt]*x)%mod; for(int i=1; i<=3; i++) { int j=i; LL ans=1; while(j--)ans=(ans*x)%mod; sum[rt][i]=(sum[rt][i]*ans)%mod; } } else { num[rt]=x; mul[rt]=1; add[rt]=0; for(int i=1; i<=3; i++) { int j=i; LL ans=1; while(j--)ans=(ans*x)%mod; sum[rt][i]=(ans*(r-l+1)%mod)%mod; } } return; } push_down(now); update(ll,rr,x,k,lson); update(ll,rr,x,k,rson); push_up(now); } LL query(int ll,int rr,int p,int_now) { if(ll>r||rr<l)return 0; if(ll<=l&&rr>=r) { return sum[rt][p]; } push_down(now); return (query(ll,rr,p,lson)+query(ll,rr,p,rson))%mod; } int main() { int n,m,k,a,b,c; while(~scanf("%d%d",&n,&m)&&(n||m)) { creat(root); while(m--) { scanf("%d%d%d%d",&k,&a,&b,&c); if(k<=3) { update(a,b,c,k,root); } else { printf("%d\n",query(a,b,c,root)); } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。