题目链接:http://acm.fzu.edu.cn/problem.php?pid=1608
题目大意:给出若干区间的效率,求总区间的效率最大和。
题目思路:本来想用一般的延迟操作来做,结果超时,看到网上有一种方法,直接插入区间,最后询问时更新到点,就可以了。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define M 110000
inline int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
int n,m;
struct node
{
int l,r,col;
int mid()
{
return (l+r)>>1;
}
}T[4*M];
void build(int l,int r,int rt)
{
T[rt].l=l;T[rt].r=r;T[rt].col=0;
if(l==r) return;
int mid=T[rt].mid();
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
}
void modify(int l,int r,int rt,int data)
{
if(T[rt].l==l&&T[rt].r==r)
{
T[rt].col=max(data,T[rt].col);
return;
}
int mid=T[rt].mid();
if(r<=mid) modify(l,r,rt<<1,data);
else if(l>mid) modify(l,r,rt<<1|1,data);
else
{
modify(l,mid,rt<<1,data);
modify(mid+1,r,rt<<1|1,data);
}
}
int query(int rt)
{
if(T[rt].l==T[rt].r)
{
return T[rt].col;
}
T[rt<<1].col=max(T[rt].col,T[rt<<1].col);
T[rt<<1|1].col=max(T[rt].col,T[rt<<1|1].col);
return query(rt<<1)+query(rt<<1|1);
}
int main()
{
int l,r,p;
while(scanf("%d%d",&n,&m)!=EOF)
{
build(0,n,1);
while(m--)
{
scanf("%d%d%d",&l,&r,&p);
modify(l,r-1,1,p);
}
printf("%d\n",query(1));
}
}
分享到:
相关推荐
求最大乘积 的源代码 次题是fzu 4月月赛题 是一道数学题啊
fzu online judge 的几道题,我的解题过程与思路,虽然都是很easy的题目,不过,重在参与嘛,哈哈
2021FZU计算机视觉作业(九)
2021FZU计算机视觉作业(七)
2021FZU计算机视觉作业(八)
2021FZU计算机视觉期末复习
不要下载此版的,请下载最新的http://download.csdn.net/source/1664620 离线版的福大acm在线评测OJ系统题目 更新到2009年8月 (注:chm电子书格式化)
fzu大数据基础实验4
C#miniword完整版,FZU作业,MINIWORD
FZU软件工程web课程复习资料-整理
FZU2021计算机视觉慕课答案(一)
FZU软件工程操作系统课程复习资料-整理
这是关于我们飞跃手册项目的相关文档,包括成员分组信息表格,各组成员任务概要文档,项目日记等文档。 (This is a collection of documents relating to our Leapfrog Handbook project, including member ...
FZU2021计算机视觉答案(三)
FZU2021计算机视觉答案(四)
2021FZU计算机视觉答案(五)
2021FZU计算机视觉答案(二 )
2021FZU计算机视觉答案(六)
2011 ACM 多校联合 2011 MU11 13 FZU
ACM数学_FZU...............绝密..........