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

#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;  
}  

#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;
}

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));
	}
	
	
	
}

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)