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...
国际大学生程序设计竞赛例题解(六) 广东省大学生程序设计竞赛例题解析
### 国际大学生程序设计竞赛教程知识点概览 #### 一、国际大学生程序设计竞赛(ACM/ICPC)概述 - **主办单位**: ACM/ICPC由国际计算机学会(Association for Computer Machinery, 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(国际大学生程序设计竞赛)和信息学竞赛精心编纂的一份参考资料,尤其适用于广东省大学生程序设计竞赛的参赛者。该资源包含了一系列精选的竞赛题目,旨在帮助参赛者提升...
这个压缩包“国际大学生程序设计竞赛例题解二”显然是一个关于该竞赛的解题集,包含了解决过去竞赛题目的一些策略和方法。 在ICPC中,参赛队伍需要解决一系列复杂的算法问题,在限时内提交正确答案。这些题目通常...
- **国际大学生程序设计竞赛例题解系列**(郭嵩山):提供多种题型的解决方案,帮助学生拓宽解题思路。 - 在线编程平台如ZJU Online Judge、POJ、Codeforces等,提供了丰富的题库供学生练习。 #### 五、训练规范与...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
算法参考资料国际大学生程序设计竞赛例题解数论、计算几何、搜索算法专集
### 国际大学生程序设计竞赛辅导教程知识点概览 #### 一、国际大学生程序设计竞赛简介 - **背景与意义**: - **主办方**:由国际计算机领域历史悠久且颇具权威性的组织——ACM学会(Association for Computer ...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
本系列丛书包括《acm国际大学生程序设计竞赛:知识与入门》、《acm国际大学生程序设计竞赛:算法与实现》、《acm国际大学生程序设计竞赛:题目与解读》、《acm国际大学生程序设计竞赛:比赛与思考》等4册,其中《acm...
国际大学生程序设计竞赛(ICPC,International Collegiate Programming Contest)是一项全球性的计算机编程赛事,旨在提升大学生的算法设计、问题解决以及团队合作能力。本压缩包“竞赛例题解(六)光盘”包含了该赛事...
本压缩包“国际大学生程序设计竞赛例题解”包含了图论、动态规划以及综合题目的例题解析,是参赛者或对算法感兴趣的学者宝贵的参考资料。 首先,我们来探讨图论这一领域。图论是数学的一个分支,主要研究点(顶点)...
2005年》一书,主要为那些准备参加国际大学生程序设计竞赛(ICPC)以及广东省大学生程序设计竞赛的读者提供了过去竞赛中的一些例题以及解题方法。书中不仅包括了国际赛题,还特别针对广东省的比赛提供了解题资源,...