【題目描述】

給出一個(gè)長(zhǎng)為 n 的數(shù)列，以及 n 個(gè)操作，操作涉及區(qū)間加法，詢問區(qū)間內(nèi)小于某個(gè)值 x 的元素個(gè)數(shù)

【輸入格式】

第一行輸入一個(gè)數(shù)字 n。

第二行輸入 n?個(gè)數(shù)字，第 i 個(gè)數(shù)字為 ai，以空格隔開。

接下來輸入 n 行詢問，每行輸入四個(gè)數(shù)字 opt、l、r、c，以空格隔開。

若 opt=0，表示將位于 [l,r] 的之間的數(shù)字都加 c。

若 opt=1，表示詢問位于 [l,r] 中小于 c^2 的數(shù)字的個(gè)數(shù)

【輸出格式】

對(duì)于每次詢問，輸出一行一個(gè)數(shù)字表示答案。

【樣例】

樣例輸入
4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2

樣例輸出
3
0
2

【數(shù)據(jù)范圍與提示】

對(duì)于 100%?的數(shù)據(jù)，1<=n<=50000,-2^31<=other,ans<=2^31-1。

【源代碼】

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 100000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std; int n; int block,sum;//block為塊的長(zhǎng)度,sum為塊的個(gè)數(shù) int a[N];//存放數(shù)列元素 int pos[N],tag[N];//pos記錄第i個(gè)元素在第幾個(gè)塊中,tag為操作標(biāo)記 int ans[N];//維護(hù)整塊和 vector<int> v[N]; void init(){block=sqrt(n);//塊的長(zhǎng)度sum=n/block;//塊個(gè)數(shù)if(n%block)sum++;for(int i=1;i<=n;i++){pos[i]=(i-1)/block+1;//第i個(gè)元素在第幾塊中v[pos[i]].push_back(a[i]);//保存每個(gè)數(shù)分塊的序號(hào)}for(int i=1;i<=sum;i++)//對(duì)整塊進(jìn)行排序sort(v[i].begin(),v[i].end()); } void resort(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 x){for(int i=L;i<=min(pos[L]*block,R);i++)//左邊的邊角料a[i]+=x;resort(L);//對(duì)不完整塊排序if(pos[L]!=pos[R]){//存在右區(qū)間才遍歷，防止重復(fù)計(jì)算for(int i=(pos[R]-1)*block+1;i<=R;i++)//右邊的邊角料a[i]+=x;resort(R);//對(duì)不完整塊排序}for(int i=pos[L]+1;i<=pos[R]-1;i++)//中間的整塊tag[i]+=x; } int query(int L,int R,int x){int res=0;for(int i=L;i<=min(pos[L]*block,R);i++)//左邊的邊角料if(a[i]+tag[pos[i]]<x)res++;if(pos[L]!=pos[R])//存在右區(qū)間才遍歷，防止重復(fù)計(jì)算for(int i=(pos[R]-1)*block+1;i<=R;i++)//右邊的邊角料if(a[i]+tag[pos[i]]<x)res++;for(int i=pos[L]+1;i<=pos[R]-1;i++){//中間的整塊進(jìn)行二分查找int temp=x-tag[i];res+=lower_bound(v[i].begin(),v[i].end(),temp)-v[i].begin();}return res; } int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);init();for(int i=1;i<=n;i++){int op;int left,right,x;scanf("%d",&op);scanf("%d%d%d",&left,&right,&x);if(op==0)update(left,right,x);else if(op==1)printf("%d\n",query(left,right,x*x));}return 0; }

?

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的数列分块入门 2（LibreOj-6278）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。