生活随笔
收集整理的這篇文章主要介紹了
#6278. 数列分块 2 分块 + 块内二分
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
傳送門
文章目錄
題意：
思路：
真 調一晚上血壓上來了。
考慮第一個操作，塊內打個標記，其他的暴力查詢即可。
考慮第二個操作，講塊內元素排序之后，直接二分查詢。
注意修改元素值的時候需要重新排序，并且在查詢開始前需要先將塊排序。。以及各種小細節。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
;
LL a
[N
],b
[N
];
LL tag
[N
],id
[N
];
int block
;void add(int l
,int r
,int c
) {if(id
[l
]==id
[r
]) {for(int i
=l
;i
<=r
;i
++) a
[i
]+=c
;int sl
=(id
[l
]-1)*block
,sr
=id
[l
]*block
; sr
=min(sr
,n
);for(int i
=sl
+1;i
<=sr
;i
++) b
[i
]=a
[i
];sort(b
+sl
+1,b
+sr
+1);} else {int sl
=id
[l
]*block
,sr
=(id
[r
]-1)*block
;for(int i
=l
;i
<=sl
;i
++) a
[i
]+=c
;for(int i
=sr
+1;i
<=r
;i
++) a
[i
]+=c
;for(int i
=sl
-block
+1;i
<=sl
;i
++) b
[i
]=a
[i
];for(int i
=sr
+1;i
<=sr
+block
;i
++) b
[i
]=a
[i
];sort(b
+sl
-block
+1,b
+sl
+1); sort(b
+sr
+1,b
+min(sr
+block
,n
)+1);for(int i
=id
[l
]+1;i
<=id
[r
]-1;i
++) tag
[i
]+=c
;}
}int query(int l
,int r
,LL c
) {int ans
=0;if(id
[l
]==id
[r
]) {for(int i
=l
;i
<=r
;i
++) ans
+=(a
[i
]+tag
[id
[l
]])<c
;} else {int sl
=id
[l
]*block
,sr
=(id
[r
]-1)*block
;for(int i
=l
;i
<=sl
;i
++) ans
+=(a
[i
]+tag
[id
[l
]])<c
;for(int i
=sr
+1;i
<=r
;i
++) ans
+=(a
[i
]+tag
[id
[r
]])<c
;for(int i
=id
[l
]+1;i
<=id
[r
]-1;i
++) {int sl
=(i
-1)*block
,sr
=i
*block
;ans
+=lower_bound(b
+sl
+1,b
+sr
+1,c
-tag
[i
])-b
-sl
-1;}}return ans
;
}int main()
{
scanf("%d",&n
); block
=sqrt(n
); for(int i
=1;i
<=n
;i
++) scanf("%lld",&a
[i
]),b
[i
]=a
[i
],id
[i
]=(i
-1)/block
+1;for(int i
=1;i
<=id
[n
];i
++) {int sl
=(i
-1)*block
,sr
=i
*block
;sort(b
+sl
+1,b
+sr
+1);}for(int i
=1;i
<=n
;i
++) {int op
,l
,r
,c
; scanf("%d%d%d%d",&op
,&l
,&r
,&c
);if(op
==0) add(l
,r
,c
);else printf("%d\n",query(l
,r
,1ll*c
*c
));}return 0;
}
總結
以上是生活随笔為你收集整理的#6278. 数列分块 2 分块 + 块内二分的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
