bzoj3050 [Usaco2013 Jan]Seating

bzoj3050 [Usaco2013 Jan]Seating

​​ Description

To earn some extra money, the cows have opened a restaurant in their barn specializing in milkshakes. The restaurant has N seats (1 <= N <= 500,000) in a row. Initially, they are all empty. Throughout the day, there are M different events that happen in sequence at the restaurant (1 <= M <= 300,000). The two types of events that can happen are: 1. A party of size p arrives (1 <= p <= N). Bessie wants to seat the party in a contiguous block of p empty seats. If this is possible, she does so in the lowest position possible in the list of seats. If it is impossible, the party is turned away. 2. A range [a,b] is given (1 <= a <= b <= N), and everybody in that range of seats leaves. Please help Bessie count the total number of parties that are turned away over the course of the day.

m(m<=300,000)个操作。操作分2种： 1.A p，表示把编号最小的空着的长度为p的区间图上颜色。 2.L a b，表示把从a到b的区间（包括端点）全部擦干净（没颜色还是没颜色）。 Q：有多少个操作1不能实现？

Input

Line 1: Two space-separated integers, N and M.Lines 2..M+1: Each line describes a single event. It is either a line of the form “A p” (meaning a party of size p arrives) or “L a b” (meaning that all cows in the range [a, b] leave).

Output

Line 1: The number of parties that are turned away.

Sample Input

10 4 A 6 L 2 4 A 5 A 2 INPUT DETAILS: There are 10 seats, and 4 events. First, a party of 6 cows arrives. Then all cows in seats 2..4 depart. Next, a party of 5 arrives, followed by a party of 2.

Sample Output

1

OUTPUT DETAILS: Party #3 is turned away. All other parties are seated.

HINT

样例解释： 首先将1~6图上颜色，再把2~4擦掉，这时不存在长度为5的空着的区间，该操作不能实现，跳过。最后把2~3图上颜色。所以不能实现的操作1有一个，即第三个操作。 Source

Gold

那天看到这题发现想不起来细节怎么做了花时间写了写

维护区间最长空闲和左区间最长空闲和右区间最长空闲即可

#include#include#include#define lc (x<<1)#define rc (x<<1|1)using namespace std;const int N=500050;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}struct node{int ls,rs,mx,lazy;}tree[N<<2];inline void update(int x,int l,int r){ tree[x].mx=max(tree[lc].mx,tree[rc].mx);int mid=l+r>>1; tree[x].mx=max(tree[x].mx,tree[lc].rs+tree[rc].ls); tree[x].ls=(tree[lc].ls==mid-l+1)?tree[lc].ls+tree[rc].ls:tree[lc].ls; tree[x].rs=(tree[rc].rs==r-mid)?tree[rc].rs+tree[lc].rs:tree[rc].rs;}inline void pushdown(int x,int l,int r){ if (!tree[x].lazy) return; if (tree[x].lazy==1){ tree[lc].mx=tree[lc].ls=tree[lc].rs=0; tree[rc].mx=tree[rc].ls=tree[rc].rs=0; tree[lc].lazy=1;tree[rc].lazy=1;tree[x].lazy=0;return; }int mid=l+r>>1; if(tree[x].lazy==-1){ tree[lc].mx=tree[lc].ls=tree[lc].rs=mid-l+1; tree[rc].mx=tree[rc].ls=tree[rc].rs=r-mid; tree[lc].lazy=-1;tree[rc].lazy=-1;tree[x].lazy=0;return; }}inline void build(int x,int l,int r){ if (l==r){tree[x].mx=tree[x].ls=tree[x].rs=1;return;}int mid=l+r>>1; build(lc,l,mid);build(rc,mid+1,r);update(x,l,r);}inline void modify(int x,int l,int r,int l1,int r1,int v){ if (l1<=l&&r1>=r){ if (v){tree[x].mx=tree[x].ls=tree[x].rs=0;tree[x].lazy=1;return;} if (!v){tree[x].mx=tree[x].ls=tree[x].rs=r-l+1;tree[x].lazy=-1;return;} }int mid=l+r>>1;pushdown(x,l,r); if(l1<=mid) modify(lc,l,mid,l1,r1,v); if(r1>mid) modify(rc,mid+1,r,l1,r1,v);update(x,l,r);}inline int query(int x,int l,int r,int len){ if (l==r) return l;int mid=l+r>>1;pushdown(x,l,r); if (tree[lc].mx>=len) return query(lc,l,mid,len); if (tree[lc].rs+tree[rc].ls>=len) return mid-tree[lc].rs+1; return query(rc,mid+1,r,len);}int n,m;int main(){ freopen("bzoj3050.in","r",stdin); n=read();m=read();int ans=0;build(1,1,n); for (int i=1;i<=m;++i){ char ch=gc();while(ch!='A'&&ch!='L') ch=gc(); if (ch=='A'){ int x=read();if(x>tree[1].mx) {++ans;continue;} int l=query(1,1,n,x);modify(1,1,n,l,l+x-1,1); } if (ch=='L'){ int l=read(),r=read(); modify(1,1,n,l,r,0); } }printf("%d\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。