C++14(g++5.4) 解法, 执行用时: 778ms, 内存消耗: 30436K, 提交时间: 2019-06-22 14:21:55

#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define lc (t<<1)
#define rc ((t<<1)|1)
#include<algorithm>
const int mn=510000*4;//1050000;
int op,n,m,ans,l[mn],r[mn],len[mn],f[mn],ls[mn],rs[mn],xx,yy,pp,st;
char bz[mn],ss[10];
inline void down(const int t){
	if (bz[t]){
		bz[lc]=bz[rc]=bz[t];
		if (bz[t]==1){
			f[lc]=ls[lc]=rs[lc]=len[lc];
			f[rc]=ls[rc]=rs[rc]=len[rc];
		}else{
			f[lc]=ls[lc]=rs[lc]=f[rc]=ls[rc]=rs[rc]=0;			
		}
		bz[t]=0;
	}
}
inline void up(const int t){
	f[t]=rs[lc]+ls[rc];
	if (f[lc]>f[t]) f[t]=f[lc];
	if (f[rc]>f[t]) f[t]=f[rc];
	ls[t]=ls[lc];
	if (ls[t]==len[lc]) ls[t]+=ls[rc];
	rs[t]=rs[rc];
	if (rs[t]==len[rc]) rs[t]+=rs[lc];
}
void buildt(int t,int x,int y){
	l[t]=x;
	r[t]=y;
	f[t]=ls[t]=rs[t]=y-x+1;
	len[t]=y-x+1;
	if (x<y){
		int mi=(x+y)>>1;
		buildt(lc,x,mi);
		buildt(rc,mi+1,y);
	}
}
void ask(const int t){
	if (l[t]==r[t]){
		st=l[t];
		return;
	}
	down(t);
	if (f[lc]>=pp){
		ask(lc);
		return;
	}
	if (rs[lc]+ls[rc]>=pp){
		st=r[lc]-rs[lc]+1;
		return;
	}
	ask(rc);
}
void chang(const int t,const int x,const int y){
	if (l[t]==x&&r[t]==y){
		bz[t]=op;
		if (op==2){
			f[t]=ls[t]=rs[t]=0;
		}else{
			f[t]=ls[t]=rs[t]=len[t];
		}
		return;
	}
	down(t);	
	if (y<=r[lc]) chang(lc,x,y);else if (x>r[lc]) chang(rc,x,y);else{
		chang(lc,x,r[lc]);
		chang(rc,l[rc],y);
	}
	up(t);
}
int main(){
	scanf("%d%d",&n,&m);
	buildt(1,1,n);
	while (m--){
		scanf("%s",ss);
		if (ss[0]=='A'){
			scanf("%d",&pp);
			if (f[1]>=pp){
				ask(1);
//				printf("find%d\n",st);
				op=2;
				chang(1,st,st+pp-1);
			}else ans++;
		}else{
			scanf("%d%d",&xx,&yy);
			if (xx>yy) std::swap(xx,yy);
			op=1;
			chang(1,xx,yy);
		}
	}
	printf("%d\n",ans);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 790ms, 内存消耗: 31480K, 提交时间: 2019-06-22 20:35:47

#include<bits/stdc++.h>
namespace ZDY{
#define ll long long
#define Fur(i,x,y) for(int i=x;i<=y;i++)
#define in2(x,y) in(x);in(y)
}using namespace ZDY;using namespace std;
#define N 5000011
#define ls rt<<1
#define rs ls|1
#define Z int m=(l+r)>>1
#define lson l,m,ls
#define rson m+1,r,rs
ll s[N<<2],sl[N<<2],sr[N<<2];
int n,q;
short add[N];
inline void pu(int rt,int ln,int rn){
    s[rt]=max(max(s[ls],s[rs]),sr[ls]+sl[rs]);
    sl[rt]=sl[ls]+(sl[ls]==ln)*sl[rs];
    sr[rt]=sr[rs]+(sr[rs]==rn)*sr[ls];
}
inline void pd(int rt,int ln,int rn){
    if(!add[rt]||(!ln&&!rn))return;
    s[ls]=sl[ls]=sr[ls]=(add[rt]>0)*ln;
    s[rs]=sl[rs]=sr[rs]=(add[rt]>0)*rn;
    add[ls]=add[rs]=add[rt];add[rt]=0;
}
inline void build(int l,int r,int rt){
    s[rt]=sl[rt]=sr[rt]=r-l+1;if(l==r)return;
    Z;build(lson);build(rson);
}
inline void upd(int L,int R,int l,int r,int rt,int v){
    if(L<=l&&r<=R){s[rt]=sl[rt]=sr[rt]=(v>0)*(r-l+1),add[rt]=v;return;}
    Z;pd(rt,m-l+1,r-m);
    if(L<=m)upd(L,R,lson,v);
    if(R>m)upd(L,R,rson,v);
    pu(rt,m-l+1,r-m);
}
inline int ask(int c,int l,int r,int rt){
    Z;pd(rt,m-l+1,r-m);
    if(s[ls]>=c)return ask(c,lson);
    else if(sr[ls]+sl[rs]>=c)return m-sr[ls]+1;
    else return ask(c,rson);
}
int main(){
     scanf("%d%d",&n,&q);build(1,n,1);
     int x,y,ans=0,pos;
     while(q--){
	 	char opt;
		cin>>opt;
		if(opt=='A'){
            scanf("%d",&x);
             if(s[1]<x)ans++;
             else{
                pos=ask(x,1,n,1);
                upd(pos,pos+x-1,1,n,1,-1);
             }
        }
        else{scanf("%d%d",&x,&y);upd(x,y,1,n,1,1);}
    }
    cout<<ans<<endl;
}