首页 > 代码库 > 洛谷 U361 序列操作（NOIP模拟赛T2）
洛谷 U361 序列操作（NOIP模拟赛T2）
题目链接：https://www.luogu.org/problem/show?pid=U361
题目背景
夏令营
题目描述
小B有一个整数序列a[1..N]，初始时序列中所有元素均为0。他会在序列上进行下面两种操作，操作共M个：
A l r x：将a[l..r]均加上x。
- Q l r：询问a[l..r]中的最大值。
输入输出格式
输入格式：
第一行，两个整数N, M。
接下来的M行，每行一个操作。
输出格式：
设询问操作有T个，则输出T行，每行一个整数，表示询问操作对应的答案。
输入输出样例
输入样例#1：
5 5A 1 4 1A 2 5 2Q 1 4A 3 4 -2Q 3 5
输出样例#1：
32
很显然地就是一个线段树，甚至几乎是裸的......
但是还是有许多细节需要注意，每次数据结构都是一写就错......
↑你说为什么我放弃了上百毫秒的时间写结构体，因为这样不容易错qwq
（老大：也没看出来你不容易错，还不是改了半天- -）
AC代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 5 using namespace std; 6 const int MAXN = 100000 + 5; 7 struct seg//建树 8 { 9 int l,r;10 int max = 0;11 int lazy;12 } tree[MAXN << 2];13 14 int max(int a,int b)15 {16 return a>b?a:b; 17 }18 19 void build(int o,int l,int r)20 {21 tree[o].l = l;22 tree[o].r = r;23 if(l == r)24 return;25 int mid = (l + r) >> 1;26 build(o << 1,l,mid);27 build(o << 1 | 1,mid + 1,r);28 }29 30 void putdown(int o)31 {32 tree[o << 1].lazy += tree[o].lazy;33 tree[o << 1 | 1].lazy += tree[o].lazy;34 tree[o << 1].max += tree[o].lazy;35 tree[o << 1 | 1].max += tree[o].lazy;36 tree[o].lazy = 0;37 }38 39 void modify2(int l, int r, int k,int o)40 {41 if(l <= tree[o].l && r >= tree[o].r)42 {43 tree[o].max += k;44 tree[o].lazy += k;45 return; 46 }47 int mid = (tree[o].l + tree[o].r) >> 1;48 if(tree[o].lazy) putdown(o);49 if(mid >= l) modify2(l, r, k, o << 1);50 if(mid < r) modify2(l, r, k, o << 1 | 1);51 tree[o].max = max(tree[o << 1].max , tree[o << 1 | 1].max);52 }53 54 int ask(int l,int r,int o)//询问操作 55 {56 if(tree[o].l >= l && tree[o].r <= r)57 {58 return tree[o].max;59 }60 if(tree[o].lazy) putdown(o);61 int ans = -2147483647;//由于每次操作增加的x可能是负值，ans要尽可能小 62 int mid = (tree[o].l + tree[o].r) >>1;63 if(mid >= l) ans = max(ans,ask(l,r,o << 1));64 if(mid < r) ans = max(ans,ask(l,r,o <<1|1)); 65 return ans;66 }67 68 int main()69 {70 int a,b,m,n,x;71 scanf("%d%d",&n,&m);72 build(1,1,n);73 char op;74 for(int i = 1;i <= m;i ++)75 {76 scanf("%c",&op);77 while(op < ‘A‘)78 scanf("%c",&op);79 scanf("%d%d",&a,&b);80 if(op == ‘A‘)81 {82 scanf("%d",&x);83 modify2(a,b,x,1);84 }85 if(op == ‘Q‘)86 {87 int t = ask(a,b,1);88 printf("%d\n",t);89 }90 }91 return 0; 92 }
线段树的易错点还是很多的，比如忘写返回值、大于小于号写反、开闭区间写错、函数参数位置颠倒……（没错，以上问题博主都出现过QAQ）写的时候一定要仔细...
洛谷 U361 序列操作（NOIP模拟赛T2）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。