loj数列分块入门-程序员宅基地
技术标签： # 数据结构
数列分块入门
入门 1-区间加法-单点查询
ll n,a[maxn],lazy[maxn];
int main() {
n = read;
for(int i=1; i<=n; i++) a[i] = read;
int blk = sqrt(n);
for(int ii=1; ii<=n; ii++) {
int op = read,l = read,r = read,c = read;
if( op == 0) {
for(int i=l; i<min(r+1,(l/blk+1)*blk); i++) {
a[i] += c;
}
for(int i=l/blk+1; i<r/blk; i++) {
lazy[i] += c;
}
if(l / blk != r / blk) {
for(int i=r/blk*blk; i<=r; i++) a[i] += c;
}
} else {
printf("%lld\n",a[r] + lazy[r/blk]);
}
}
return 0;
}
/**
4
1 2 2 3
0 1 3 1
1 0 1 0
0 1 2 2
1 0 2 0
2
5
**/
入门 2-区间加法-区间查询
const int maxn = 1e5 + 7;
ll n, a[maxn];
vector<ll> vet[maxn];
ll blk, lazy[maxn], b[maxn];
void reget(int id) {
vet[id].clear();
for (int i = (id - 1) * blk + 1; i <= min(n, id * blk); i++) {
vet[id].push_back(a[i]);
}
sort(vet[id].begin(), vet[id].end());
}
void update(ll l, ll r, ll c) {
for (int i = l; i <= min(b[l]*blk, r); i++)
a[i] += c;
reget(b[l]);
if (b[l] != b[r]) {
for (int i = (b[r] - 1) * blk + 1; i <= r; i++)
a[i] += c;
reget(b[r]);
}
for (int i = b[l] + 1; i <= b[r] - 1; i++) {
lazy[i] += c;
}
}
ll query(ll l, ll r, ll val) {
ll ret = 0;
for (int i = l; i <= min(b[l]*blk, r); i++) {
if (a[i] + lazy[b[l]] < val)
++ ret;
}
if (b[l] != b[r]) {
for (int i = (b[r] - 1) * blk + 1; i <= r; i++) {
if (a[i] + lazy[b[r]] < val)
++ ret;
}
}
for (int i = b[l] + 1; i <= b[r] - 1; i++) {
int get = val - lazy[i];
// ret += upper_bound(vet[i].begin(),vet[i].end(),get) - lower_bound(vet[i].begin(),vet[i].end(),get);
ret += lower_bound(vet[i].begin(), vet[i].end(), get) - vet[i].begin();
}
return ret;
}
int main() {
n = read;
for (int i = 1; i <= n; i++)
a[i] = read;
blk = sqrt(n);
for (int i = 1; i <= n; i++) {
b[i] = (i - 1) / blk + 1;
vet[b[i]].push_back(a[i]);
}
for (int i = 1; i <= b[n]; i++)
sort(vet[i].begin(), vet[i].end());
for (int i = 1; i <= n; i++) {
int op = read, l = read, r = read, c = read;
if (op == 0)
update(l, r, c);
else
printf("%lld\n", query(l, r, c * c));
}
return 0;
}
/**
4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2
3
0
2
**/
入门 3-区间加法-单点查询
const int maxn = 1e5 + 7;
ll n, a[maxn];
vector<ll> vet[maxn];
ll blk, lazy[maxn], b[maxn];
void reget(int id) {
vet[id].clear();
for (int i = (id - 1) * blk + 1; i <= min(n, id * blk); i++) {
vet[id].push_back(a[i]);
}
sort(vet[id].begin(), vet[id].end());
}
void update(ll l, ll r, ll c) {
for (int i = l; i <= min(b[l]*blk, r); i++)
a[i] += c;
reget(b[l]);
if (b[l] != b[r]) {
for (int i = (b[r] - 1) * blk + 1; i <= r; i++)
a[i] += c;
reget(b[r]);
}
for (int i = b[l] + 1; i <= b[r] - 1; i++) {
lazy[i] += c;
}
}
ll query(ll l, ll r, ll val) {
ll ret = -1;
for (int i = l; i <= min(b[l]*blk, r); i++) {
if (a[i] + lazy[b[l]] < val)
ret = max(ret, a[i] + lazy[b[l]]);
}
if (b[l] != b[r]) {
for (int i = (b[r] - 1) * blk + 1; i <= r; i++) {
if (a[i] + lazy[b[r]] < val)
ret = max(ret, a[i] + lazy[b[r]]);
}
}
for (int i = b[l] + 1; i <= b[r] - 1; i++) {
ll get = val - lazy[i];
vector<ll>::iterator l = lower_bound(vet[i].begin(), vet[i].end(), get);
if (l == vet[i].begin())
continue;
l --;
ret = max(ret, *l + lazy[i]);
}
return ret;
}
int main() {
n = read;
for (int i = 1; i <= n; i++)
a[i] = read;
blk = sqrt(n);
for (int i = 1; i <= n; i++) {
b[i] = (i - 1) / blk + 1;
vet[b[i]].push_back(a[i]);
}
for (int i = 1; i <= b[n]; i++)
sort(vet[i].begin(), vet[i].end());
for (int i = 1; i <= n; i++) {
int op = read, l = read, r = read, c = read;
if (op == 0)
update(l, r, c);
else
printf("%lld\n", query(l, r, c));
// debug(i);
}
return 0;
}
/**
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4
3
-1
**/
入门 4-区间加法-区间查询
ll n,a[maxn];
ll blk,lazy[maxn],b[maxn],sum[maxn];
void update(ll l,ll r,ll c) {
for(int i=l; i<=min(b[l]*blk,r); i++) a[i] += c,sum[b[l]] += c;
if(b[l] != b[r]) {
for(int i=(b[r] - 1) * blk+1; i<=r; i++) a[i] += c,sum[b[r]] += c;
}
for(int i=b[l]+1; i<=b[r] - 1; i++) {
lazy[i] += c;
}
}
ll query(ll l,ll r,ll val) {
ll ret = 0;
for(int i=l; i<=min(b[l]*blk,r); i++) {
ret += a[i] + lazy[b[l]];
ret %= (val + 1);
}
if(b[l] != b[r]) {
for(int i=(b[r]-1)*blk+1; i<=r; i++) {
ret += a[i] + lazy[b[r]];
ret %= (val + 1);
}
}
for(int i=b[l]+1; i<=b[r]-1; i++) {
ll add = lazy[i] * blk % (val + 1);
ret += (sum[i] + add) % (val + 1);
ret %= (val + 1);
}
return ret;
}
int main() {
n = read;
for(int i=1; i<=n; i++) a[i] = read;
blk = sqrt(n);
for(int i=1; i<=n; i++) {
b[i] = (i - 1) / blk + 1;
sum[b[i]] += a[i];
}
for(int i=1; i<=n; i++) {
int op = read,l = read,r = read,c = read;
if(op == 0) update(l,r,c);
else printf("%lld\n",query(l,r,c));
}
return 0;
}
/**
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4
1
4
**/
入门 5-区间开方-区间查询
ll n,a[maxn];
ll blk,lazy[maxn],b[maxn],sum[maxn];
bool vis[maxn];
bool check(int id) {
if(vis[id]) return true;
for(int i=(id-1)*blk+1; i<=min(n,blk*id); i++) {
if(a[i] > 1) return false;
}
return vis[id] = 1;
}
void update(ll l,ll r) {
if(!check(b[l])) {
for(int i=l; i<=min(b[l]*blk,r); i++) {
sum[b[l]] -= a[i];
a[i] = sqrt(a[i]);
sum[b[l]] += a[i];
}
}
if(b[l] != b[r] && !check(b[r])) {
for(int i=(b[r]-1)*blk+1; i<=r; i++) {
sum[b[r]] -= a[i];
a[i] = sqrt(a[i]);
sum[b[r]] += a[i];
}
}
for(int i=b[l]+1; i<=b[r]-1; i++) {
if(!check(i)) {
sum[i] = 0;
for(int j=(i-1)*blk+1; j<=i*blk; j++) {
a[j] = sqrt(a[j]);
sum[i] += a[j];
}
}
}
}
ll query(ll l,ll r) {
ll ret = 0;
for(int i=l; i<=min(b[l]*blk,r); i++) {
ret += a[i];
}
if(b[l] != b[r]) {
for(int i=(b[r]-1)*blk+1; i<=r; i++) {
ret += a[i];
}
}
for(int i=b[l]+1; i<=b[r]-1; i++) {
ret += sum[i];
}
return ret;
}
int main() {
n = read;
for(int i=1; i<=n; i++) a[i] = read;
blk = sqrt(n);
for(int i=1; i<=n; i++) {
b[i] = (i - 1) / blk + 1;
sum[b[i]] += a[i];
}
for(int i=1; i<=n; i++) {
int op = read,l = read,r = read,c = read;
if(op == 0) update(l,r);
else printf("%lld\n",query(l,r));
}
return 0;
}
/**
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4
6
2
**/
入门 6-单点插入-单点查询
typedef pair<int,int> PII;
ll n,a[maxn];
ll blk,lazy[maxn],b[maxn],sum[maxn],tot;
vector<int> vet[maxn];
void reBuild() {
int p = 0;
for(int i=1; i<=tot; i++) {
for(int val : vet[i]) {
a[++p] = val;
}
vet[i].clear();
}
blk = sqrt(p);
tot = ceil(1.0 * p / blk);
for(int i=1; i<=p; i++) {
b[i] = (i - 1) / blk + 1;
vet[b[i]].push_back(a[i]);
}
}
PII query(ll r) {
for(int i=1; i<=tot; i++) {
if(r > vet[i].size()) r -= vet[i].size();
else return {
i,r-1};
}
}
void insert(ll l,ll r) {
PII t = query(l);
vet[t.first].insert(vet[t.first].begin() + t.second,r);
if(vet[t.first].size() > 10 * blk) reBuild();
}
int main() {
n = read;
for(int i=1; i<=n; i++) a[i] = read;
blk = sqrt(n);
tot = ceil(1.0*n / blk);
for(int i=1; i<=n; i++) {
b[i] = (i - 1) / blk + 1;
vet[b[i]].push_back(a[i]);
}
for(int i=1; i<=n; i++) {
int op = read,l = read,r = read,c = read;
if(op == 0) insert(l,r);
else {
PII t = query(r);
printf("%d\n",vet[t.first][t.second]);
}
}
return 0;
}
/**
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4
2
3
**/
入门 7-区间乘法-区间加法-单点查询
const int maxn = 1e5 + 7;
const int mod = 10007;
ll n,a[maxn];
ll blk,add[maxn],b[maxn],sum[maxn],mul[maxn];
void pushDown(int id) {
for(int i=(id-1) * blk + 1; i<=min(id * blk,n); i++) {
a[i] = (a[i] * mul[id] % mod + add[id] + mod) % mod;
}
mul[id] = 1;
add[id] = 0;
}
void add_mul(int l,int r,ll val,int op) {
pushDown(b[l]);
for(int i=l; i<=min(b[l]*blk,1LL*r); i++) {
if(op) a[i] = (a[i] * val) % mod;
else a[i] = (a[i] + val) % mod;
}
if(b[l] != b[r]) {
pushDown(b[r]);
for(int i=(b[r]-1)*blk + 1; i<=r; i++) {
if(op) a[i] = (a[i] * val) % mod;
else a[i] = (a[i] + val) % mod;
}
}
for(int i=b[l]+1; i<=b[r]-1; i++) {
if(op) mul[i] = (mul[i] * val) % mod,add[i] = (add[i] * val) % mod;
else add[i] = (add[i] + val) % mod;
}
}
ll query(int r) {
ll ret = 0;
ret = (a[r] * mul[b[r]] % mod + add[b[r]]) % mod;
return ret;
}
int main() {
n = read;
for(int i=1; i<=n; i++) a[i] = read;
blk = sqrt(n);
for(int i=1; i<=n; i++) {
b[i] = (i - 1) / blk + 1;
mul[b[i]] = 1;
add[b[i]] = 0;
}
for(int i=1; i<=n; i++) {
int op = read,l = read,r = read,c = read;
if(op == 2) {
printf("%lld\n",query(r));
} else {
add_mul(l,r,c,op);
}
}
return 0;
}
/**
7
1 2 2 3 9 3 2
0 1 3 1
2 1 3 1
1 1 4 4
0 1 7 2
1 2 6 4
1 1 6 5
2 2 6 4
3
100
**/
入门 8-区间修改-区间查询
ll n,a[maxn];
ll blk,add[maxn],b[maxn],upd[maxn];
void reset(int id) {
if(upd[id] == -1) return ;
for(int i=(id-1) * blk+1; i<=min(id*blk,n); i++) {
a[i] = upd[id];
}
upd[id] = -1;
}
ll getSet(int l,int r,ll val) {
ll ans = 0;
reset(b[l]);
for(int i=l; i<=min(b[l]*blk,1LL*r); i++) {
ans += a[i] == val;
a[i] = val;
}
if(b[l] != b[r]) {
reset(b[r]);
for(int i=(b[r]-1)*blk + 1; i<=r; i++) {
ans += a[i] == val;
a[i] = val;
}
}
for(int i=b[l]+1; i<=b[r]-1; i++) {
if(upd[i] == -1) {
for(int j=(i-1)*blk+1; j<=i*blk; j++) {
ans += a[j] == val;
}
} else ans += upd[i] == val?blk:0;
upd[i] = val;
}
return ans;
}
int main() {
n = read;
for(int i=1; i<=n; i++) a[i] = read;
blk = sqrt(n);
for(int i=1; i<=n; i++) {
b[i] = (i - 1) / blk + 1;
upd[b[i]] = -1;
}
for(int i=1; i<=n; i++) {
int l = read,r = read,c = read;
ll ans = getSet(l,r,c);
printf("%lld\n",ans);
}
return 0;
}
/**
4
1 2 2 4
1 3 1
1 4 4
1 2 2
1 4 2
1
1
0
2
**/
入门 9-区间查询众数
#define Clear(x,val) memset(x,val,sizeof x)
ll n,a[maxn],ans[2007][2007],b[maxn],blk,cnt[maxn],num;
vector<int> vet[maxn];
map<int,int> vis,val;
void get(int id) {
Clear(cnt,0);
int mx = 0,res = 0;
for(int i=(id-1) * blk + 1; i<=n; i++) {
int to = b[i];///cur is the b[i]-th blk
++ cnt[a[i]];/// the amt ++
if(cnt[a[i]] > mx || (cnt[a[i]] == mx && val[a[i]] < val[res])) {
res = a[i];/// set the cur mx value
mx = cnt[a[i]];
}
ans[id][to] = res;/// from blk id -> blk to the ans = res
}
}
int getNum(int l,int r,int x) {
int ret = 0;
ret = upper_bound(vet[x].begin(),vet[x].end(),r) - lower_bound(vet[x].begin(),vet[x].end(),l);/// amount of x
return ret;
}
ll query(int l,int r) {
ll ret = ans[b[l] + 1][b[r] - 1];// center blks
int mx = getNum(l,r,ret);// get the amount of this
for(int i=l; i<=min(r*1LL,b[l]*blk); i++) {
int amt = getNum(l,r,a[i]);
if(amt > mx || (amt == mx && val[a[i]] < val[ret])) {
///val[ret]
ret = a[i];
mx = amt;
}
}
if(b[l] != b[r]) {
for(int i = (b[r] - 1) * blk + 1; i<=r; i++) {
int amt = getNum(l,r,a[i]);
if(amt > mx || (amt == mx && val[a[i]] < val[ret])) {
ret = a[i];
mx = amt;
}
}
}
return val[ret];
}
int main() {
n = read;
blk = sqrt(n);
blk = 80;
for(int i=1; i<=n; i++) {
a[i] = read;
b[i] = (i - 1) / blk + 1;
if(!vis[a[i]]) {
vis[a[i]] = ++ num;
val[num] = a[i];///¶ÔÓ¦ÏÂ
}
a[i] = vis[a[i]];
vet[a[i]].push_back(i);
}
for(int i=1; i<=b[n]; i++) get(i); /// get the i-th blk
for(int i=1; i<=n; i++) {
int l = read,r = read;
if(l > r) swap(l,r);
ll ans = query(l,r);
printf("%lld\n",ans);
}
return 0;
}
/**
4
1 2 2 4
1 2
1 4
2 4
3 4
1
2
2
2
**/
七夕快乐
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
智能推荐
TeamTalk部署问题及解决方案_teamtalk ../daeml: 没有那个文件或目录-程序员宅基地
文章浏览阅读727次。TeamTalk部署问题及解决方案1、部分源下载地址2、编译安装libiconv报错3、找不到tt4、编译im-server5、缺少daeml6、找不到mysql.h7、centos7 mini 安装后无法连接到网络8、使用mwget提高下载速度9、nginx: [emerg] unknown log format "access" in错误解决方法10、PHP报错1、部分源下载地址gmpwget ftp://ftp.gnu.org/gnu/gmp/gmp-5.1.3.tar.gzmpfrwge_teamtalk ../daeml: 没有那个文件或目录
java中将多文件字节流压缩成zip-程序员宅基地
文章浏览阅读2.4k次。java中将多文件字节流压缩成zip核心就是使用java.util.zip包中的ZipOutputStream直接上核心代码/** * * @param zipFilePath zip保存路径 * @param zipFileName zip文件名 * @param byteList 文件字节码Map，k:fileNam..._java将多个字节流压缩成zip
Python-Django毕业设计在线考试系统（程序+Lw)_django在线考试系统-程序员宅基地
文章浏览阅读141次。该项目含有源码、文档、程序、数据库、配套开发软件、软件安装教程项目运行环境配置：Pychram社区版+ python3.7.7 + Mysql5.7 + HBuilderX+list pip+Navicat11+Django+nodejs。项目技术：django + python+ Vue 等等组成，B/S模式 +pychram管理等等。环境需要1.运行环境：最好是python3.7.7，我们在这个版本上开发的。其他版本理论上也可以。2.pycharm环境：pycharm都可以。_django在线考试系统
Java关键字(二)——native_nativeadd-程序员宅基地
文章浏览阅读612次。 本篇博客我们将介绍Java中的一个关键字——native。 native 关键字在 JDK 源码中很多类中都有，在 Object.java类中，其 getClass() 方法、hashCode()方法、clone() 方法等等都是用 native 关键字修饰的。 public final native Class&l..._nativeadd
【HarmonyOS HiSpark IPC DIY Camera试用连载4 】 鸿蒙OS内核liteos-a如何启动第一个用户进程init_lite_lite_user_sec_entry原理-程序员宅基地
文章浏览阅读2.6k次。【HarmonyOS HiSpark IPC DIY Camera试用连载4 】 鸿蒙OS内核如何启动第一个用户进程init_lite1. 鸿蒙OS编译知识2. 从编译过程看鸿蒙OS代码结构3. 第一个用户态进程init_lite4. Init_lite是如何被kernel调用的?1. 鸿蒙OS编译知识(原理引自中科创达OpenHarmony研究组 鸿蒙OS开源代码精要解读之——init)OpenHarmony源码编译系统使用了google开发的gn工具以及ninjia。这二者结合起来比传统的make_lite_user_sec_entry原理
TheiSfM - Win7/VS2015/CMake_theia-sfm-程序员宅基地
文章浏览阅读1k次。Instruction for building TheiaSfM._theia-sfm
随便推点
html符号中文含义大全特殊,中文标点符号大全名称-程序员宅基地
文章浏览阅读2.6k次。中文的标点符号包括句号，逗号，感叹号，问号，引号，冒号等等，接下来分享常见的中文标点符号名称。常见的中文标点符号1.句号：【。】用于句子末尾，表示陈述语气。有时也可表示较缓和的祈使语气和感叹语气。2.问号：【？】用于句子末尾，表示疑问语气(包括反问、设问等疑问类型)。在多个问句连用或表达疑问语气加重时，可叠用问号。3.叹号：【！】用于句子末尾，主要表示感叹语气，有时也可表示强烈的祈使语气、反问语气..._html顿号
【加密算法】5 种常见的摘要、加密算法_摘要加密-程序员宅基地
文章浏览阅读994次。那么上面提到的这些能力，我们都可以利用哪些加密算法来实现呢？咱们接着往下看。加密算法整体上可以分为：不可逆加密、可逆加密。可逆加密又可以分为：对称加密、非对称加密。_摘要加密
引用形参和指针形参的比较_函数用形参 指针哪个效率高-程序员宅基地
文章浏览阅读1k次。指针与引用看上去完全不同（指针用操作符’*’和’->’，引用使用操作符’.’），但是它们似乎有相同的功能。指针与引用都是让你间接引用其他对象。你如何决定在什么时候使用指针，在什么时候使用引用呢？ 首先，要认识到在任何情况下都不能用指向空值的引用。一个引用必须总是指向某些对象。因此如果你使用一个变量并让它指向一个对象，但是该变量在某些时候也可能不指向任何对象，这时你应该把变量声明为指针_函数用形参 指针哪个效率高
0012-用OpenCV批量读取图片的三种方法-程序员宅基地
文章浏览阅读3.3k次。有时我们需要批量读取图片，所以我们有必要知道怎么在OpenCV开源环境下批量读取图片！批量读取图片的关键是如何让程序知道文件夹下图片的名字！第一种方法：这种方法只针对图片名字有规律的情况，比如：***(0).jpg***(1).jpg***(2).jpg***(3).jpg..................源代码如下：代码中用到的图片下载链接为：http://pan.b..._opencv批量读取图片
.bat脚本基本命令语法_bat脚本串口发送-程序员宅基地
文章浏览阅读1.1k次。目录批处理的常见命令（未列举的命令还比较多，请查阅帮助信息） 1、REM 和 :: 2、ECHO 和 @ 3、PAUSE 4、ERRORLEVEL 5、TITLE 6、COLOR 7、mode 配置系统设备 8、GOTO 和 : 9、FIND 10、START 11、assoc 和 ft..._bat脚本串口发送
自己实现一个队列(Java)_java实现一个队列 匀速处理-程序员宅基地
文章浏览阅读1.5k次。思路：1、链表实现，不用考虑扩容问题2、节点维护next指针，每次删除元素，删除头结点，插入元素队尾插入代码：package com.datastructure.stackqueue;/** * 实现一个栈，自定义栈，用链表实现，方便扩容 */public class DefineQueue<T> { private Node<T> ..._java实现一个队列 匀速处理