Android 静态IP Linux软件安装 双重检验锁 swing uiview orm transactions null arm vue安装 bootstrap后台管理系统 python数据挖掘实战pdf db2从入门到精通 java数据分析 windows杀进程命令 oracle给表增加字段 小程序下拉刷新样式 安装mysql python数据 pythonassert函数 python运算符优先级 java基础 java中的多态 jdk环境配置 java路径 怎么安装linux系统 ** 离散数学pdf java疯狂讲义 相机权限 狮子狗皮肤 ps色阶快捷键 坐标标注插件 spss20安装教程 js发送http请求 pycharm中文版 mysql导出数据 脚本列表 证书小精灵
当前位置: 首页 > 学习教程  > 编程语言

hdu 1754 I Hate It (树状数组求区间最大和)(线段树单点修改)

2020/8/11 21:01:46 文章标签:

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

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

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
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9

解析:
题意很简单,写个单点修改的线段树就好了,然后为了熟悉树状数组的操作,又多学习了下树状数组求区间最大值的写法。

idx [ i ] 表示 区间中最大的值,a [ ] 是存放元素数组
在这里插入图片描述

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second

typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const ll mod=1000000007;
const int maxn=2e5+10;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

int t,n,m,x,y,cnt=0;
int a[maxn],idx[maxn];
int lowbit(int x){
   return x&-x;
}
void modify(int p,int v){
   a[p] = v;
   for(int i = p; i <= n; i+=lowbit(i)){
      if(idx[i] < v) idx[i] = v;
      else break;
      for(int j = 1; j < lowbit(i); j<<=1){
         idx[i] = max(idx[i],idx[i-j]);
      }
   }
}
 
int query(int l,int r){
   int ans = a[r];
 
   while(true){
      ans = max(a[r],ans);
      if(l == r)break;
      for(r--; r-lowbit(r) >= l; r -= lowbit(r)){
         ans = max(ans,idx[r]);
      }
   }
   return ans;
}

int main(){
   while(~scanf("%d %d",&n,&m) && n){
      memset(idx,0,sizeof idx);
      for(int i=1;i<=n;i++){
         scanf("%d",&a[i]);
         modify(i,a[i]);
      }
      while(m--){
         char str[2];
         scanf("%s %d %d",str,&x,&y);
         if(str[0] == 'Q') printf("%d\n",query(x,y));
         else modify(x,y);
      }
   }
   return 0;
}

同时,放上单点修改的线段树的写法:

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const ll mod=1000000007;
const int maxn=2e6+10;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int t,n,m,a,b;
int sum[maxn<<2];
void push_up(int rt){
	sum[rt] = max(sum[rt<<1],sum[rt<<1 | 1]);
}
void build(int l,int r,int rt){
	if(l == r) {
		scanf("%d",&sum[rt]);
		return;
	}
	int mid =(l+r)>>1;
	build(lson);
	build(rson);
	push_up(rt);
}
void update(int p,int add,int l,int r,int rt){
	if(l==r){
		sum[rt]=add;
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid) update(p,add,lson);
	else update(p,add,rson);
	push_up(rt);
}
int query(int a,int b,int l,int r,int rt){
	if(a<=l && b>=r) return sum[rt];
	int mid = (l+r)>>1;
	int ans=0;
	if(a<=mid) ans=max(ans,query(a,b,lson));
	if(b>mid) ans=max(ans,query(a,b,rson));
	return ans;
}

int main(){
	while(~scanf("%d %d",&n,&m) && n){
		build(1,n,1);
		while(m--){
			char str[2];
			scanf("%s %d %d",str,&a,&b);
			if(str[0] == 'Q') printf("%d\n",query(a,b,1,n,1));
			else update(a,b,1,n,1);
		}
	}

	
	return 0;
}

本文链接: http://www.dtmao.cc/news_show_100452.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?