分析
题目很简单,给自己复建用的,好久没打代码了,摸鱼必死qwq。
我们读完题目,可以很容易发现,这题就是要维护最长连续区间,区间内全为0。
维护最长连续区间,那就经典维护三个值。len
,llen
,rlen
。分别表示维护,区间最长的线段,从左开始最长线段,从右开始最长线段。
相对于维护的值,可能相对查询会更麻烦些。
查询:需要我们查询起始点最靠左的长度大于等于x的线段的左端点是什么。
等于说是,我们要寻找满足某些条件的最靠左的线段
。
那,很容易就可以想到线段树上二分
。
那本题就结束了。
看代码。
AC_code
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
const int N = 5e4 + 10;
struct Node
{
int l,r;
int len,llen,rlen,tag;
}tr[N<<2];
void pushup(int u)
{
auto &root = tr[u],&left = tr[u<<1],&right = tr[u<<1|1];
root.len = max(right.len,left.len);
root.llen = tr[u<<1].llen;root.rlen = right.rlen;
if(left.llen==left.r-left.l+1) root.llen += right.llen;
if(right.rlen==right.r-right.l+1) root.rlen += left.rlen;
root.len = max(root.len,max(left.rlen+right.llen,max(root.llen,root.rlen)));
}
void build(int u,int l,int r)
{
if(l==r)
{
tr[u] = {l,r,1,1,1,-1};
return ;
}
tr[u] = {l,r,0,0,0,-1};
int mid = l + r >> 1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
void change(Node &u,int k)
{
if(!k) u.len = u.rlen = u.llen = u.r - u.l + 1;
else u.len = u.rlen = u.llen = 0;
u.tag = k;
}
void pushdown(int u)
{
if(tr[u].tag!=-1)
{
change(tr[u<<1],tr[u].tag);
change(tr[u<<1|1],tr[u].tag);
tr[u].tag = -1;
}
}
void modify(int u,int l,int r,int k)
{
if(l<=tr[u].l&&tr[u].r<=r)
{
change(tr[u],k);
return ;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l<=mid) modify(u<<1,l,r,k);
if(r>mid) modify(u<<1|1,l,r,k);
pushup(u);
}
int query(int u,int x)
{
if(tr[u].l==tr[u].r) return tr[u].l;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(tr[u<<1].len>=x) return query(u<<1,x);
else if(tr[u<<1].rlen+tr[u<<1|1].llen>=x) return query(u<<1|1,x-tr[u<<1].rlen);
else if(tr[u<<1|1].len>=x) return query(u<<1|1,x);
return 0;
}
int main()
{
ios;
int n,m;
cin>>n>>m;
build(1,1,n);
while(m--)
{
int op,x,y;
cin>>op>>x;
if(op==1)
{
int t = query(1,x);
if(t)
{
cout<<t-x+1<<"\n";
modify(1,t-x+1,t,1);
}
else cout<<"0\n";
}
else
{
cin>>y;
modify(1,x,x+y-1,0);
}
}
return 0;
}
标签:return,int,线段,Hotel,USACO08FEB,P2894,query,最长
From: https://www.cnblogs.com/aitejiu/p/16629861.html