网站建设方案论文1500,企业门户网站运营推广,wordpress链接数据库出错,个人网站可以备案吗1081 线段树练习 2 时间限制: 1 s空间限制: 128000 KB题目等级 : 大师 Master题目描述 Description给你N个数#xff0c;有两种操作 1#xff1a;给区间[a,b]的所有数都增加X 2#xff1a;询问第i个数是什么#xff1f; 输入描述 Input Description第一行一个正整数n#… 1081 线段树练习 2 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 大师 Master 题目描述 Description 给你N个数有两种操作 1给区间[a,b]的所有数都增加X 2询问第i个数是什么 输入描述 Input Description 第一行一个正整数n接下来n行n个整数再接下来一个正整数Q表示操作的个数. 接下来Q行每行若干个整数。如果第一个数是1后接3个正整数a,b,X表示在区间[a,b]内每个数增加X,如果是2后面跟1个整数i, 表示询问第i个位置的数是多少。 输出描述 Output Description 对于每个询问输出一行一个答案 样例输入 Sample Input 3 1 2 3 2 1 2 3 2 2 3 样例输出 Sample Output 5 数据范围及提示 Data Size Hint 数据范围 1n100000 1q100000 分析 Analysis qwq阔别一年终于能用分块写啦 这段时间在网上翻了一些博客也翻了蓝书和ACM模版小红书发现分块写法风格实在是多样 像ACM红书就清华大学出版社俞勇主编那本ACMXXX《算法与实现》里面写成了纯链表 蓝书写的就比较接近我现在的习惯但是也是难以模仿 现在的分块类型总结如下 A. 将数据完全存在各种块中就是红书那种块状链表一个节点保存一块的信息 B. 将数据存在线性数组中分块相关的附属信息用另外一个结构存线性数组中每一个元素有对应的块编号 个人觉得B. 比较好写其实是因为B.写对了 个人觉得写的比较好的分块范例是在 1081线段树练习2 的题解里找到的推荐 显然分块的风格还是挺多的 之前也听学长说分块很难写因为细节部分容易出错还难调我是挺难调的 不过还是推荐学一学 代码 Code 1 #includecstdio2 #includecmath3 #includeiostream4 #define maxn 10000005 using namespace std;6 7 int size,arr[maxn],block[maxn],add[maxn],n,q,swi,a,b,c;8 9 void modify(int a,int b,int c){
10 a--,b--;
11 for(int i a;i min(block[a]*size-1,b);i)
12 arr[i] c;
13 if(block[a] ! block[b]){
14 for(int i (block[b]-1)*size;i b;i)
15 arr[i] c;
16 }
17 for(int i block[a]1;i block[b];i)
18 add[i] c;
19 }
20
21 int main(){
22 scanf(%d,n);
23 size (int)sqrt(n);
24 for(int i 0;i n;i) scanf(%d,arr[i]);
25 for(int i 0;i n;i) block[i] i/size1;
26 // for(int i 0;i n;i) printf(#%d: block-%d\n,i1,block[i]);
27 scanf(%d,q);
28 for(int i 1;i q;i){
29 scanf(%d,swi);
30 if(swi%2){
31 scanf(%d%d%d,a,b,c);
32 // for(int i 1;i n;i) printf(#%d: add-%d\n,i,add[block[i]]);
33 modify(a,b,c);
34 }else{
35 scanf(%d,a);
36 printf(%d\n,arr[a-1]add[block[a-1]]);
37 }
38 }
39
40 // for(int i 0;i n;i) printf(#%d: block[%d]\n,i,block[i]);
41
42 return 0;
43 } 分块 转载于:https://www.cnblogs.com/Chorolop/p/7512248.html
