[LOJ6278]数列分块入门 2
2024-09-08 03:10:40
题目大意:
给你一个长度为$n(n\leq 50000)$的序列$A$,支持进行以下两种操作:
1.将区间$[l,r]$中所有数加上$c$;
2.询问区间$[l,r]$中小于$c^2$的数的个数。
思路:
分块。
对于整块的数据打标记,零散的数据直接修改。同时维护同一块中从小到大的顺序,统计时对于同一块中的数二分答案,零散的数直接统计。
#include<cmath>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<functional>
inline int getint() {
register char ch;
register bool neg=false;
while(!isdigit(ch=getchar())) if(ch=='-') neg=true;
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return neg?-x:x;
}
const int N=;
int val[N],s[N],tag[N],bel[N],begin[N],end[N];
inline bool cmp(const int &a,const int &b) {
return val[a]+tag[bel[a]]<val[b]+tag[bel[b]];
}
inline void modify(const int &l,const int &r,const int &c) {
if(bel[l]==bel[r]) {
for(register int i=l;i<=r;i++) val[i]+=c;
std::sort(&s[begin[bel[l]]],&s[end[bel[l]]]+,cmp);
return;
}
for(register int i=l;bel[i]==bel[l];i++) val[i]+=c;
std::sort(&s[begin[bel[l]]],&s[end[bel[l]]]+,cmp);
for(register int i=r;bel[i]==bel[r];i--) val[i]+=c;
std::sort(&s[begin[bel[r]]],&s[end[bel[r]]]+,cmp);
for(register int i=bel[l]+;i<bel[r];i++) tag[i]+=c;
}
inline int query(const int &l,const int &r,const int &c) {
int ret=;
val[]=c*c;
if(bel[l]==bel[r]) {
for(register int i=l;i<=r;i++) {
if(val[i]+tag[bel[i]]<val[]) ret++;
}
return ret;
}
for(register int i=l;bel[i]==bel[l];i++) {
if(val[i]+tag[bel[i]]<val[]) ret++;
}
for(register int i=r;bel[i]==bel[r];i--) {
if(val[i]+tag[bel[i]]<val[]) ret++;
}
for(register int i=bel[l]+;i<bel[r];i++) {
ret+=std::lower_bound(&s[begin[i]],&s[end[i]]+,,cmp)-&s[begin[i]];
}
return ret;
}
int main() {
const int n=getint(),block=sqrt(n);
for(register int i=;i<=n;i++) {
val[i]=getint();
bel[i]=i/block;
s[i]=i;
if(!begin[bel[i]]) begin[bel[i]]=i;
end[bel[i]]=i;
}
for(register int i=;i<=bel[n];i++) {
std::sort(&s[begin[i]],&s[end[i]]+,cmp);
}
for(register int i=;i<n;i++) {
const int opt=getint(),l=getint(),r=getint(),c=getint();
if(opt) {
printf("%d\n",query(l,r,c));
} else {
modify(l,r,c);
}
}
return ;
}
最新文章
- 奇怪的Hibernate——当?遇上%
- dotnet run是如何启动asp.net core站点的
- ELK 信息统计分析-2
- js+jquery检测用户浏览器型号(包括对360浏览器的检测)
- android 模拟微信消息框 BaseAdapter()方法 [2]
- silverlight datagrid绑定匿名类
- CSS中 清除浮动解决“包含问题”
- # .NET切面编程——PostSharp
- 虚拟机iso整理
- 【Solution】MySQL 5.8 this is incompatible with sql_mode=only_full_group_by
- 快乐!ajax入门(1)
- ";hello,world";———C++入门有感
- springsecurity 源码解读之 AnonymousAuthenticationFilter
- UVA10410-Tree Reconstruction(BFS序和DFS序的性质)
- 004_浅析Python的GIL和线程安全
- (转)游戏引擎中三大及时光照渲染方法介绍(以unity3d为例)
- predict_proba 的使用
- python进阶之关键字和运算符触发魔法方法
- oracle数据库恢复归档脚本
- unity, particle play once and destroy