关键词:
不得已又挖了一个坑。。想来学习线段树也有一段时间了,也有了些了解,但是在做题的
时候还是磕磕碰碰的,还是不够熟练,还是要多做题(水题除外),多思考。
这是一道典型的线段树区间更新,一定要使用延迟标记,同时又要使用区间合并。
区间合并的做法和poj3667 Hotel这题是一样的。起先我想都使用线段树的查询,发现有困难
然后参考了http://blog.csdn.net/azheng51714/article/details/8089260这里的做法,即保存分配
过的区间的思路,因为所有的区间都是没有重合的,一个区间只能分配一次。但是无论我怎么
改都是TLE。。有哪位大神可以帮我看看。。
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
const int maxn=50010;
int llen[maxn*4],rlen[maxn*4],mlen[maxn*4];
int change[maxn*4];
struct seg{
int l,r;
seg(){}
seg(int _l,int _r):l(_l),r(_r){}
bool operator<(const seg &s)const
{
return l<s.l;
}
};
vector<seg>sgmts;
void pushUp(int root,int l,int r)
{
int len=r-l+1;
llen[root]=llen[root*2];
rlen[root]=rlen[root*2+1];
if(llen[root*2]==len-len/2)llen[root]+=llen[root*2+1];
if(rlen[root*2+1]==len/2)rlen[root]+=rlen[root*2];
mlen[root]=max(rlen[root*2]+llen[root*2+1],max(mlen[root*2],mlen[root*2+1]));
}
void pushDown(int root,int l,int r)
{
if(change[root]!=-1){
change[root*2]=change[root*2+1]=change[root];
int t=change[root],len=r-l+1;
llen[root*2]=rlen[root*2]=mlen[root*2]=t?0:len-len/2;//0表示释放,1表示分配
llen[root*2+1]=rlen[root*2+1]=mlen[root*2+1]=t?0:len/2;
change[root]=-1;
}
}
void build(int root,int l,int r)
{
change[root]=-1;
llen[root]=rlen[root]=mlen[root]=r-l+1;
if(l==r)return;
int mid=(l+r)/2;
build(root*2,l,mid);
build(root*2+1,mid+1,r);
}
void update(int root,int v,int L,int R,int l,int r)
{
if(R<l||L>r)return;
if(L<=l&&r<=R){
int len=r-l+1;
change[root]=v;
llen[root]=rlen[root]=mlen[root]=v?0:len;//0表示释放,1表示分配///
return;
}
pushDown(root,l,r);
int mid=(l+r)/2;
if(mid>=L)update(root*2,v,L,R,l,mid);
if(mid<R)update(root*2+1,v,L,R,mid+1,r);
pushUp(root,l,r);
}
int query2(int root,int w,int l,int r)
{
if(l==r)return l;///
pushDown(root,l,r);
int mid=(l+r)/2;
if(mlen[root*2]>=w)return query2(root*2,w,l,mid);
else if(rlen[root*2]+llen[root*2+1]>=w)return mid-rlen[root*2]+1;
else return query2(root*2+1,w,mid+1,r);
}
int main()
{
//freopen("in.txt","r",stdin);
int N,M;
while(scanf("%d%d
",&N,&M)!=EOF){
char cmd[10];
int n;
build(1,1,N);
sgmts.clear();
while(M--){
scanf("%s",cmd);
if(cmd[0]==‘N‘){
scanf("%d",&n);
if(mlen[1]<n)printf("Reject New
");
else {
int p=query2(1,n,1,N);
update(1,1,p,p+n-1,1,N);
//sgmts.push_back(seg(p,p+n-1));
//sort(sgmts.begin(),sgmts.end());
seg t=seg(p,p+n-1);
auto itr=upper_bound(sgmts.begin(),sgmts.end(),t);
sgmts.insert(itr,t);
printf("New at %d
",p);
}
}
if(cmd[0]==‘F‘){
scanf("%d",&n);
seg t=seg(n,n);
auto p=upper_bound(sgmts.begin(),sgmts.end(),t);
if(p==sgmts.begin()||(--p)->r<n)printf("Reject Free
");
else {
update(1,0,p->l,p->r,1,N);
printf("Free from %d to %d
",p->l,p->r);
sgmts.erase(p);
}
}
if(cmd[0]==‘G‘){
scanf("%d",&n);
if(n>sgmts.size())printf("Reject Get
");
else{
printf("Get at %d
",sgmts[n-1].l);
}
}
if(cmd[0]==‘R‘){
//build(1,1,N);//
update(1,0,1,N,1,N);
sgmts.clear();
printf("Reset Now
");
}
}
printf("
");
}
//while(1);
}
hdu1698线段树区间更新
JustaHookTimeLimit:4000/2000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):36313 AcceptedSubmission(s):17713ProblemDescriptionInt 查看详情
hdu1698justahook线段树区间更新
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1698 题目描述:区间更新,最后求出1~n之和 解题思路:这里涉及到区间更新,这也是我第一次写区间更新,以前都是单点更新,回溯就可以了,如果将区间更... 查看详情
hdu1556colortheball(线段树:区间更新)
...每个气球涂色的次数。 思路:这道题目用树状数组和线段树都可以,拿这道题来入门一下线段树的区间更新。1#include<iostream>2#include<cstring>3#include<algorithm&g 查看详情
hdu1166敌兵布阵(线段树单点更新)
线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。 对于线段树中的每一个非叶子节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],... 查看详情
hdu3308线段树区间合并+单点更新+区间查询
LCISTimeLimit:6000/2000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):6592 AcceptedSubmission(s):2866ProblemDescriptionGivenninte 查看详情
hdu1540tunnelwarfare(线段树,单点更新,区间查询)
ProblemDescriptionDuringtheWarofResistanceAgainstJapan,tunnelwarfarewascarriedoutextensivelyinthevastareasofnorthChinaPlain.Generallyspeaking,villagesconnectedbytunnelslayinaline.Exceptthetwoattheends 查看详情
hdu1754ihateit(线段树单点更新区间查询最值)
HDU1754IHateIthttp://acm.hdu.edu.cn/showproblem.php?pid=1754//////////////////注意线段树的大小要比需要使用线段树的数据的个数大个3到4倍//////////////////////////////////////////IHateItTimeLimit:9000/3000MS(Java/Others) &nbs 查看详情
hdu3308lcis线段树区间更新
...间x-y的最长连续上升子序列的长度L 解题思路:对于线段树不好的我依然好难.....有太多细节需要注意了....但是这是一道很好的题,一段区间的L可能从三个地方来,一种是中间,一种是以左起点为开头的,一 查看详情
hdu1698justahook线段树区间更新
pid=1698">点击打开链接题目链接JustaHookTimeLimit:4000/2000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):18010 AcceptedSubmission(s):9013Pr 查看详情
hdu1166线段树(单点更新,区间求和)
敌兵布阵TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):78691 AcceptedSubmission(s):33255ProblemDescriptionC国的死对头A国 查看详情
hdu4027canyouanswerthesequeries?(线段树/区间不等更新)
传送门Canyouanswerthesequeries?TimeLimit:4000/2000MS(Java/Others) MemoryLimit:65768/65768K(Java/Others)TotalSubmission(s):18290 AcceptedSubmission(s):4308Des 查看详情
hdu1116敌兵布阵线段树区间求和单点更新
线段树的基本知识可以先google一下,不是很难理解线段树功能:update:单点增减query:区间求和#include<bits/stdc++.h>#definelsonl,m,rt<<1#definersonm+1,r,rt<<1|1usingnamespacestd;constintMAXN=50008;intsum[MAXN<<2];voi 查看详情
hdu1698justahook(线段树区间更新入门题)
JustaHookTimeLimit:4000/2000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):36705 AcceptedSubmission(s):17920ProblemDescriptionInt 查看详情
hdu-4027canyouanswerthesequeries?(线段树区间更新+思维)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4027题意:给定两种操作,查询(求出区间内的和),更新(区间内每个值都开根号,取整数)题目给出所有数字之和小于263,所以最大的数最多7次也就变成1。所以在更新的时候加个判... 查看详情
hdu--5023acorruptmayor'sperformanceart(线段树+区间更新+位运算)
DescriptionCorruptgovernorsalwaysfindwaystogetdirtymoney.Paintsomething,thenselltheworthlesspaintingatahighpricetosomeonewhowantstobribehim/heronanauction,thisseemedasafewayformayorXtomakemoney. 查看详情
hdu3397sequenceoperation线段树区间更新区间合并
题意:5种操作,所有数字都为0或10ab:将[a,b]置01ab:将[a,b]置12ab:[a,b]中的0和1互换3ab:查询[a,b]中的1的数量4ab:查询[a,b]中的最长连续1串的长度这题看题目就很裸,综合了区间更新,区间合并我一开始把更新操作全放一个变量... 查看详情
java-hdu1698(线段树的区间更新,和区间查询)(代码片段)
HDU1698:题目意思:JustaHookTimeLimit:4000/2000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):49065 AcceptedSubmission(s):23200ProblemD 查看详情
hdu6070(分数规划/二分+线段树区间更新,区间最值)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6070 题意:给出一个题目提交序列,从中选出一个正确率最小的子串.选中的子串中每个题目当且仅当最后一次提交是正确的. 思路:分数规划二分答案,然后在check函数中查找是否存在... 查看详情