重新認識vector - -其實就是鏈表式數組，或者說數組式鏈表？ 哈哈哈
其實還是跟 Hotel 一樣，然後加了Get操作吧。
用vector維護一下有多少個區間嘛。
也學會了vector 的erase和insert的應用。
#include
#include
#include
#include
#include
#include
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#define maxn 50005
using namespace std;
int cov[maxn<<2];
int rmax[maxn<<2];
int lmax[maxn<<2];
int cmax[maxn<<2];
struct node
{
int st,ed;
};
vectorcq;
void pushup(int num,int s,int e)
{
int mid=(s+e)>>1;
cmax[num]=max(rmax[num<<1]+lmax[num<<1|1],max(cmax[num<<1],cmax[num<<1|1]));
lmax[num]=lmax[num<<1];
rmax[num]=rmax[num<<1|1];
if(lmax[num]==mid-s+1)lmax[num]+=lmax[num<<1|1];
if(rmax[num]==e-mid)rmax[num]+=rmax[num<<1];
}
void pushdown(int num,int s,int e)
{
if(cov[num]!=-1)
{
int mid=(s+e)>>1;
cov[num<<1]=cov[num<<1|1]=cov[num];
cmax[num<<1]=lmax[num<<1]=rmax[num<<1]=cov[num]?0:mid-s+1;
cmax[num<<1|1]=lmax[num<<1|1]=rmax[num<<1|1]=cov[num]?0:e-mid;
cov[num]=-1;
}
}
void build(int num,int s,int e)
{
cov[num]=-1;
if(s==e)
{
lmax[num]=rmax[num]=cmax[num]=1;
return;
}
int mid=(s+e)>>1;
build(lson);
build(rson);
pushup(num,s,e);
}
void update(int num,int s,int e,int l,int r,int val)
{
if(l<=s && r>=e)
{
cov[num]=val;
lmax[num]=rmax[num]=cmax[num]=val?0:e-s+1;
return;
}
pushdown(num,s,e);
int mid=(s+e)>>1;
if(l<=mid)update(lson,l,r,val);
if(r>mid)update(rson,l,r,val);
pushup(num,s,e);
}
int query(int num,int s,int e,int val)
{
if(s==e)
{
return s;
}
pushdown(num,s,e);
int mid=(s+e)>>1;
if(cmax[num<<1]>=val)return query(lson,val);
else if(rmax[num<<1]+lmax[num<<1|1]>=val)return mid+1-rmax[num<<1];
else return query(rson,val);
}
int bin(int key)
{
int l=0,r=cq.size()-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(cq[mid].st<=key)l=mid+1;
else r=mid-1;
}
return l-1;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
cq.clear();
build(1,1,n);
while(m--)
{
char str[10];
scanf("%s",str);
if(str[0]=='R')
{
cq.clear();
update(1,1,n,1,n,0);
printf("Reset Now\n");
}
else if(str[0]=='N')
{
int v;
scanf("%d",&v);
if(cmax[1]
