题意:
给你 N 个花瓶, 编号是 0 到 N - 1 , 一开始每个花瓶都是空的, 你有两个操作:
第一个操作:
从第 x 个花瓶起开始插花, 总共插 y 束, 如果遇到花瓶中有花就跳过这个花瓶, 直到花插完或者
插到第 N-1 个花瓶为止, 输出插第一朵花的位置和最后一朵花的位置
第二个操作
将第 x 个花瓶到第 y 个花瓶之间的花扔掉, 输出扔掉的花的数目
链接: http://acm.hdu.edu.cn/showproblem.php?pid=4614
思路
我们通过线段树来记录每个区间中花的数目, 区间长度减去该区间中花的数目即为该区间
中空花瓶的数目, 我们通过二分位置来确定插花的起始位置和终止位置
代码:
- #include <bits/stdc++.h>
- int n,m;
- using namespace std;
- const int MAXN=5e4+4;
- typedef long long ll;
- int lazy[MAXN<<4],tree[MAXN<<4];
- void push_up(int node)
- {
- tree[node]=tree[node<<1]+tree[node<<1|1];
- }
- void build(int node,int l,int r)
- {
- lazy[node]=-1,tree[node]=0;
- if(l==r)
- return;
- int mid=(l+r)>>1;
- build(node<<1,l,mid);
- build(node<<1|1,mid+1,r);
- }
- void push_down(int node,int l,int r,int mid)
- {
- if(lazy[node]!=-1)
- {
- lazy[node<<1]=lazy[node<<1|1]=lazy[node];
- tree[node<<1]=(mid-l+1)*lazy[node];
- tree[node<<1|1]=(r-mid)*lazy[node];
- lazy[node]=-1;
- }
- }
- void update(int node,int l,int r,int x,int y,int k)
- {
- if(x<=l&&y>=r)
- {
- lazy[node]=k;
- tree[node]=(r-l+1)*k;
- return;
- }
- int mid=(l+r)>>1;
- push_down(node,l,r,mid);
- if(x<=mid)
- update(node<<1,l,mid,x,y,k);
- if(y>mid)
- update(node<<1|1,mid+1,r,x,y,k);
- push_up(node);
- }
- int query(int node,int l,int r,int x,int y)
- {
- if(x<=l&&y>=r)
- {
- return tree[node];
- }
- int mid=(l+r)>>1;
- push_down(node,l,r,mid);
- int ans=0;
- if(x<=mid)
- ans+=query(node<<1,l,mid,x,y);
- if(y>mid)
- ans+=query(node<<1|1,mid+1,r,x,y);
- return ans;
- }
- int search_(int x,int num) // 二分查找位置
- {
- int temp=query(1,0,n,x,n);//x 到 n 的空位数
- if(temp==n-x+1)// 没有空位的情况下
- return -1;
- // 如果从 x 到 n 的空位数比要插的数少, 那么要插的数就是 x 到 n 的空位数
- if(n-x+1-temp<num)
- num=n-x+1-temp;
- int down=x,up=n,index=0;
- while(down<=up)
- {
- int mid=(down+up)>>1;
- if(mid-x+1-query(1,0,n,x,mid)<num)
- down=mid+1;
- else
- if(mid-x+1-query(1,0,n,x,mid)>num)
- up=mid-1;
- else
- {
- index=mid;up=mid-1;
- }
- }
- return index;
- }
- int main()
- {
- int t;scanf("%d",&t);
- while(t--)
- {
- scanf("%d%d",&n,&m);n--;
- build(1,0,n);
- while(m--)
- {
- int op,x,y;
- scanf("%d%d%d",&op,&x,&y);
- if(op==1)
- {
- int fir=search_(x,1);// 寻找第一个位置
- if(fir==-1)
- printf("Can not put any one.\n");
- else
- {
- int sec=search_(x,y);// 寻找第二个位置
- printf("%d %d\n",fir,sec);
- update(1,0,n,fir,sec,1);// 修改区间值
- }
- }
- else
- {
- printf("%d\n",query(1,0,n,x,y));
- update(1,0,n,x,y,0);// 修改区间值
- }
- }
- printf("\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3395828.html