#6281. 数列分块入门 5 - 题目 - LibreOJ (loj.ac)
区间开方，区间求和题。
显然，针对区间维护开方操作很难做到，于是考虑其值的性质，显然，int范围内的值最多开方6次就会变为1，之后再开方依然为1，于是考虑暴力维护一个区间内的值是否全部为1即可，全部为1标记上之后再遇到O(1)处理即可。复杂度大概就为O(n*6+n*sqrt(n))
代码如下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1e5)+5;
int a[maxn];
int sum[maxn];
int bel[maxn];
int L[maxn],R[maxn];
bool tag[maxn];
void build(int n){
int block=sqrt(n);
int num=n/block;
if(n%block)num++;
for(int i=1;i<=num;i++){
L[i]=(i-1)*block+1;
R[i]=i*block;
for(int j=L[i];j<=R[i];j++){
bel[j]=i;
sum[i]+=a[j];
}
}
}
void update(int l,int r){
if(bel[l]==bel[r]){
for(int i=l;i<=r;i++){
if(tag[bel[i]])break;
sum[bel[i]]=sum[bel[i]]-a[i]+int(sqrt(a[i]));
a[i]=int(sqrt(a[i]));
}
}
else{
for(int i=l;i<=R[bel[l]];i++){
if(tag[bel[i]])break;
sum[bel[i]]=sum[bel[i]]-a[i]+int(sqrt(a[i]));
a[i]=int(sqrt(a[i]));
}
for(int i=L[bel[r]];i<=r;i++){
if(tag[bel[i]])break;
sum[bel[i]]=sum[bel[i]]-a[i]+int(sqrt(a[i]));
a[i]=int(sqrt(a[i]));
}
for(int i=bel[l]+1;i<bel[r];i++){
bool fg=1;
for(int j=L[i];j<=R[i];j++){
if(tag[i])break;
sum[i]=sum[i]-a[j]+int(sqrt(a[j]));
a[j]=int(sqrt(a[j]));
if(a[j]>1)fg=0;
}
if(fg)tag[i]=1;
}
}
}
void calc(int l,int r){
int ans=0;
if(bel[l]==bel[r]){
for(int i=l;i<=r;i++){
ans+=a[i];
}
}
else{
for(int i=l;i<=R[bel[l]];i++){
ans+=a[i];
}
for(int i=L[bel[r]];i<=r;i++){
ans+=a[i];
}
for(int i=bel[l]+1;i<bel[r];i++){
ans+=sum[i];
}
}
cout<<ans<<endl;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
build(n);
for(int i=1;i<=n;i++){
int opt,l,r,c;
cin>>opt>>l>>r>>c;
if(opt){
calc(l,r);
}
else{
update(l,r);
}
}
return 0;
}
#6283. 数列分块入门 7 - 题目 - LibreOJ (loj.ac)
区间乘法，区间加法，单点询问
类似线段树的实现操作，注意先乘后加。当时我调bug花了很久，主要原因是在处理离散块的时候我直接对a数组进行了修改操作，导致标记数组出错，解决方法为直接对离散块所属的完整块进行下放标记的操作（暴力但是可行）
代码如下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1e5)+5;
const int modd=(1e4)+7;
int a[maxn];
int bel[maxn];
int L[maxn],R[maxn];
int tag1[maxn];
int tag2[maxn];
void build(int n){
int block=sqrt(n);
int num=n/block;
if(n%block)num++;
for(int i=1;i<=num;i++){
L[i]=(i-1)*block+1;
R[i]=min(n,i*block);
tag1[i]=0;
tag2[i]=1;
for(int j=L[i];j<=R[i];j++){
bel[j]=i;
}
}
}
void pushdown(int p){
int l=L[bel[p]],r=R[bel[p]];
for(int i=l;i<=r;i++){
a[i]=(a[i]*tag2[bel[p]]+tag1[bel[p]])%modd;
}
tag1[bel[p]]=0;
tag2[bel[p]]=1;
}
void add(int l,int r,int c){
if(bel[l]==bel[r]){
pushdown(l);
for(int i=l;i<=r;i++){
a[i]=(a[i]+c)%modd;
}
}
else{
pushdown(l);
for(int i=l;i<=R[bel[l]];i++){
a[i]=(a[i]+c)%modd;
}
pushdown(r);
for(int i=L[bel[r]];i<=r;i++){
a[i]=(a[i]+c)%modd;
}
for(int i=bel[l]+1;i<bel[r];i++){
tag1[i]=(tag1[i]+c)%modd;
}
}
}
void multiply(int l,int r,int c){
if(bel[l]==bel[r]){
pushdown(l);
for(int i=l;i<=r;i++){
a[i]=(a[i]*c)%modd;
}
}
else{
pushdown(l);
for(int i=l;i<=R[bel[l]];i++){
a[i]=(a[i]*c)%modd;
}
pushdown(r);
for(int i=L[bel[r]];i<=r;i++){
a[i]=(a[i]*c)%modd;
}
for(int i=bel[l]+1;i<bel[r];i++){
tag1[i]=(tag1[i]*c)%modd;
tag2[i]=(tag2[i]*c)%modd;
}
}
}
void calc(int i){
int ans=(a[i]*tag2[bel[i]]+tag1[bel[i]])%modd;
cout<<ans<<endl;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
build(n);
for(int i=1;i<=n;i++){
int opt,l,r,c;
cin>>opt>>l>>r>>c;
if(opt==0){
add(l,r,c);
}
if(opt==1){
multiply(l,r,c);
}
if(opt==2){
calc(r);
}
}
return 0;
}
#6284. 数列分块入门 8 - 题目 - LibreOJ (loj.ac)
区间询问等于一个数 c 的元素，并将这个区间的所有元素改为 c。
这题我折腾了挺久。思路为标记每个区间是否为同一个值，若是则标记为该值，否则标记为1e11。之后在分块的模板中再分三种情况进行分析。1.该区间全部为c，2.该区间全部为另外一个值，3.该区间的值不统一。注意点：在离散块情况2进行修改操作时需要先进行标记下放操作。
代码如下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1e5)+5;
ll a[maxn];
ll tag[maxn];
ll bel[maxn];
ll L[maxn],R[maxn];
void build(ll n){
ll block=sqrt(n);
ll num=n/block;
if(n%block)num++;
for(int i=1;i<=num;i++){
L[i]=(i-1)*block+1;
R[i]=min(n,i*block);
tag[i]=1e11;
for(int j=L[i];j<=R[i];j++){
bel[j]=i;
}
}
}
void pushdown(int p){
for(int i=L[p];i<=R[p];i++){
a[i]=tag[p];
}
}
void ope(ll l,ll r,ll c){
ll ans=0;
if(bel[l]==bel[r]){
if(tag[bel[l]]==c){
ans+=r-l+1;
}
else if(tag[bel[l]]!=1e11){
pushdown(bel[l]);
for(int i=l;i<=r;i++){
a[i]=c;
}
tag[bel[l]]=1e11;
}
else{
for(int i=l;i<=r;i++){
if(a[i]==c)ans++;
else a[i]=c;
}
}
}
else{
if(tag[bel[l]]==c){
ans+=R[bel[l]]-l+1;
}
else if(tag[bel[l]]!=1e11){
pushdown(bel[l]);
for(int i=l;i<=R[bel[l]];i++){
a[i]=c;
}
tag[bel[l]]=1e11;
}
else{
for(int i=l;i<=R[bel[l]];i++){
if(a[i]==c)ans++;
else a[i]=c;
}
}
if(tag[bel[r]]==c){
ans+=r-L[bel[r]]+1;
}
else if(tag[bel[r]]!=1e11){
pushdown(bel[r]);
for(int i=L[bel[r]];i<=r;i++){
a[i]=c;
}
tag[bel[r]]=1e11;
}
else{
for(int i=L[bel[r]];i<=r;i++){
if(a[i]==c)ans++;
else a[i]=c;
}
}
for(int i=bel[l]+1;i<bel[r];i++){
if(tag[i]==c){
ans+=(R[i]-L[i]+1);
}
else if(tag[i]==1e11){
for(int j=L[i];j<=R[i];j++){
if(a[j]==c)ans++;
else a[j]=c;
}
tag[i]=c;
}
else{
tag[i]=c;
}
}
}
cout<<ans<<endl;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
build(n);
for(int i=1;i<=n;i++){
ll l,r,c;
cin>>l>>r>>c;
ope(l,r,c);
}
return 0;
}
