HDU4614【线段树。】【花瓶与插花】 _恶心

题目链接：
果然看了理解了一下大牛的代码然后自己敲结果果然有不少错误
回复说，线段树做为一种数据结构，最好以一种风格过一题裸的然后作为自己的模板
。。
二分写的也很恶心哪

文章插图
还有题目稍复杂一点的注定得推敲各种公式，不光DP注意边界那样令自己恶心，就是这些公式+1，-1结果都是差之千里，或者自己根本调试不出来。
思路很重要，模板也比较重要，线段树裸敲的话容易出错，比树状数组出错几率大的多。
【HDU4614【线段树。】【花瓶与插花】】

#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_backtypedef 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];//这地方也有技巧 线段树要存多大的数据 比如树高为Hvoid 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？而不是+2int 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;}