Vases and Flowers HDU - 4614

題意:

一排空瓶子放花，操作1：從第x個瓶子開始放花，放y朵花，每個瓶子就一朵花，如果碰到已經(jīng)有花的瓶子跳過這個瓶子，看下一個，當(dāng)花沒了，或者瓶子不夠了結(jié)束，輸入第一個放花的瓶子和最后一個放花的瓶子，如果一朵花都沒放進瓶子輸出一行字符’Can not put any one.’，操作2：把x到y(tǒng)之間的花清空，輸出清空花的數(shù)量

題解：

操作2好做，操作1的起點終點如何確定？我們可以直接二分確定，先二分確定左端點，然后利用左端點，再二分確定右端點。

代碼：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b); typedef long long ll; using namespace std; const ll mod=1e4+7; const int maxn=1e5+50;int lazy[maxn<<2],ans[maxn<<2]; int n,m;void pushup(int rt) {ans[rt]=ans[rt<<1]+ans[rt<<1|1]; }void pushdown(int rt,int m) {if(lazy[rt]!=-1){ans[rt<<1]=lazy[rt]*(m-(m>>1));ans[rt<<1|1]=lazy[rt]*(m>>1);lazy[rt<<1]=lazy[rt];lazy[rt<<1|1]=lazy[rt];lazy[rt]=-1;} }void Update(int L,int R,int l,int r,int rt,int c) {if(L<=l && r<=R){ans[rt]=c*(r-l+1);lazy[rt]=c;return;}pushdown(rt,r-l+1);int mid=(r+l)>>1;if(L<=mid)Update(L,R,l,mid,rt<<1,c);if(R>mid)Update(L,R,mid+1,r,rt<<1|1,c);pushup(rt); }int Query(int L,int R,int l,int r,int rt) {if(L<=l && r<=R){return ans[rt];}pushdown(rt,r-l+1);int ANS=0;int mid=(l+r)>>1;if(L<=mid)ANS+=Query(L,R,l,mid,rt<<1);if(R>mid)ANS+=Query(L,R,mid+1,r,rt<<1|1);return ANS; }int findst(int l,int r) {if(Query(l,r,0,n-1,1)==(r-l+1))return -1;while(l<r){int mid=(l+r)>>1;if(Query(l,mid,0,n-1,1)<(mid-l+1))r=mid;else l=mid+1;}return l; }int finded(int l,int r,int f) {int st=l;f=min(f,(r-l+1)-Query(l,r,0,n-1,1));while(l<r){int mid=(l+r)>>1;if((mid-st+1)-Query(st,mid,0,n-1,1)<f)l=mid+1;else r=mid;}return l; }int main() { // freopen("in.txt","r",stdin);int t;scanf("%d",&t);while(t--){memset(lazy,-1,sizeof lazy);memset(ans,0,sizeof ans);scanf("%d%d",&n,&m);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);if(a==2){cout<<Query(b,c,0,n-1,1)<<endl;Update(b,c,0,n-1,1,0);}else{int st=findst(b,n-1);if(st==-1){cout<<"Can not put any one."<<endl;continue;}int ed=finded(st,n-1,c);Update(st,ed,0,n-1,1,1);cout<<st<<" "<<ed<<endl;}}cout<<endl;}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的Vases and Flowers HDU - 4614的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。