1,题意:
I a b c给区间[a b]加c个糖果.
C a b选出[a b]最多的糖果,并取出.
2,解决:
动态的区间数据维护,可用线段树解决.
3,实现代码:
#include <iostream>
using namespace std;
#define MAX(a,b) ( a>b? a:b )
const int MAXN=100005;
struct Node
{
int a,b;//左右端点
int m;//区间最多的糖果数
int mIndex;//区间最多糖果数的下标
int r;//区间的糖果数增量
};
Node tree[MAXN*4];
void build(int x,int y,int k)//从位置tree[k]建立线段树
{
tree[k].a=x;
tree[k].b=y;
tree[k].m=0; //初始化为0
tree[k].mIndex=x;
tree[k].r=0;
if(x<y)
{
int mid=(x+y)/2;
build(x,mid,2*k+1);
build(mid+1,y,2*k+2);
}
}
//在节点tree[k]上执行操作I x y p
void insert(int x,int y,int p,int k)
{
if( x<=tree[k].a&&y>=tree[k].b )//x,y完全覆盖了tree[k]的区间
{
tree[k].m+=p; //糖果最多数增加
tree[k].r+=p; //增量
return;
}
int r=tree[k].r;
tree[2*k+1].r+=r;tree[2*k+1].m+=r;
tree[2*k+2].r+=r;tree[2*k+2].m+=r;
tree[k].r=0;//将增量分发给了子区间
int mid=(tree[k].a+tree[k].b)/2;
if(x<=mid)//[x y]与左孩子有交集
insert(x,y,p,2*k+1);
if(y>=mid+1)//与有孩子有交集
insert(x,y,p,2*k+2);
tree[k].m=MAX(tree[2*k+1].m,tree[2*k+2].m);
tree[k].mIndex=tree[2*k+1].m>=tree[2*k+2].m ? tree[2*k+1].mIndex:tree[2*k+2].mIndex;
}
int getmax(int x,int y,int k,int& mindex) //从tree[k]查询[x y]的最大值,将下标保存到mindex
{
if( x<=tree[k].a&&y>=tree[k].b )//x,y完全覆盖了tree[k]的区间
{
mindex=tree[k].mIndex;
return tree[k].m;
}
int r=tree[k].r;
tree[2*k+1].r+=r;tree[2*k+1].m+=r;
tree[2*k+2].r+=r;tree[2*k+2].m+=r;
tree[k].r=0;//将增量分发给了子区间
int mid=(tree[k].a+tree[k].b)/2;
int ret,mindex1,mindex2,r1,r2;
if(x<=mid)//[x y]与左孩子有交集
{
if(y>=mid+1)//与右孩子也有交集
{
r1=getmax(x,y,2*k+1,mindex1);
r2=getmax(x,y,2*k+2,mindex2);
ret=MAX(r1,r2);
mindex=r1>=r2? mindex1:mindex2;
}
else//只与左孩子有交集
{
ret=getmax(x,y,2*k+1,mindex1);
mindex=mindex1;
}
}
else//只与有孩子有交集
{
ret=getmax(x,y,2*k+2,mindex2);
mindex=mindex2;
}
return ret;
}
int main()
{
freopen("3.3.in","r",stdin);
freopen("main.txt","w",stdout);
int n,m;//糖果数,操作数
int ans,mindex;
string op;
int x,y,p;
while(cin>>n>>m,n)
{
build(1,n,0);//初始化线段树
while(m--)
{
cin>>op;
if(op=="I")
{
cin>>x>>y>>p;
insert(x,y,p,0);
}
else
{
cin>>x>>y;
ans=getmax(x,y,0,mindex);
cout<<ans<<endl;
insert(mindex,mindex,-ans,0);//取出糖果数
}
}
}
return 0;
}
分享到:
相关推荐
国际大学生程序设计竞赛例题解.三:图论、动态规划算法、综合题专集
本系列丛书包括《ACM国际大学生程序设计竞赛:知识与入门》、《ACM国际大学生程序设计竞赛:算法与实现》、《ACM国际大学生程序设计竞赛:题目与解读》、《ACM国际大学生程序设计竞赛:比赛与思考》等4册,其中《ACM...
国际大学生程序设计竞赛例题解(六) 广东省大学生程序设计竞赛例题解析
第二本:国际大学生程序设计竞赛例题解 2 广东省大学生程序设计竞赛试题 2003-2005年 第三本:国际大学生程序设计竞赛例题解 3 图论·动态规划算法·综合题专集 第四本:国际大学生程序设计竞赛例题解 4 广东省...
此资源压缩包分为两卷,此卷为part1。 《ACM国际大学生程序设计竞赛:题目与解读》讲述了ACM国际大学生程序设计竞赛(ACM—...《ACM国际大学生程序设计竞赛:题目与解读》为各类算法配备经典例题及题库,并提供解题思路。
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
国际大学生程序设计竞赛例题解二,分享给大家!
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
国际大学生程序设计竞赛例题解 广东省大学生程序设计竞赛试题,搞ACM,信息学竞赛的同学都用得着!
国际大学生程序设计竞赛例题解.一:数论、计算几何、搜索算法专集.
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
为了帮助高等院校的大学生们备战国际大学生程序设计竞赛,帮助他们提高程序设计水平和培养更强的分析问题和解决问题的能力,我们编写了这本辅导教材。本书所用的语言是Pascal(Delphi)。全书共分六章,第1章先介绍...
中国大学生数学建模竞赛题解_matlab
此资源压缩包分为两卷,此卷为part2。 《ACM国际大学生程序设计竞赛:题目与解读》讲述了ACM国际大学生程序设计竞赛(ACM—...《ACM国际大学生程序设计竞赛:题目与解读》为各类算法配备经典例题及题库,并提供解题思路。
国际大学生程序设计竞赛(ACM)例题解析合集八本1-8,设计到各类算法的方方面面,包括动态规划、图论、搜索算法等。对于做算法开发的程序员很有参考意义。 附件为百度网盘永久链接地址。
国际大学生程序设计竞赛例题解 6 广东省大学生程序设计竞赛试题解 2008-2009年 郭嵩山 电子工业出版社
国际大学生程序设计竞赛例题解赛试题(一)