题意
维护一个 \(01\) 串,初始均为 \(0\),支持:
- 单点将 \(1\) 修改为 \(0\)。
- 查询区间中 \(1\) 的个数。
- 查询最长且最靠右的连续 \(0\) 段的靠右的中点,并将其改为 \(1\)。
分析
第一个操作和第二个操作显然使用动态开点线段树维护。
我们只需要解决第三个操作。
我们用平衡树存储连续的 \(0\) 段的左右端点。
维护两棵平衡树,一棵按区间的左端点从小到大排序,另一棵以区间长度为第一关键字,左端点为第二关键字从大到小排序。
询问的时候只需要在第二棵平衡树中取出其最大的元素。
考虑修改操作带来的影响。
单点修改为 \(1\) 会导致一段连续的 \(0\) 段断开成为至多 \(2\) 段。
分类讨论处理一下段的分裂情况。
单点修改为 \(0\) 会导致至多两段连续的 \(0\) 段合并为同一段。
在第一棵树上二分找出插入点前后的连续段,同样分类讨论一下段的合并情况。
时间复杂度 \(O(q\log n+q\log q)\)。
发现平衡树只需要支持查前驱后继,所以可以使用 set
实现。
可以向 set
中加入两个哨兵区间 \([-1,-2],[n+2,n+1]\) 以避免越界分类讨论。
Code
#include<bits/stdc++.h>
using namespace std;
struct SegT
{
struct node
{
uint32_t sum;
node *lc, *rc;
node() {lc=rc=0; sum=0;}
}*rt;
#define mid ((l+r)>>1)
#define lson x->lc, l, mid
#define rson x->rc, mid+1, r
void modify(node *&x, int l, int r, int p, int v)
{
if(!x) x=new node;
x->sum+=v;
if(l==r) return;
if(p<=mid) modify(lson, p, v);
if(p>mid) modify(rson, p, v);
}
uint32_t query(node *x, int l, int r, int L, int R)
{
if(!x) return 0;
if(L<=l&&r<=R) return x->sum;
uint32_t ret=0;
if(L<=mid) ret+=query(lson, L, R);
if(R>mid) ret+=query(rson, L, R);
return ret;
}
}tr;
struct itv
{
int l, r;
int pos() {return (l+r+1)>>1;}
itv(int L, int R) {l=L, r=R;}
};
#define len(x) (x.r-x.l+1)
struct cmp1{bool operator()(itv a, itv b)const{return a.l<b.l;}};
struct cmp2{bool operator()(itv a, itv b)const{return len(a)==len(b)?a.l>b.l:len(a)>len(b);}};
set<itv, cmp1> s1;
set<itv, cmp2> s2;
map<int, int> pos;
void emplace(int x, int y) {s1.emplace(x, y), s2.emplace(x, y);}
void emplace(itv &x) {s1.emplace(x), s2.emplace(x);}
void erase(itv &x) {s1.erase(x), s2.erase(x);}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, q, l, r, k;
cin>>n>>q;
emplace(1, n);
emplace(-1, -2);
emplace(n+2, n+1);
while(q--)
{
cin>>k;
if(!k)
cin>>l>>r,
cout<<tr.query(tr.rt, 1, n, l, r)<<'\n';
else
{
if(!pos[k])
{
auto seg=*s2.begin();
erase(seg);
int p=seg.pos();
pos[k]=p;
tr.modify(tr.rt, 1, n, p, 1);
if(p!=seg.l) emplace(seg.l, p-1);
if(p!=seg.r) emplace(p+1, seg.r);
}
else
{
int p=pos[k];
pos[k]=0;
tr.modify(tr.rt, 1, n, p, -1);
auto it=s1.lower_bound({p, 0});
auto seg2=*it, seg1=*--it;
if(seg1.r==p-1&&seg2.l==p+1)
erase(seg1), erase(seg2),
emplace(seg1.l, seg2.r);
else if(seg1.r==p-1) erase(seg1), emplace(seg1.l, p);
else if(seg2.l==p+1) erase(seg2), emplace(p, seg2.r);
else emplace(p, p);
}
}
}
}
标签:node,emplace,插排,int,题解,void,TJOI2014,itv,return
From: https://www.cnblogs.com/redacted-area/p/18405331