洛谷 P2357 守墓人

题干

由题意得,需要区间修改,区间查询

所以这个题可以用树状数组,线段树和分块来做

咱们今天讲分块的做法:

先理解分块,就会发现本题相当于板子题,整活

#include<iostream>
#include<cstdio>
#include<cmath>
#define NUM 200010
using namespace std;
struct dian{
int k;
long long zhi;
};
dian a[NUM];//存下每个点当前的数值zhi以及所在块的编号 
struct kuai{
long long sum,tag;
int l,r;
};
kuai b[1000];//存下每个块的范围(l-r),懒惰标记与块内总和 
int n,m;//点数量与询问数量 
int main(){
cin >> n >> m;
int w = (int)sqrt(n),k = n/w;//w是块的数量,k是每个满块的零点数量 
if( w*w < n ) w++;//凑满 
if( n == 3 ){w = 2;k = 2;}//特殊处理 
if( n == 2 ){w = 2;k = 1;}
//    cout << "块的数量为:" << w << "  每个块里有数量为:" << k << endl; 
int cnt = 0;
for( int i = 1;i <= n;i++ )
cin >> a[i].zhi;
for( int i = 1;i <= w;i++ ){
for( int j = 1;j <= k;j++ ){
a[++cnt].k = i;
if( j == 1 ) b[i].l = cnt;//如果是新块的开头,说明l为该点 
b[i].r = cnt;
b[i].sum += a[cnt].zhi; 
if( cnt >= n ) break;//所有块都已经就位 
        }
}
for( int i = 1;i <= w;i++ )
//        printf( "i = %d,sum = %d,l = %d,r = %d\n",i,b[i].sum,b[i].l,b[i].r );
int l,r,p;
for( int fi = 1;fi <= m;fi++ ){
cin >> cnt;
if( cnt == 1 ){
cin >> l >> r >> p;
bool ok = 0;
for( int i = 1;i <= w;i++ ){ //枚举每个块 
if( ok ) break;
if( l <= b[i].l && b[i].r <= r ) b[i].tag += p;//这个块完全在范围中 
else{
if( l <= b[i].r && b[i].l < l ) //是左边的碎块 
for( int j = l;j <= min(r,b[i].r);j++ ){
a[j].zhi += p;
b[a[j].k].sum += p;
}
if( b[i].l <= r && b[i].r > r ){ //右边的碎块 
ok = 1;//已经到头了 
for( int j = max(l,b[i].l);j <= r;j++ ){
a[j].zhi += p;
b[a[j].k].sum += p;
}
}
}
}
//            cout << "进行了区间修改:\n";
for( int i = 1;i <= n;i++ )
cout << a[i].zhi + b[a[i].k].tag << " ";
cout << endl;
}
if( cnt == 2 ){
cin >> p;
a[1].zhi += p;
b[1].sum += p;
//            cout << "当前主坟为:" << a[1].zhi+b[1].tag << endl;
continue;
}
if( cnt == 3 ){
cin >> p;
a[1].zhi -= p;
b[1].sum -= p;
//            cout << "当前主坟为:" << a[1].zhi+b[1].tag << endl;
continue;
}
if( cnt == 4 ){
//            cout << "各个区间取和:" << endl;
long long ans = 0;bool ok = 0;
cin >> l >> r;
for( int i = 1;i <= w;i++ ){
if( ok ) break;
if( l <= b[i].l && b[i].r <= r ){
ans += b[i].sum;
ans += (b[i].r-b[i].l+1) * b[i].tag;
}
else{
if( l <= b[i].r && b[i].l < l )
for( int j = l;j <= min(r,b[i].r);j++ ){
ans += a[j].zhi + b[a[j].k].tag; //当前每个数的数值加所在块的懒惰标记 
                        }
if( b[i].l <= r && b[i].r > r ){
ok = 1;
for( int j = max(l,b[i].l);j <= r;j++ )
ans += a[j].zhi + b[a[j].k].tag;
}
}
//                cout << ans << " ";
            }
//            cout << endl << "区间和为:";
cout << ans << endl;
continue;
}
if( cnt == 5 ){
//            cout << "主坟墓为:";
cout << a[1].zhi+b[1].tag << endl;
continue;
}
}
return 0;
}

我的理解

然而我的理解WA了,没明白错在哪

网上正解

#include<iostream>
#include<cstdio>
#include<cmath>
#define NUM 200010
using namespace std;
struct dian{
int k;
long long zhi;
};
dian a[NUM];
struct kuai{
long long sum,tag;
int l,r;
};
kuai b[1000];
int n,m;
int main(){
cin >> n >> m;
int w = (int)sqrt(n);//就是每个块的大小 
cout << w << endl;
for( int i = 1;i <= n;i++ ){
cin >> a[i].zhi;
a[i].k = (i-1) / w + 1;//每个点在哪个块,存下 
b[a[i].k].sum += a[i].zhi;
}
cout << endl;
for( int i = 1;i <= n;i++ )
cout << a[i].k << " ";
cout << endl;
int l,r,p,cnt;
for( int fi = 1;fi <= m;fi++ ){ //开始操作 
cin >> cnt;
if( cnt == 1 ){
cin >> l >> r >> p;
//add(l,r,q)__________________________ 
/ for( int i = l;i <= min(r,a[l].k*w);i++ ){ //处理左边碎块
/  //从最左端点开始,一直到a[l].k*w,就是第k个块的结尾的点编号 
/       a[i].zhi += p;
/        b[a[i].k].sum += p;
/     }
/      if( a[l].k != a[r].k ){ //如果不止在一个块里 
/         for( int i = (a[r].k-1)*w+1;i <= r;i++ ) //处理右边碎块 
\         //从前结尾前一个块的最后+1(即结尾所在块的第一个)开始,一直到 
\          a[i].zhi += p,b[a[i].k].sum += p;//碎块本身加,所在大块加 
      \     }
\    //处理范围所包含的整块
\    //开始于起点所在的碎块的后一个块(即第一个整块),结束于终点的前一个块(最后一个整块) 
\  for( int i = a[l].k+1;i <= a[r].k-1;i++ ) b[i].tag += p;
//        \ ____________________________________
        }
if( cnt == 2 ){
cin >> p;
a[1].zhi += p;
b[1].sum += p;
continue;
}
if( cnt == 3 ){
cin >> p;
a[1].zhi -= p;
b[1].sum -= p;
continue;
}
if( cnt == 4 ){
long long ans = 0;bool ok = 0;
cin >> l >> r;
//query(l,r) ,原理类似于上面的add函数 
for( int i = l;i <= min(r,a[l].k * w);i++ )
ans += a[i].zhi + b[a[i].k].tag;
if( a[l].k != a[r].k ){
for( int i = (a[r].k-1)*w+1;i <= r;i++ )
ans += a[i].zhi + b[a[i].k].tag;
}
for( int i = a[l].k+1;i < a[r].k;i++ )
ans += b[i].sum + b[i].tag * w;
cout << ans << endl;
continue;
}
if( cnt == 5 ){
cout << a[1].zhi+b[1].tag << endl;
continue;
}
}
return 0;
}

网上正解

要注意每次使用真实的$a[i].zhi$时一点要加上$b[a[i].k].tag$,即每次取点值的时候要加上所在块的懒惰数值

算是对分块的基本了解了

推荐这些文章:

板刷洛谷B题库计划

B2001
#include <bits/stdc++.h>
// #include <bits/extc++.h>
using namespace std;
// using namespace __gnu_pbds;
//#pragma GCC optimize(2)

int main() {
//freopen("data.in", "r", stdin);
//freopen("data.out", "w", stdout);
long long a,b;
cin>>a>>b;
cout<<a+b;
fclos...

洛谷·P1130

title: "简单dp"
author: Sun-Wind
date: February 13,2022
#include<iostream>
#include<utility>
using namespace std;
typedef long long ll;
#define fi(i,a,b) for(int i = a; i <= b; ++i)
#define fr(i,a,b) for(int i = a; i >= b; --i)
#define x first
#define y second
#define sz(x) ((int)(...

2022.1.17

放假好久了,写了几个
上程序:
#include <iostream>using namespace std;
int main(){ int a, x = 1,b=0,c=0,z=0; cin >> a; string k; cin >> k; cout << k; for (int i = 2; i < a; i++) { x += 2 * (2*i - 1); if (x > a) ...

上海月赛《打印漏斗》

#include <iostream>using namespace std;int main() { int n; cin >> n; for (int i = 1; i <= n - 1 ; i++) { for (int j = 1; j <= i - 1; j++) { cout << ' '; } for (int j = 1; j <= 2 * (n + 1 - i) - 1; j++) { cout << '*';...

习题3.5 实现从标准输入每次读入一行文本。然后改写程序,每次读入一个单词。

1.每次读入一个单词

#include<iostream>
#include<string>
using namespace std;
int main(){
string word;
int n=1;
while(cin>>word){
cout<<n<<": "<<word<<endl;
n++;
}
cout<<endl;
system("pause");
return 0;
}

2.每次读入一行文本...

[二分法]求解递增序列中与x最接近元素问题

#include <iostream>
using namespace std;

int main(){
int i,mid,m,n,ask;
int a[100000];
cin>>n;
for(i=1;i<=n;i++){
cin>>a[i];
}
cin>>m;
for(i=1;i<=m;i++){
cin>>ask;
if(ask<a[1]){
cout<<a[1]...

C++中常用的系统预定义宏

目前只遇到过两个:

#include <iostream>
#include <stdio.h>
using namespace std;

int main(void)
{
cout << __FILE__ << endl;
cout << __LINE__ << endl;
return 0;
}

 

...

error: invalid operands of types 'int' and '<unresolved overloaded function type>' to binary 'operator<<' cout << a&&b <<endl错误

cout << a&&b <<endl这一行出现了这个错误
查了下是因为运算符优先级的问题,加个()就行了
cout << (a&&b) <<endl

 

...

最短hamilton路径

#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N=20,M=1<<N;int n;int w[N][N];int f[M][N];int main(){ cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>w[i][j]; memset(f,0x3f,sizeof f); f[1][0]=0; for(int i=0;i...

opencv-cvCeil返回不小于参数的最小整数值

#include<opencv2/opencv.hpp>
#include<iostream>
#include <vector>

int main(int argc, char** argv) {

std::cout << "cvCeil(3.7) = " << cvCeil(3.7) << std::endl;
std::cout << "cvCeil(3.2) = " << cvCeil(3.2) << std::endl;
s...

文章标题:洛谷 P2357 守墓人
文章链接:https://www.dianjilingqu.com/50831.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>