【题解】CF2096F

CF2096F

题目

暴力

显然有一个 $O(qm\log n)$ 的暴力，对于每组询问逐条便利语句，是 $0$ 类型则将区间 $[a_i,b_i]$ 赋值为 $0$。赋值完后将剩下的空位赋值为 $1$，并检查每个 $1$ 类型的语句是否合法。

优化

分析

考虑优化。

注意到题目不强制在线，只要求出 $mx{l}_i$ 为对于 $i$ 语句前面最前的语句使得语句 $[mx{l}_i,i]$ 可以同时成立。

显然 $mx{l}_i$ 单调不降，则可以用双指针维护。

我们用 $c_i$ 表示 $i$ 这个位置被 $0$ 语句覆盖的次数。

新加入一个 $1$ 语句 $i$

我们只需要判断 ${\min }_{j=a_i}^{b_i}{c}_j$ 是否大于 $0$ 即可，等于则合法。

删除一个 $0$ 语句 $i$

我们要让 $j\in [a_i,b_i]$ 的 $c_j$ 减一。

显然 $c$ 的维护可以开一颗线段树。

我们用 $m{x}_i$ 表示类型为 $1$ 且右端点为 $i$ 的询问的左端点的最大值。即 $m{x}_i={\max }_{x_j=1,b_j=i}{a}_j$

新加入一个 $0$ 语句 $i$

先将区间 $[a_i,b_i]$ 的 $c$ 加 $1$

考虑找出最大的区间 $[x,y]$ 满足 $x\le a_i,b_i\le y,{\min }_{j=x}^y{c}_j>0$，然后判断 ${\max }_{j=x}^{y}m{x}_j$ 是否小于 $x$ 即可，小于即合法。

删除一个 $1$ 语句 $i$

考虑如何维护 $m{x}_i$，可以直接暴力的搞一个线段树维护 $m{x}_i$ 的最大值，再用 $n$ 个 multiset 维护 $m{x}_i$，这样单次修改的均摊复杂度是 $O(\log n)$ 的。

最后讲一下如何找到 $x,y$。可以得出 $x$ 为 $[0,a_i-1]$ 中最右边的 $c_x$ 为 $0$ 的位置再加 $1$，$y$ 为 $[b_i+1,n+1]$ 中最左边的 $c_y$ 为 $0$ 的位置再减 $1$。可以线段树上二分维护。

最终我们开两个线段树和 $n$ 个 multiset，总时间复杂度为 $O(m\log n)$，可以通过此题。

代码

代码：

#define ls x<<1
#define rs x<<1|1
#define mid ((l+r)>>1)
struct TR_{int mi[N<<2],add[N<<2];void pushup(int x){mi[x]=min(mi[ls],mi[rs]);}void pushdown(int x){if(add[x]){int &ad=add[x];mi[ls]+=ad,mi[rs]+=ad;add[ls]+=ad,add[rs]+=ad;ad=0;}}int ask(int x,int l,int r,int ql,int qr){if(ql<=l&&r<=qr)return mi[x];int res=1e9;pushdown(x);if(ql<=mid)res=min(res,ask(ls,l,mid,ql,qr));if(qr>mid)res=min(res,ask(rs,mid+1,r,ql,qr));return res;}void modify(int x,int l,int r,int ql,int qr,int k){if(ql<=l&&r<=qr){mi[x]+=k,add[x]+=k;return ;}pushdown(x);if(ql<=mid)modify(ls,l,mid,ql,qr,k);if(qr>mid)modify(rs,mid+1,r,ql,qr,k);pushup(x);}int askl(int x,int l,int r,int ql,int qr){if(l==r)return !mi[x]?l:n+1;pushdown(x);if(ql<=l&&r<=qr){if(!mi[ls])return askl(ls,l,mid,ql,qr);return askl(rs,mid+1,r,ql,qr);}int res=n+1;if(ql<=mid)res=min(res,askl(ls,l,mid,ql,qr));if(qr>mid)res=min(res,askl(rs,mid+1,r,ql,qr));return res;}int askr(int x,int l,int r,int ql,int qr){if(l==r)return !mi[x]?l:0;pushdown(x);if(ql<=l&&r<=qr){if(!mi[rs])return askr(rs,mid+1,r,ql,qr);return askr(ls,l,mid,ql,qr);}int res=0;if(ql<=mid)res=max(res,askr(ls,l,mid,ql,qr));if(qr>mid)res=max(res,askr(rs,mid+1,r,ql,qr));return res;}
}A;
multiset<int>ps[N];
struct TR__{int mx[N<<2];void pushup(int x){mx[x]=max(mx[ls],mx[rs]);}void modify(int x,int l,int r,int pos,int k,int type){if(l==r){if(type==1)ps[l].insert(k);elseps[l].erase(ps[l].find(k));if(!ps[l].empty())mx[x]=*ps[l].rbegin();elsemx[x]=0;return ;}if(pos<=mid)modify(ls,l,mid,pos,k,type);elsemodify(rs,mid+1,r,pos,k,type);pushup(x);}int ask(int x,int l,int r,int ql,int qr){if(ql<=l&&r<=qr)return mx[x];int res=0;if(ql<=mid)res=max(res,ask(ls,l,mid,ql,qr));if(qr>mid)res=max(res,ask(rs,mid+1,r,ql,qr));return res;}
}B;
int mxl[N];
int opt[N],opx[N],opy[N];
void cl(int n){for(int i=1;i<=4*n;i++)A.mi[i]=A.add[i]=0,B.mx[i]=0;for(int i=1;i<=n;i++)ps[i].clear();
}
void solve(){cin>>n>>m;int l=1;for(int r=1;r<=m;r++){int op,x,y;cin>>op>>x>>y;opt[r]=op,opx[r]=x,opy[r]=y;if(!op)A.modify(1,1,n,x,y,1);elseB.modify(1,1,n,y,x,1);while(l<=r){if(!op){int al=A.askr(1,1,n,1,x)+1,ar=A.askl(1,1,n,y,n)-1;if(B.ask(1,1,n,al,ar)<al)break;}elseif(A.ask(1,1,n,x,y)==0)break;if(!opt[l])A.modify(1,1,n,opx[l],opy[l],-1);elseB.modify(1,1,n,opy[l],opx[l],-1);l++;}mxl[r]=l;}int q;cin>>q;while(q--){int l,r;cin>>l>>r;cout<<(l>=mxl[r]?"YES\n":"NO\n");}cl(n);
}