第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-8 算法训练 操作格子 线段树
前言
最近的一些文章都可能会很碎，写到哪里是哪里，过一阵子会具体的整理一遍，这里其它的类型题先往后排一排，因为蓝桥最后考的也就是对题目逻辑的理解能力，也就是dp分析能力了，所以就主要目标定在这里，最近的题目会很散，很多，基本上都是网罗全网的一些dp练习题进行二次训练，准备比赛的学生底子薄的先不建议看啊，当然，脑子快的例外，可以直接跳过之前的一切直接来看即可，只需要你在高中的时候数学成绩还可以那就没啥问题，其实，dp就是规律总结，我们只需要推导出对应题目的数学规律就可以直接操作，可能是一维数组，也可能是二维数组，总体来看二维数组的较多，但是如果能降为的话建议降为，因为如果降为起来你看看时间复杂度就知道咋回事了，那么在这里祝大家能无序的各种看明白，争取能帮助到大家。
算法训练 操作格子
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
有n个格子，从左到右放成一排，编号为1-n。
共有m次操作，有3种操作类型：
1.修改一个格子的权值，
2.求连续一段格子权值和，
3.求连续一段格子的最大值。
对于每个2、3操作输出你所求出的结果。
输入格式
第一行2个整数n，m。
接下来一行n个整数表示n个格子的初始权值。
接下来m行，每行3个整数p,x,y，p表示操作类型，p=1时表示修改格子x的权值为y，p=2时表示求区间[x,y]内格子权值和，p=3时表示求区间[x,y]内格子最大的权值。
输出格式
有若干行，行数等于p=2或3的操作总数。
每行1个整数，对应了每个p=2或3操作的结果。
样例输入
4 3
1 2 3 4
2 1 3
1 4 3
3 1 4
样例输出
6
3
数据规模与约定
对于20%的数据n <= 100，m <= 200。
对于50%的数据n <= 5000，m <= 5000。
对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000
题解：
C语言
#include <stdio.h> #define N 100000 #define A 1000 #define B 100 int sum(int* a, int m, int n) { int i,s=0; for (i=m;i<=n;i++) s+=a[i]; return s; } int max(int* a, int m, int n) { int i,s=a[m]; for (i=m+1;i<=n;i++) if (s<a[i]) s=a[i]; return s; } int main() { int i,j,k,m,n; int a[100000],b[100000][3],c[A][2]={0}; scanf("%d%d",&n,&m); for (i=0; i<n;i++) scanf("%d",&a[i]); for (i=0;i<m;i++) for (j=0;j<3;j++) scanf("%d", &b[i][j]); for (i=0;i<(n+B-1)/B;i++) { c[i][0]=c[i][1]=a[i * B]; for (j=i*B+1;j<i*B+B && j<n;j++) { c[i][0]+=a[j]; if (c[i][1]<a[j]) c[i][1]=a[j]; } } for (i=0;i<m;i++) { if (b[i][0]==1) { c[(b[i][1]-1)/B][0]+=b[i][2]-a[b[i][1]-1]; k=(b[i][1]-1)/B; if (c[k][1]<=b[i][2]) { c[k][1]=b[i][2]; } else if (a[b[i][1]-1]==c[k][1]) { a[b[i][1]-1]=b[i][2]; c[k][1]=max(a,k*B,k*B+B>n ? n-1 : k*B+B-1); } a[b[i][1]-1]=b[i][2]; } else if(b[i][0]==2) { int s=0; b[i][1]--, b[i][2]--; int o=b[i][2]/B-b[i][1]/B; if (o<2) { s=sum(a,b[i][1],b[i][2]); } else { s=sum(a,b[i][1],(b[i][1]+B)/B*B-1); s+=sum(a, b[i][2]/B*B, b[i][2]); for (j = b[i][1]/B+1;j<b[i][2]/B;j++) s += c[j][0]; } printf("%d\n",s); } else if (b[i][0]==3) { int s = 0,t; b[i][1]--, b[i][2]--; int o=b[i][2]/B-b[i][1]/B; if (o<2) { s=max(a, b[i][1],b[i][2]); } else { s=max(a,b[i][1],(b[i][1]+B)/B*B-1); t=max(a,b[i][2]/B*B,b[i][2]); if (s<t)s=t; for (j=b[i][1]/B+1;j<b[i][2]/B;j++) if (s<c[j][1]) s=c[j][1]; } printf("%d\n",s); } } return 0; }
C++语言
#include <cstdio> #include <algorithm> struct Tree { int sum, max; }; Tree tree[1 << 18]; void scan(int &n) { char c; c = getchar(); if (c == EOF) { return ; } while (c < '0' || c > '9') { c = getchar(); } n = c - '0'; while (c = getchar(), c >= '0' && c <= '9') { n *= 10; n += c - '0'; } } void put(int n) { int cnt = 0; char s[16]; if (n == 0) { putchar('0'); return ; } for( ; n; n /= 10) { s[cnt++] = n % 10 + '0'; } while (cnt--) { putchar(s[cnt]); } } void update(int n, int v) { for (n += (1 << 17),tree[n].sum = tree[n].max = v, n >>= 1; n; n >>= 1) { tree[n].max = std::max(tree[n + n].max, tree[n + n + 1].max); tree[n].sum = tree[n + n].sum + tree[n + n + 1].sum; } } int query(int s, int t, int func) { int sum = 0, max = 0; for (s += (1 << 17) - 1, t += (1 << 17) + 1; s ^ t ^ 1; s >>= 1, t >>= 1) { if (~s & 1) { sum += tree[s ^ 1].sum; max = std::max(max, tree[s ^ 1].max); } if (t & 1) { sum += tree[t ^ 1].sum; max = std::max(max, tree[t ^ 1].max); } } return func ? max : sum; } int main() { int n, m, i, a, b, c; scan(n);scan(m); for (i = 1; i <= n; ++i) { scan(a); update(i, a); } while (m--) { scan(c);scan(a);scan(b); c == 1 && (update(a, b), 0); c == 2 && (put(query(a, b, 0)), putchar('\n'), 0); c == 3 && (put(query(a, b, 1)), putchar('\n'), 0); } return 0; }
Java语言
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class Main { static int[] array; static long []mark; static long []Tree; static int[] Max; public static void main(String[] args) throws IOException { // TODO Auto-generated method stub StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter pt=new PrintWriter(System.out); st.nextToken(); int n=(int)st.nval; array=new int[n+1];//图方便从1开始 mark=new long[4*n+4]; Tree=new long[4*n+4]; Max=new int[4*n+4]; st.nextToken(); int m=(int)st.nval; for(int i=1;i<=n;i++) { st.nextToken(); array[i]=(int)st.nval; } build(1,n,1); for(int i=0;i<m;i++) { st.nextToken(); if((int)st.nval==1) { st.nextToken(); int a=(int)st.nval; st.nextToken(); int v=(int)st.nval; update(a,a,v,1,1,n); } else if((int)st.nval==2){ st.nextToken(); int a=(int)st.nval; st.nextToken(); int b=(int)st.nval; pt.println(query(a, b, 1, 1, n)); } else { st.nextToken(); int a=(int)st.nval; st.nextToken(); int b=(int)st.nval; pt.println(getMax(a, b, 1, 1, n)); } } pt.close(); } public static void build(int l,int r,int p) { if(l==r) { Tree[p]=array[l]; Max[p]=array[l]; } else { int mid=l+(r-l)/2; build(l,mid,p*2); build(mid+1,r,p*2+1); Tree[p]=Tree[p*2]+Tree[p*2+1]; Max[p]=Math.max(Max[p*2], Max[p*2+1]); } } public static void update(int l,int r,int d,int p,int nowL,int nowR) { if(r<nowL||l>nowR) return; if(l<=nowL&&r>=nowR) { Tree[p]=d;//懒标记的规则就是在更新当前的mark之前 已经修改了当前的tree的值 Max[p]=d; } else { int mid=nowL+(nowR-nowL)/2; update(l,r,d,p*2,nowL,mid); update(l,r,d,p*2+1,mid+1,nowR); Tree[p]=Tree[p*2]+Tree[p*2+1]; Max[p]=Math.max(Max[p*2], Max[p*2+1]); } } public static long query(int l,int r,int p,int cl,int cr) { if (cl> r || cr < l) return 0; else if (cl >= l && cr <= r) return Tree[p]; else { int mid =cl+(cr-cl)/2; return query(l, r, p * 2, cl, mid) + query(l, r, p * 2 + 1, mid + 1, cr ); // 上一行拆成三行写就和区间修改格式一致了 } } public static int getMax(int l,int r,int p,int cl,int cr) { if(cl>r||l>cr) { return 0; } if(cl>=l&&cr<=r) return Max[p]; int mid=cl+(cr-cl)/2; return Math.max(getMax(l,r,p*2,cl,mid),getMax(l,r,p*2+1,mid+1,cr)); } }
Python语言
n,m = map(int,input().split()) value = list(map(int,input().split())) num = [] a = [ dict() for j in range(4*n)] # print(a) def update(k): node = a[k] node['sum'] = a[k * 2]['sum'] + a[k * 2 + 1]['sum'] node['max'] = max(a[k * 2]['max'], a[k * 2 + 1]['max']) def built(k,l,r): node = a[k] node['l'] = l node['r'] = r if l == r: node['sum'] = value[l] node['max'] = value[l] else: mod = int((r+l)/2) built(2*k,l,mod) built(2*k+1,mod+1,r) update(k) def chang(k,x,y): node = a[k] if node['l']==node['r']: node['sum'] = y node['max'] = y else: mod = int((node['r']+node['l'])/2) if x>mod: chang(k*2+1,x,y) else: chang(k*2,x,y) update(k) def Sum(k,l,r): node = a[k] if node['l']==l and node['r']==r: return node['sum'] else: mod = int((node['r']+node['l'])/2) if r<=mod: return Sum(k*2,l,r) elif l>mod: return Sum(k*2+1,l,r) else: return Sum(k*2,l,mod)+Sum(k*2+1,mod+1,r) def Max(k,l,r): node = a[k] if node['l'] == l and node['r'] == r: return node['max'] else: mod = int((node['r'] + node['l']) / 2) if r <= mod: return Max(k * 2, l, r) elif l > mod: return Max(k * 2+1, l, r) else: return max(Max(k * 2, l, mod),Max(k * 2 + 1, mod + 1, r)) built(1,0,n-1) for i in range(m): p,x,y = map(int,input().split()) if p == 1: chang(1,x-1,y) if p == 2: s=Sum(1,x-1,y-1) num.append(s) if p == 3: m = Max(1,x-1,y-1) num.append(m) for i in num: print(i)
没有什么不付出就能拿到的结果，我们都是在负重前行，最终结果与自身先天的脑力有一定的关系，但是还是有很大一部分看自己后天的努力，其实从报名到比赛也就5个月左右，真正刷题的事件也就2个月，2个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。
