数列分块入门 2
题目描述
给出一个长为 的数列，以及 个操作，操作涉及区间加法，询问区间内小于某个值 的元素个数。
输入格式
第一行输入一个数字n。
第二行输入n个数字，第i个数字为a[i]，以空格隔开。
接下来输入n行询问，每行输入四个数字 op、l、r、c，以空格隔开。
若 op==0，表示将位于[l,r] 的之间的数字都加 c。
若 op==1，表示询问 [l,r]中，小于c*c的数字的个数。
输出格式
对于每次询问，输出一行一个数字表示答案。
样例输入
4 1 2 2 3 0 1 3 1 1 1 3 2 1 1 4 1 1 2 3 2
样例输出
3 0 2
数据范围
n<=5e4, 答案和其他数据在int范围之内
分析：
加法操作同题目1一样维护加法标记。 查询操作比较麻烦。 这里用的是另外开一个vector数组保存每一块的数据的有序情况，每块sqrt(n)个数。 查询的时候直接lower_bound二分查询。 最后注意每次修改原来的数据数组的时候要 维护存放有序块数组vector。
我的代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
typedef long long ll
;
const int inf
=0x3f3f3f3f;
const int inn
=0x80808080;
using namespace std
;
const int maxm
=5e4+5;
int a
[maxm
];
int add
[maxm
];
int belong
[maxm
];
int l
[maxm
],r
[maxm
];
int block
,num
;
int n
;
vector
<int>temp
[300];
void reset(int pos
){
temp
[pos
].clear();
for(int i
=l
[pos
];i
<=r
[pos
];i
++){
temp
[pos
].push_back(a
[i
]);
}
sort(temp
[pos
].begin(),temp
[pos
].end());
}
void build(){
block
=sqrt(n
);
num
=n
/block
;
if(n
%block
)num
++;
for(int i
=1;i
<=num
;i
++){
l
[i
]=(i
-1)*block
+1;
r
[i
]=i
*block
;
add
[i
]=0;
reset(i
);
}
r
[num
]=n
;
for(int i
=1;i
<=n
;i
++){
belong
[i
]=(i
-1)/block
+1;
}
}
void update(int x
,int y
,int val
){
if(belong
[x
]==belong
[y
]){
for(int i
=x
;i
<=y
;i
++){
a
[i
]+=val
;
}
reset(belong
[x
]);
return ;
}
for(int i
=x
;i
<=r
[belong
[x
]];i
++){
a
[i
]+=val
;
}
reset(belong
[x
]);
for(int i
=l
[belong
[y
]];i
<=y
;i
++){
a
[i
]+=val
;
}
reset(belong
[y
]);
for(int i
=belong
[x
]+1;i
<belong
[y
];i
++){
add
[i
]+=val
;
}
}
int ask(int x
,int y
,int val
){
int ans
=0;
if(belong
[x
]==belong
[y
]){
for(int i
=x
;i
<=y
;i
++){
if(a
[i
]+add
[belong
[i
]]<val
){
ans
++;
}
}
return ans
;
}
for(int i
=x
;i
<=r
[belong
[x
]];i
++){
if(a
[i
]+add
[belong
[i
]]<val
){
ans
++;
}
}
for(int i
=l
[belong
[y
]];i
<=y
;i
++){
if(a
[i
]+add
[belong
[i
]]<val
){
ans
++;
}
}
for(int i
=belong
[x
]+1;i
<belong
[y
];i
++){
ans
+=lower_bound(temp
[i
].begin(),temp
[i
].end(),val
-add
[i
])-temp
[i
].begin();
}
return ans
;
}
int main(){
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++){
scanf("%d",&a
[i
]);
}
build();
while(n
--){
int d
,x
,y
,c
;
scanf("%d%d%d%d",&d
,&x
,&y
,&c
);
if(d
==0){
update(x
,y
,c
);
}else{
printf("%d\n",ask(x
,y
,c
*c
));
}
}
return 0;
}
