首页 >> 大全

HDU4614【线段树。】【花瓶与插花】

2023-12-17 大全 29 作者：考证青年

题目链接：

果然看了理解了一下大牛的代码然后自己敲结果果然有不少错误

回复说，线段树做为一种数据结构，最好以一种风格过一题裸的然后作为自己的模板

。。

二分写的也很恶心哪

花瓶插花问题_花瓶插花线条画_

还有题目稍复杂一点的注定得推敲各种公式，不光DP注意边界那样令自己恶心，就是这些公式+1，-1结果都是差之千里，或者自己根本调试不出来。

思路很重要，模板也比较重要，线段树裸敲的话容易出错，比树状数组出错几率大的多。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define lowbit(i) (i&-i)
#define sqr(x) ((x)*(x))
#define enter printf("\n")
#define is_sqr(x) (x&(x-1))
#define pi acos(-1.0)
#define clr(x)  memset(x,0,sizeof(x))
#define fp1 freopen("in.txt","r",stdin)
#define fp2 freopen("out.txt","w",stdout)
#define pb push_back
typedef long long LL;
const double eps = 1e-7;
const double DINF = 1e100;
const int INF = 1000000006;
const LL LINF = 1000000000000000005ll;
const int MOD = (int) 1e9 + 7;
const int maxn=300005;
template inline T Min(T a,T b){return a inline T Max(T a,T b){return a>b?a:b;}
template inline T Min(T a,T b,T c){return min(min(a, b),c);}
template inline T Max(T a,T b,T c){return max(max(a, b),c);}
struct Node
{
int l,r,sum,add;
}node[maxn];//这地方也有技巧 线段树要存多大的数据 比如树高为H
void build(int root,int l,int r)
{
node[root].l=l;
node[root].r=r;
node[root].add=-1;
node[root].sum=0;
if(node[root].l==node[root].r) return ;
else
{
int mid=(l+r)/2;
build(root*2,l,mid);
build(root*2+1,mid+1,r);
}
}
int query(int root,int l,int r)
{
if(node[root].l==l&&node[root].r==r) return node[root].sum;//又有错误
if(node[root].add>=0)//更新子结点？
{
int ls=root*2,rs=root*2+1;
//node[root].sum=(node[root].r-node[root].l+1)*node[root].add;
//这一步不需要，前面已修改
node[ls].sum=(node[ls].r-node[ls].l+1)*node[root].add;//两处错误
node[rs].sum=(node[rs].r-node[rs].l+1)*node[root].add;// ls rs用不用更新？
node[ls].add=node[rs].add=node[root].add;
node[root].add=-1;
}
int ans=0;
int mid=(node[root].l+node[root].r)/2;
if(r<=mid)
{
return query(root*2,l,r);
}
else if(l>mid)
{
return query(root*2+1,l,r);
}
else
{
ans=query(root*2,l,mid);
ans+=query(root*2+1,mid+1,r);
}
return ans;
}
void update(int root,int l,int r,int add)
{
if(node[root].l==l&&node[root].r==r)//不够掌握的就是他这块的更新和上面的什么关系
{
node[root].add=add;
node[root].sum=(node[root].r-node[root].l+1)*node[root].add;
return;
}
int mid=(node[root].l+node[root].r)/2;
if(r<=mid)
{
update(root*2,l,r,add);
}
else if(l>mid)
{
update(root*2+1,l,r,add);
}
else
{
update(root*2,l,mid,add);
update(root*2+1,mid+1,r,add);
}
node[root].sum=node[root*2].sum+node[root*2+1].sum;
}
int bin_sea(int l,int r,int a)
{
int ll=l;
while(l=a)//最开始没写出二分查找来 后来又因为mid-l+1错了 //第N处错误 //第N+1处错误
r=mid;
else l=mid+1;
}
return l;
}
int main()
{
int ncase;
scanf("%d",&ncase);
while(ncase--)
{
int n,m,i,j;
scanf("%d%d",&n,&m);
n--;
build(1,0,n);
for(i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a==1)
{
int right_num=query(1,b,n);
// printf("~%d\n",right_num);
if(right_num==n-b+1)
printf("Can not put any one.\n");
else
{
int left_num=b==0?0:query(1,0,b-1);//这地方要是b==0的话 left_num直接等于0 （注意点1）//第N+3处错误
//printf("~%d\n",left_num);
int left_pos=bin_sea(0,n,b-left_num+1);//为吗是b-left_num+1？而不是+2
int right_pos=bin_sea(b,n,min(n-b+1-right_num,c));//（注意点2，min）
printf("%d %d\n",left_pos,right_pos);
update(1,left_pos,right_pos,1);
}
}
else if(a==2)
{
printf("%d\n",query(1,b,c));
update(1,b,c,0);
}
}
printf("\n");
}
return 0;
}

tags: 恶心 出错 公式 题目 数组
其他相关
考证青年

最短路问题+最小生成树

01-10 32
考证青年

Google Python挑战赛：不服，就来！

01-09 39
考证青年

金九银十，收下这份 Java String 面试题

01-08 46
考证青年

微软的面试题及答案－看看你的智商

01-08 48
考证青年

30天自制操作系统第11天

01-08 46
考证青年

c语言——卡塔尔世界杯猜球（二维数组）

01-08 37
最新文章

利用区块链等技术，加强对交通运输信用信息的归集共享和分析应用

01-11 328

印尼西爪哇梳邦县发生山体滑坡 已经导致2人死亡

01-11 417

【SpringBoot笔记10】Spring中Bean的6种作用域

01-11 309

ARS548 ARS549RDI 80GHZ毫米波雷达达学习笔记（一)

01-11 339

叠氮PEG修饰二硒化钨 (N3-WSe2；azide

01-11 377

ATFX：黑海运粮遭俄暂停，小麦期货开盘跳涨

01-11 286

关于我们

最火推荐

小编推荐

联系我们

版权声明：本站内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 88@qq.com 举报，一经查实，本站将立刻删除。备案号：桂ICP备2021009421号
Powered By Z-BlogPHP.
复制成功
微信号:
我知道了