本文主要是介绍分块#6278. 数列分块入门 2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题：https://loj.ac/problem/6278
修改自：https://www.cnblogs.com/xiongtao/p/9746789.html
//
// main.cpp
// tmpFENKUAI
//
// Created by RogerQian on 2019/6/5.
// Copyright © 2019 RogerQian. All rights reserved.
//#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>using namespace std;const int maxn=50010;
int block,a[maxn],lazy[maxn],pos[maxn];//block块大小，a原数列，pos是a的所属块标记vector<int>v[555];//存放每个块int n;void reset(int x)//对于左右块进行重新排序
{v[pos[x]].clear();for (int i=(pos[x]-1)*block+1; i<=min(pos[x]*block,n); i++) {v[pos[x]].push_back(a[i]);}sort(v[pos[x]].begin(),v[pos[x]].end());
}void update(int l, int r, int c)//更新操作
{for (int i=l; i<=min(pos[l]*block,r); i++) {a[i]+=c;}reset(l);//leftif(pos[l]!=pos[r]){for (int i= (pos[r]-1)*block+1; i<=r; i++) {a[i]+=c;}reset(r);}//rightfor (int i =pos[l]+1; i<=pos[r]-1; i++) {lazy[i]+=c;}//midle
}int query(int l, int r, int c)//查询操作
{int ans=0;for (int i=l; i<=min(pos[l]*block,r); i++) {if(a[i]+lazy[pos[l]]<c) ans++;}//leftif (pos[l]!=pos[r]) {for (int i=(pos[r]-1)*block+1; i<=r; i++) {if (a[i]+lazy[pos[r]]<c) {ans++;}}}//rightfor (int i=pos[l]+1; i<=pos[r]-1; i++) {int x=c-lazy[i];ans+=lower_bound(v[i].begin(),v[i].end(),x)-v[i].begin();//二分查找}return ans;
}int main()
{//int n;scanf("%d",&n);block = sqrt(n);for (int i=1; i<=n; i++) {scanf("%d",&a[i]);//录入pos[i]=(i-1)/block+1;//标记块组v[pos[i]].push_back(a[i]);//压入}for (int i=1; i<=pos[n]; i++) {sort(v[i].begin(),v[i].end());}int opt,l,r,c;for (int i=1; i<=n; i++) {scanf("%d%d%d%d",&opt,&l,&r,&c);if (opt==0) update(l,r,c);else printf("%d\n",query(l,r,c*c));}return 0;
}这篇关于分块#6278. 数列分块入门 2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
