【loj6029】「雅礼集训 2017 Day1」市场
题意:四种操作,区间加法、区间除法(下取整)、区间求最小值、区间求和。
第1、3、4个操作都是摆设,关键在于如何做区间除法。
很明显不能直接把区间的和做除法后向下取整,因为区间和可能会多凑出一个除数因子。例如$3,3$,对这两个数的区间除以2取整后变成$1,1$,但如果直接把它们的和6除以2取整后得到的和是3,很明显有误。
但是根据经验,带有区间除法操作的题目一般都会把数给你往小了压。再一看这题,两个修改操作中,区间加法的加数不大且可能是负数,而除数可高达$10^9$!
尤其是除法的大除数带来的影响特别大,这实际上暗示我们序列的数很容易迅速被压到0附近。而数的绝对值被压到很小,除数却有很大时,我们发现实际上这些数的变化可能会很小。小到什么程度呢?
考虑如果有一些近似连续的小数段,
比如$2,2,2,3,3,3$,在除3意义下,变成$0,0,0,1,1,1$,相当于整体-2。
在序列的数都被压到足够接近0时,很容易出现上面这种序列,此时就可以用区间加法维护上面这种区间的除法操作了!
那怎么判断除法区间的所有数的变化量是否相同呢?只需判断最大值和最小值的变化量是否相同即可。原因:除法区间的数按从小到大的顺序,数的变化量是单调不下降的(大数和小数都被同一个大于等于$1$的正数(题目说了除数在$[2,10^9]$范围内)除,大数当然还比小数大,变化量也比小数大,即使是在向下取整的意义下,大数仍不会比小数小,变化量也不会比小数小(为什么除数是在$(0,1)$范围内的正数时 "变化量也不会比小数小" 这条不成立,请自行思考,如果想明白了你也就明白为什么除数是大于等于$1$的正数时这条成立了)),所以只要看两端的最小值和最大值的变化量是否相同就能知道整个区间的数的变化量是否相同。
归根结底区间除法转化成了区间加法+区间最大值+区间最小值,于是还需要维护一下原题没有要求的区间最大值。
#include<bits/stdc++.h>
#define N 100001
#define inf 0x7f7f7f7f7f7f7f7f
using namespace std;
inline int read(){
int x=; bool f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=;
for(; isdigit(c);c=getchar()) x=(x<<)+(x<<)+(c^'');
if(f) return x;
return -x;
}
int n,q;
long long a[N],mx[N<<],mn[N<<],sum[N<<],tag[N<<];
int L,R,x;
inline void pushup(int o){
sum[o]=sum[o<<]+sum[o<<|];
mx[o]=max(mx[o<<],mx[o<<|]);
mn[o]=min(mn[o<<],mn[o<<|]);
}
void pushdown(int o,int l,int r){
if(!tag[o] || l==r) return;
//printf("pushdown:%d %d %d %d %d\n",o,l,r,tag[o],mn[o]);
int mid=(l+r)>>;
sum[o<<]+=(mid-l+)*tag[o], sum[o<<|]+=(r-mid)*tag[o];
mx[o<<]+=tag[o], mx[o<<|]+=tag[o];
mn[o<<]+=tag[o], mn[o<<|]+=tag[o];
tag[o<<]+=tag[o], tag[o<<|]+=tag[o]; //严重错因,好几个小时才查出这里直接覆盖儿子tag值的错误,一定要铭记!
tag[o]=;
}
void build(int o,int l,int r){
//printf("%d %d %d\n",o,l,r); system("pause");
if(l==r){sum[o]=mx[o]=mn[o]=a[l]; return;}
int mid=(l+r)>>;
build(o<<,l,mid), build(o<<|,mid+,r);
pushup(o);
}
void add(int o,int l,int r){
//printf("query:%d %d %d %d\n",l,r,mn[o],tag[o]);
if(L<=l && r<=R){
tag[o]+=x, sum[o]+=(long long)(r-l+)*x, mx[o]+=x, mn[o]+=x;
return;
}
pushdown(o,l,r);
int mid=(l+r)>>;
if(L<=mid) add(o<<,l,mid);
if(mid<R) add(o<<|,mid+,r);
pushup(o);//printf("pushup hou:%d %d %d %d %d\n",l,r,mn[o],mn[o<<1],mn[o<<1|1]);
}
long long min_query(int o,int l,int r){
//printf("query:%d %d %d %d\n",l,r,mn[o],tag[o]);
if(L<=l && r<=R) return mn[o];
pushdown(o,l,r);
int mid=(l+r)>>;
long long ret=inf;
if(L<=mid) ret=min(ret,min_query(o<<,l,mid));
if(mid<R) ret=min(ret,min_query(o<<|,mid+,r));
pushup(o);
return ret;
}
void div(int o,int l,int r){
//printf("query:%d %d %d %d\n",l,r,mn[o],tag[o]);
if(L<=l && r<=R){
long long g1=mx[o]-(long long)floor((double)mx[o]/x), g2=mn[o]-(long long)floor((double)mn[o]/x);
if(g1==g2){
//printf("fvcking subquence:%d %d %lld %lld\n",l,r,g1,g2);
tag[o]-=g1, sum[o]-=(r-l+)*g1, mx[o]-=g1, mn[o]-=g1;
return;
}
}
pushdown(o,l,r);
int mid=(l+r)>>;
if(L<=mid) div(o<<,l,mid);
if(mid<R) div(o<<|,mid+,r);
pushup(o);
}
long long sum_query(int o,int l,int r){
//printf("query:%d %d %d %d\n",l,r,mn[o],tag[o]);
if(L<=l && r<=R) return sum[o];
pushdown(o,l,r);
int mid=(l+r)>>;
long long ret=;
if(L<=mid) ret+=sum_query(o<<,l,mid);
if(mid<R) ret+=sum_query(o<<|,mid+,r);
pushup(o);
return ret;
} void find(int o,int l,int r){
if(l==r){printf("%d ",sum[o]); return;}
pushdown(o,l,r);
int mid=(l+r)>>;
find(o<<,l,mid), find(o<<|,mid+,r);
pushup(o);
} int main(){
//freopen("rand.in","r",stdin);
//freopen("count.out","w",stdout);
n=read(),q=read();
int i,k;
for(i=;i<=n;i++) a[i]=read();
build(,,n);
for(i=;i<=q;i++){
k=read(),L=read()+,R=read()+;
if(k==) x=read(), add(,,n);
else if(k==) x=read(), div(,,n);
else if(k==) printf("%lld\n",min_query(,,n));
else if(k==) printf("%lld\n",sum_query(,,n));
//find(1,1,n);
//putchar('\n');putchar('\n');putchar('\n');putchar('\n');
}
return ;
}
/*
10 11
1 2 3 4 5 6 7 8 9 10
2 0 9 2
2 0 9 3
2 0 9 4
2 0 9 5
2 0 9 6
3 0 9
4 0 9
1 0 4 -4
2 0 4 2
3 0 4
4 0 9
*/
最新文章
- eclipse 高亮配对的括号
- Nodejs开发(2.连接MongoDB)
- hdu 2079
- javascript 字符串滚动显示
- zepto源码研究 - ajax.js($.ajax具体流程分析)
- mysql、添加和删除用户、添加权限
- iOS 网络错误-分类
- php结合redis实现高并发下的抢购、秒杀功能 (转载)
- 【深入理解JVM】类加载器与双亲委派模型
- Django 系列博客(十三)
- iOS----------The Apple Developer Program License Agreement has been updated.
- Python 内置库 sys用法
- lsass.exe占用cpu 解决方法
- JavaScript:event loop详解
- Shell-2--输入输出重定向
- DirectShow设置采集帧率码率YUV<;转>;
- OC代码编译成c++代码 编译器命令
- Opengl绘制我们的小屋(三)纹理绘制
- go的精选类库
- HDU4436_str2int
热门文章
- siege4压测脚本示例
- leetcode_1048. Longest String Chain_[DP,动态规划,记忆化搜索]
- Jordan 标准型的推论
- HTML5服务器发送事件(Server-Send Events)
- javaEE(16)_Servlet监听器
- iOS旋屏
- c++ 输入10个数,显示它的平均分
- python中的decorator的作用
- javascript 使用 load 和 unload 事件,解决浏览器打开和关闭时需要做的操作。
- 【php】 php-fpm 配置见解