P3071 [USACO13JAN]Seating G
Zvelig1205 · · 题解
P3071 [USACO13JAN]Seating G
前言 闲话
哎，P2894 珂朵莉被卡了
推荐题目……
！有一个没做过
于是
题目传送门
思路
那当然珂朵莉了
对于“离开”操作，直接区间推平为 0。
而对于“安置”操作，直接暴力扫一遍珂树，找到足够大的空区间就将客人安置到那里，即区间推平为 1。
找空位的时候，可能出现两个相邻的区间都为 0 的情况（对珂树足够了解的人应该能看懂这句话），所以统计答案时不能只看当前区间，也要注意和之前的区间的关系：
-
当前区间为空：
-
若前一个区间为空，则直接将区间长度累加到待选空区间长度
sum 中； -
若前一个区间不空，则将当前区间的左端点记录为整个待选空区间的左端点
L 。
-
-
当前区间不空：
清空
sum 和L 。 -
找到合适的空区间：
返回空区间左端点。若遍历整个珂树都没有满足条件的
sum ，返回 -1（即无解）
贴一下代码
int n,m,l,r,ans;
struct C_Tree{
int le,ri,val;
C_Tree(int le,int ri=0,int val=0):
le(le),ri(ri),val(val){}
bool operator <(const C_Tree &b)const
{
return le<b.le;
}
};
set<C_Tree>T;
#define IT set<C_Tree>::iterator
IT split(int now)
{
IT i=T.lower_bound(C_Tree(now));
if(i!=T.end()&&i->le==now)return i;
i--;int l=i->le,r=i->ri,v=i->val;
T.erase(i);
T.insert(C_Tree(l,now-1,v));
return T.insert(C_Tree(now,r,v)).first;
}
void assign(int l,int r,int k)
{
IT ir=split(r+1),il=split(l);
T.erase(il,ir);
T.insert(C_Tree(l,r,k));
}
int ask(int siz)
{
int sum=0,pos=0;
for(IT i=T.begin();i!=T.end();i++)
{
if(i->val==0)
{
if(pos==0)pos=i->le;
sum+=i->ri-i->le+1;
if(sum>=siz)return pos;
}
else sum=pos=0;
}
return -1;
}
signed main()
{
n=re();m=re();
T.insert(C_Tree(1,n,0));
for(int i=1;i<=m;i++)
{
char op[10]="";scanf("%s",op);
if(op[0]=='A')
{
l=re(),r=ask(l);
if(r!=-1)assign(r,r+l-1,1);
else ans++;
}
else l=re(),r=re(),assign(l,r,0);
}
wr(ans);
return 0;
}