当前位置:网站首页>HDU ACM 4578 Transformation->段树-间隔的变化
HDU ACM 4578 Transformation->段树-间隔的变化
2022-07-06 19:36:00 【全栈程序员站长】
大家好,又见面了,我是全栈君
分析:复杂的经营分部树。
只有一个查询操作,这是要求[l,r]的数量之间p钍总和。并不是所有的查询所有节点,会议TLE。最好的是查询部件[a。b]。所有这个区间值我们是平等的,即能返回(b-a+1)*val 的值。区间内全部值都同样的情况的区间。对于置初值和加乘操作。分两种情况:1、当为置初值操作。直接覆盖区间就可以。并把标记的加乘操作赋为初始值。2、当为加乘操作时。先推断当前区间段是否为同样的值,是的话直接加乘,维护这个同样的值就可以。假设不同样,看区间是否已有加乘标记,把这个加乘标记一直传递下去。直到遇见那个区间段区间全部值同样时停止。最后把这个加乘赋给最開始的区间段。简单的说就是,覆盖操作可直接维护,不是覆盖操作的话。区间仅仅能保留一个加乘操作。
#include<iostream>
using namespace std;
#define lz t<<1,l,mid //左区间
#define rz (t<<1)|1,mid+1,r //右区间
#define N 100005
#define MOD 10007
__int64 add[N<<2],mul[N<<2],chan[N<<2],sum[N<<2];
void Build(int t,int l,int r) //建立线段树
{
int mid;
mul[t]=1;
add[t]=sum[t]=0;
chan[t]=0;
if(l==r)
{
chan[t]=1; //叶节点设为1。方便询问的查询
return ;
}
mid=(l+r)>>1;
Build(lz);
Build(rz);
}
void PushDown(int t,int l,int r) //标记下传
{
int mid;
if(l==r) return ;
mid=(l+r)>>1;
if(chan[t]) //set标记下传
{
add[t<<1]=0,mul[t<<1]=1;
add[(t<<1)|1]=0,mul[(t<<1)|1]=1;
chan[t<<1]=chan[(t<<1)|1]=1;
sum[t<<1]=sum[(t<<1)|1]=sum[t];
chan[t]=0;
}
else
{
if(add[t]) //加标记下传
{
if(chan[t<<1]) sum[t<<1]=(sum[t<<1]+add[t])%MOD; //左子树有set标记
else
{
PushDown(lz); //下传
add[t<<1]=(add[t<<1]+add[t])%MOD;
}
if(chan[(t<<1)|1]) sum[(t<<1)|1]=(sum[(t<<1)|1]+add[t])%MOD; //左子树有set标记
else
{
PushDown(rz); //下传
add[(t<<1)|1]=(add[(t<<1)|1]+add[t])%MOD;
}
add[t]=0;
}
if(mul[t]>1) //乘标记下传
{
if(chan[t<<1]) sum[t<<1]=(sum[t<<1]*mul[t])%MOD; //左子树有set标记
else
{
PushDown(lz); //下传
mul[t<<1]=(mul[t<<1]*mul[t])%MOD;
}
if(chan[(t<<1)|1]) sum[(t<<1)|1]=(sum[(t<<1)|1]*mul[t])%MOD; //左子树有set标记
else
{
PushDown(rz); //下传
mul[(t<<1)|1]=(mul[(t<<1)|1]*mul[t])%MOD;
}
mul[t]=1;
}
}
}
void Update(int t,int l,int r,int ul,int ur,int c,int op)
{
int mid;
if(l>=ul && ur>=r) //边界
{
if(op==3)
chan[t]=1,mul[t]=1,add[t]=0,sum[t]=c;
else if(chan[t])
{
if(op==1) sum[t]=(sum[t]+c)%MOD;
else sum[t]=(sum[t]*c)%MOD;
}
else
{
PushDown(t,l,r); //下传
if(op==1) add[t]=(add[t]+c)%MOD;
else mul[t]=(mul[t]*c)%MOD;
}
return ;
}
PushDown(t,l,r);
mid=(l+r)>>1;
if(ur<=mid) Update(lz,ul,ur,c,op);
else if(ul>mid) Update(rz,ul,ur,c,op);
else
{
Update(lz,ul,mid,c,op);
Update(rz,mid+1,ur,c,op);
}
}
__int64 Query(int t,int l,int r,int ul,int ur,int p)
{
int mid,i;
__int64 ans,tp,t1,t2;
if(ul<=l && r<=ur)
if(chan[t])
{
ans=1;
tp=sum[t];
for(i=1;i<=p;i++) ans=(ans*tp)%MOD;
return (r-l+1)*ans%MOD; //由于区间的每一个部分都是同样的
}
PushDown(t,l,r); //下传标记
mid=(l+r)>>1;
if(ur<=mid) return Query(lz,ul,ur,p);
else if(ul>mid) return Query(rz,ul,ur,p);
else
{
t1=Query(lz,ul,mid,p);
t2=Query(rz,mid+1,ur,p);
return (t1+t2)%MOD;
}
}
int main()
{
int n,m,i,l,r,c,op;
while(scanf("%d%d",&n,&m)==2 && n+m)
{
Build(1,1,n); //1为根节点
for(i=1;i<=m;i++)
{
scanf("%d%d%d%d",&op,&l,&r,&c);
if(op<=3) Update(1,1,n,l,r,c,op);
else
printf("%I64d\n",Query(1,1,n,l,r,c)%MOD);
}
}
return 0;
}
版权声明:本文博主原创文章。博客,未经同意不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116783.html原文链接:https://javaforall.cn
边栏推荐
- PSINS中19维组合导航模块sinsgps详解(初始赋值部分)
- Cglib agent in agent mode
- Use of promise in ES6
- c语言(字符串)如何把字符串中某个指定的字符删除?
- Wireshark installation
- Unity custom webgl packaging template
- 新标杆!智慧化社会治理
- What management points should be paid attention to when implementing MES management system
- Oracle中日期的使用方法实例
- How to write test cases for test coupons?
猜你喜欢
Left path cloud recursion + dynamic planning
Le tube MOS réalise le circuit de commutation automatique de l'alimentation principale et de l'alimentation auxiliaire, et la chute de tension "zéro", courant statique 20ua
The whole process of knowledge map construction
MySQL - common functions - string functions
Matlb| economic scheduling with energy storage, opportunity constraints and robust optimization
Statistics of radar data in nuscenes data set
硬件之OC、OD、推挽解释
Analysis of USB network card sending and receiving data
Form validation of uniapp
Redis introduction complete tutorial: client case analysis
随机推荐
密码学系列之:在线证书状态协议OCSP详解
What management points should be paid attention to when implementing MES management system
知识图谱构建全流程
Hash table and full comments
Software testing -- common assertions of JMeter interface testing
Code debugging core step memory
Lingyun going to sea | yidiantianxia & Huawei cloud: promoting the globalization of Chinese e-commerce enterprise brands
Andrews - multimedia programming
oracle连接池长时间不使用连接失效问题
从控制理论的角度谈数据分析
Redis introduction complete tutorial: replication principle
Oauth2协议中如何对accessToken进行校验
换个姿势做运维!GOPS 2022 · 深圳站精彩内容抢先看!
Unity webgl adaptive web page size
掘金量化:通过history方法获取数据,和新浪财经,雪球同用等比复权因子。不同于同花顺
2022年信息安全工程师考试大纲
Uniapp adaptation problem
从 1.5 开始搭建一个微服务框架——日志追踪 traceId
Analysis of USB network card sending and receiving data
Kubernetes source code analysis (II) -- resource