第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-8 算法训练 操作格子 线段树

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-8 算法训练 操作格子 线段树

目录

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-8 算法训练 操作格子 线段树

前言

算法训练 操作格子

C语言

C++语言

Java语言

Python语言

第六届——第十三届省赛题解

第六届——第十二届省赛题解

前言

        最近的一些文章都可能会很碎，写到哪里是哪里，过一阵子会具体的整理一遍，这里其它的类型题先往后排一排，因为蓝桥最后考的也就是对题目逻辑的理解能力，也就是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("%dn",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("%dn",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个月回忆一下你真正的认真刷过题吗，如果你真的用尽所有的精力去努力了，那么我相信你最终的成绩一定会让你满意的，加油。

第六届——第十三届省赛题解

所有的题目都做了讲解，最难的有配套的视频，视频提供者是【2020级的弓家宜】先生。

第六届——第十二届省赛题解

所有题目均有题解，部分第10题非最优解，至少跑20%数据。

最后

以上就是机灵手机为你收集整理的第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-8 算法训练 操作格子 线段树的全部内容，希望文章能够帮你解决第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-8 算法训练 操作格子 线段树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。