线段树-区间单个点更新-区间和-区间最大

首页 > 代码库 > 线段树-区间单个点更新-区间和-区间最大

线段树-区间单个点更新-区间和-区间最大

2024-07-04 00:47:31 240人阅读

线段树：

图中的元素【a，b】表示该节点存储的值是在a到b内的结果（最大值或者和）。其根节点为c的话，其下面两个子树节点的序号为 c*2 和 c*2+1

区间最大值

题目：

Problem Description

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input

本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取‘Q‘或‘U‘) ，和两个正整数A，B。
当C为‘Q‘的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为‘U‘的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。

Output

对于每一次询问操作，在一行里面输出最高成绩。

Sample Input

Sample Output

---改自飘过的小牛

#include<cstdio>
#include<algorithm>
#include<cmath>
#include <iostream>
using namespace std;

#define lson l, m, root << 1
#define rson m + 1, r, root << 1 | 1
const int N = 200010;
int segtree[N << 1 + 10]; //开2倍

void PushUp(int root) //节点保存区间最大值
{
	segtree[root] = max(segtree[root << 1], segtree[root << 1 | 1]);
}

void Build_Tree(int l, int r, int root)
{
	if(l == r)
	{
		scanf("%d", &segtree[root]);
		//cout<<root<<"<-"<<endl;
		return ;
	}
	int m = (l + r) >> 1;
	Build_Tree(lson);
	Build_Tree(rson);
	PushUp(root);
}

void Update(int pos, int data, int l, int r, int root)
{
	if(l == r)
	{
		segtree[root] = data;
		return ;
	}
	int m = (l + r) >> 1;
	if(pos <= m)
		Update(pos, data, lson);
	else
		Update(pos, data, rson);
	PushUp(root);
}

int Query(int L, int R, int l, int r, int root)
{
	int sum = -9999999;
	if(L <= l && r <= R)
		return segtree[root];
	int m = (l + r) >> 1;
	if(L <= m)
		sum = max(sum, Query(L, R, lson));
	if(R > m)
		sum = max(sum, Query(L, R, rson));
	return sum;
}

int main()
{
	int num, que;
	char ope;
	int a, b;
	while(scanf("%d%d", &num, &que) != EOF)
	{
		Build_Tree(1, num, 1);
		//for(int i=0;i<num*2;i++)
        //    cout<<segtree[i]<<" ";
        //cout<<endl;
		for(int i = 0; i < que; ++i)
		{
			scanf("%*c%c %d %d", &ope, &a, &b);
			if(ope == ‘U‘)
				Update(a, b, 1, num, 1);
			else
				printf("%d\n", Query(a, b, 1, num, 1));
		}
	}
	return 0;
}

题目：区间求和

士兵杀敌（二）

时间限制：1000 ms | 内存限制：65535 KB

难度：5

描述

南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的。

小工是南将军手下的军师，南将军经常想知道第m号到第n号士兵的总杀敌数，请你帮助小工来回答南将军吧。

南将军的某次询问之后士兵i可能又杀敌q人，之后南将军再询问的时候，需要考虑到新增的杀敌数。

输入

只有一组测试数据
第一行是两个整数N,M，其中N表示士兵的个数(1<N<1000000)，M表示指令的条数。(1<M<100000)
随后的一行是N个整数，ai表示第i号士兵杀敌数目。(0<=ai<=100)
随后的M行每行是一条指令，这条指令包含了一个字符串和两个整数，首先是一个字符串，如果是字符串QUERY则表示南将军进行了查询操作，后面的两个整数m,n，表示查询的起始与终止士兵编号；如果是字符串ADD则后面跟的两个整数I,A(1<=I<=N,1<=A<=100),表示第I个士兵新增杀敌数为A.

输出

对于每次查询，输出一个整数R表示第m号士兵到第n号士兵的总杀敌数，每组输出占一行

样例输入

5 6
1 2 3 4 5
QUERY 1 3
ADD 1 2
QUERY 1 3
ADD 2 3
QUERY 1 2
QUERY 1 5

样例输出

#include<stdio.h>
int sum[3000000];
void build(int b, int e, int index)
{
    if(b==e)
    {
        scanf("%d", &sum[index]);
        return;
    }
    int mid = (b+e)/2, lchild=index<<1 ,rchild=lchild|1;
    build(b, mid, lchild);
    build(mid+1, e, rchild);
    sum[index] = sum[lchild] + sum[rchild];
}

int query(int qb, int qe, int b, int e, int index)
{
    if(qb<=b && e<=qe)
        return sum[index];
    int mid = (b+e)/2, lchild=index<<1 ,rchild=lchild|1, lr=0, rr=0;
    if(qb<=mid)lr = query(qb, qe, b, mid, lchild);
    if(qe>mid) rr = query(qb, qe, mid+1, e,rchild);
    return lr+rr;
}

void update(int b, int e, int node, int num, int index)
{
    if(b==e && e==node)
    {
        sum[index]+=num;
        return;
    }
    int mid = (b+e)/2, lchild=index<<1 ,rchild=lchild|1;
    if(node<=mid)update(b, mid, node, num, lchild);
    else update(mid+1, e, node, num, rchild);
    sum[index] += num;
}

int main()
{
    int n, k, b, e;
    char str[10];
    scanf("%d %d", &n, &k);
    build(1, n, 1);
    for(int i=0; i<k; i++)
    {
        scanf("%s %d %d", str, &b, &e);
        if(str[0]==‘Q‘)
            printf("%d\n", query(b, e, 1, n, 1));
        else
            update(1, n, b, e, 1);
    }
    return 0;
}

题目：蓝桥杯练习题目-综合了区间最大和区间和

算法训练操作格子

时间限制：1.0s 内存限制：256.0MB

问题描述

有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。

#include <cstdio>
#include <iostream>
using namespace std;
const int MAX = 100110;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
int sum[MAX << 2], segs[MAX << 2], maxv[MAX << 2];//区间和-区间值-区间最大

inline void push_up(int rt){
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    maxv[rt] = max(maxv[rt << 1], maxv[rt << 1 | 1]);
}
void build_up(int l, int r, int rt){
    if(l == r){
        scanf("%d", &segs[rt]);
        sum[rt] = segs[rt];
        maxv[rt] = segs[rt];
        return;
    }
    int m = (l + r) >> 1;
    build_up(lson);
    build_up(rson);
    push_up(rt);
}

void update(int l, int r, int rt, int p, int v){
    if(l == r){
        segs[rt] = v;
        maxv[rt] = v;
        sum[rt] = v;
        return;
    }
    int m = (l + r) >> 1;
    if(p <= m)update(lson, p, v);
    else update(rson, p, v);
    push_up(rt);
}

int query_sum(int L, int R, int l, int r, int rt){
    if(L <= l && r <= R){
        return sum[rt];
    }
    int ret = 0;
    int m = (l + r) >> 1;
    if(L <= m)ret += query_sum(L, R, lson);
    if(R > m)ret += query_sum(L, R, rson);
    return ret;
}

int query_max(int L, int R, int l, int r, int rt){
    if(L <= l && r <= R){
        return maxv[rt];
    }
    int ret = -1;
    int m = (l + r) >> 1;
    if(L <= m)ret = max(ret, query_max(L, R, lson));
    if(R > m)ret = max(ret, query_max(L, R, rson));
    return ret;
}
int main(){
    int n, m;
    cin >> n >> m;
    build_up(1, n, 1);
    while(m--){
        int p, x, y;
        scanf("%d%d%d", &p, &x, &y);
        if(p == 1){
            update(1, n, 1, x, y);
        }else if(p == 2){
            printf("%d\n", query_sum(x, y, 1, n, 1));
        }else{
            printf("%d\n", query_max(x, y, 1, n, 1));
        }
    }
    return 0;
}

题目：

掺杂几何知识

Crane

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 3012		Accepted: 806		Special Judge

Description

ACM has bought a new crane (crane -- je?áb) . The crane consists of n segments of various lengths, connected by flexible joints. The end of the i-th segment is joined to the beginning of the i + 1-th one, for 1 ≤ i < n. The beginning of the first segment is fixed at point with coordinates (0, 0) and its end at point with coordinates (0, w), where w is the length of the first segment. All of the segments lie always in one plane, and the joints allow arbitrary rotation in that plane. After series of unpleasant accidents, it was decided that software that controls the crane must contain a piece of code that constantly checks the position of the end of crane, and stops the crane if a collision should happen.

Your task is to write a part of this software that determines the position of the end of the n-th segment after each command. The state of the crane is determined by the angles between consecutive segments. Initially, all of the angles are straight, i.e., 180^o. The operator issues commands that change the angle in exactly one joint.

Input

The input consists of several instances, separated by single empty lines.

The first line of each instance consists of two integers 1 ≤ n ≤10 000 and c 0 separated by a single space -- the number of segments of the crane and the number of commands. The second line consists of n integers l1,..., ln (1 li 100) separated by single spaces. The length of the i-th segment of the crane is li. The following c lines specify the commands of the operator. Each line describing the command consists of two integers s and a (1 ≤ s < n, 0 ≤ a ≤ 359) separated by a single space -- the order to change the angle between the s-th and the s + 1-th segment to a degrees (the angle is measured counterclockwise from the s-th to the s + 1-th segment).

Output

The output for each instance consists of c lines. The i-th of the lines consists of two rational numbers x and y separated by a single space -- the coordinates of the end of the n-th segment after the i-th command, rounded to two digits after the decimal point.

The outputs for each two consecutive instances must be separated by a single empty line.

Sample Input

Sample Output

5.00 10.00

-10.00 5.00
-5.00 10.00

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define lson i<<1
#define rson i<<1|1
#define lc l,mid,i<<1
#define rc mid+1,r,i<<1|1
const int L = 100000+10;
const double pi = acos(-1.0);

struct node
{
    double x,y;
    int deg;
    int flag;
} a[L<<2];

double set(int x)
{
    return x*pi/180;
}

void work(int i,int deg)//求新坐标公式
{
    double r = set(deg);
    double x = a[i].x;
    double y = a[i].y;
    a[i].x = x*cos(r)-y*sin(r);
    a[i].y = x*sin(r)+y*cos(r);
    a[i].deg = (a[i].deg+deg)%360;
}

void pushup(int i)
{
    a[i].x = a[lson].x+a[rson].x;
    a[i].y = a[lson].y+a[rson].y;
}

void pushdown(int i)
{
    if(a[i].flag)
    {
        work(lson,a[i].flag);
        work(rson,a[i].flag);
        a[lson].flag+=a[i].flag;
        a[rson].flag+=a[i].flag;
        a[i].flag = 0;
    }
}

void init(int l,int r,int i)
{
    a[i].x = a[i].y = 0;
    a[i].flag = a[i].deg = 0;
    if(l == r)
    {
        scanf("%lf",&a[i].y);
        return;
    }
    int mid = (l+r)>>1;
    init(lc);
    init(rc);
    pushup(i);
}

void insert(int l,int r,int i,int L,int R,int z)
{
    if(L<=l && r<=R)
    {
        work(i,z);
        a[i].flag+=z;
        return ;
    }
    pushdown(i);
    int mid = (l+r)>>1;
    if(L<=mid)
        insert(lc,L,R,z);
    if(R>mid)
        insert(rc,L,R,z);
    pushup(i);
}

int query(int l,int r,int i,int x)
{
    if(l == r)
        return a[i].deg;
    pushdown(i);
    int mid = (l+r)>>1;
    if(x<=mid)
        return query(lc,x);
    else
        return query(rc,x);
}
int main()
{
    int n,m,x,y,flag = 1,i,j;
    while(~scanf("%d%d",&n,&m))
    {
        init(0,n-1,1);
        if(!flag)
            printf("\n");
        flag = 0;
        while(m--)
        {
            scanf("%d%d",&x,&y);
            int deg;
            deg  = query(0,n-1,1,x-1)+180+y-query(0,n-1,1,x);
//由于题目是逆时针转的，该计算是顺时针，要加上180度,将后面的棒看成依然在Y轴，所以要减去后一个的角度
            insert(0,n-1,1,x,n-1,deg);
            printf("%.2f %.2f\n",a[1].x,a[1].y);
        }
    }

    return 0;
}

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 线段树-区间单个点更新-区间和-区间最大

线段树-区间单个点更新-区间和-区间最大

士兵杀敌（二）

看完仍有疑问？有类似问题直接问程序猿