题解--VSQ

abruce · 2021-07-23 12:57:23 · 题解

很明显 O(n\sqrt{n}\log n) 的算法无法通过如此大的数据范围，我们考虑是否存在 O(n\log^2n) 的算法。
首先我们想到构造一个长度为 n-1 的 01 串 b 为 b_i=a_i\ xor\ a_{i+1}。这样，长度为 k-1 且全为 1 的 b 的子串就代表了一个长度为 k 的 VS 串。
我们考虑如何去维护 b 数组，先看如何查询。
设极长连续串 l,r 为 \forall i\in [l,r] b_i=1 \land b_{l-1}=b_{r+1}=0，设 b_0=b_{n+1}=0。
首先我们开一棵线段树，线段树上每个点维护的是该区间内所有极长连续串，这个可以用类似 ODT 的方式用 set 维护区间。
对于 3 操作，我们需要找到区间内所有极长连续串，对于一个长度为 l(l\ge k-1) 的极长连续串，它对于答案的贡献是 l-k+2。把它拆成 l 和 -k+2 两部分考虑，我们就可以每个节点用一个树状数组维护长度 \ge k-1 的极长连续串长度和和个数。求得答案。
注意当前区间的第一个极长连续串可能和上一个区间的最后一个极长连续串拼接得到答案。 对于 4 操作，我们需要求得区间内极长连续串长度的最大值。我们需要一个可删堆，维护长度的最大值。同理注意当前区间的第一个极长连续串可能和上一个区间的最后一个极长连续串拼接得到答案。

接下来我们看修改。
对于 0/1 操作，我们发现它会将 [l,r-1] 内的 b 全部赋值为 0，我们可以找到这些为 1 的 b，然后将它们一个一个删除。然后注意 l-1 与 l，r 与 r+1 是否会使 b 产生变动。
对于 2 操作，我们发现它对于 [l,r-1] 内的 b 不影响，所以只需要注意 l-1 与 l，r 与 r+1 是否会使 b 产生变动。
为了维护边界，我们需要再来一棵线段树维护 a 的真实值。
我们发现 b 数组中为 1 的数量是 O(n) 个，每次操作最多增加 O(1) 个，所以 0/1 操作删除的数量的总和为 O(n) 个，所以复杂度正确：O(n\log^2n)。
实际上，这个东西常数巨大，在修改很多的时候跑得比暴力还慢。

#include<bits/stdc++.h>
#define lc id<<1
#define rc id<<1|1
using namespace std;
//去掉了快读快写
const int maxn=3e5+5;
typedef const int ci;
struct node {
    int l,r;
    node() {}
    node(ci l,ci r) {
        this->l=l,this->r=r;
    }
    const bool operator<(const node &b)const {
        return l<b.l;
    }
    const bool operator==(const node &b)const {
        return l==b.l&&r==b.r;
    }
} lst;//维护区间结构体
struct que {
    priority_queue<int> q,e;
    void ins(ci x) {
        q.push(x);
    }
    void del(ci x) {
        q.top()==x?q.pop():e.push(x);
    }
    int top() {
        while(q.size()&&e.size()&&q.top()==e.top())q.pop(),e.pop();
        return q.size()?q.top():0;
    }
};//对顶堆
typedef set<node>::iterator iter;
int a[maxn],b[maxn],n,m;
namespace Seg {
    struct tree {
        int l,r,mid;
        char v,tag,rev;
    } t[maxn*4];
    void build(ci id,ci l,ci r) {
        t[id]=(tree) {
            l,r,l+r>>1,0,-1,0
        };
        if(l==r)return t[id].v=a[l],void();
        ci mid=l+r>>1;
        build(lc,l,mid),build(rc,mid+1,r);
    }
    void chtag(ci id,char v) {
        t[id].v=t[id].tag=v,t[id].rev=0;
    }
    void revtag(ci id) {
        t[id].rev^=1,t[id].v^=1;
        if(~t[id].tag)t[id].tag^=1;
    }
    void pushdown(ci id) {
        if(t[id].rev)revtag(lc),revtag(rc),t[id].rev=0;
        char &k=t[id].tag;
        if(~k)chtag(lc,k),chtag(rc,k),k=-1;
    }
    void change(ci id,ci l,ci r,ci v) {
        if(t[id].l>=l&&t[id].r<=r)return chtag(id,v);
        pushdown(id);
        if(l<=t[id].mid)change(lc,l,r,v);
        if(r>t[id].mid)change(rc,l,r,v);
    }
    void rev(ci id,ci l,ci r) {
        if(t[id].l>=l&&t[id].r<=r)return revtag(id);
        pushdown(id);
        if(l<=t[id].mid)rev(lc,l,r);
        if(r>t[id].mid)rev(rc,l,r);
    }
    int ask(ci id,ci v) {
        if(t[id].l==t[id].r)return t[id].v;
        pushdown(id);
        return ask(v<=t[id].mid?lc:rc,v);
    }
}//维护真实值线段树
struct tree {
    int l,r,mid,len;
    set<node> s;
    vector<int> c,w;
    que q;
    void add(int x,ci v) {
        v>0?q.ins(x):q.del(x);
        if(x==1)return;
        ci y=x;
        x=len-x+1;
        while(x<=len)c[x]+=v,w[x]+=v*y,x+=x&(-x);
    }
    int ask(int x) {
        if(x==1)return 0;
        ci y=x;
        int sum=0;
        x=len-x+1;
        while(x)sum+=w[x]-c[x]*(y-1),x-=x&(-x);
        return sum;
    }//维护 3 操作树状数组
    void change0(ci x) {
        iter it=s.upper_bound(node(x,0));
        it--;
        ci l=it->l,r=it->r,len=r-l+1;
        if(l==x&&r==x)return add(1,-1),s.erase(it),void();
        add(len,-1),s.erase(it);
        if(l==x)return add(len-1,1),s.insert(node(l+1,r)),void();
        if(r==x)return add(len-1,1),s.insert(node(l,r-1)),void();
        add(x-l,1),s.insert(node(l,x-1));
        add(r-x,1),s.insert(node(x+1,r));
    }//将 1 变成 0
    void change1(ci x) {
        if(!s.size())return add(1,1),s.insert(node(x,x)),void();
        iter ir=s.upper_bound(node(x,0)),il=ir;
        il--;
        const bool pd1=ir!=s.begin()&&il->r==x-1,pd2=ir!=s.end()&&ir->l==x+1;
        if(!pd1&&!pd2)return add(1,1),s.insert(node(x,x)),void();
        if(!pd2) {
            ci l=il->l;
            add(x-l,-1),s.erase(il);
            add(x-l+1,1),s.insert(node(l,x));
            return;
        }
        if(!pd1) {
            ci r=ir->r;
            add(r-x,-1),s.erase(ir);
            add(r-x+1,1),s.insert(node(x,r));
            return;
        }
        ci l=il->l,r=ir->r;
        add(x-l,-1),s.erase(il);
        add(r-x,-1),s.erase(ir);
        add(r-l+1,1),s.insert(node(l,r));
    }//将 0 变成 1
    iter split(int p) {
        iter it=s.lower_bound(node(p,-1)),tmp=it;
        tmp--;
        if(it!=s.end()&&(it==s.begin()||it->l==p))return it;
        if(tmp->r>=p) {
            int l=tmp->l,r=tmp->r;
            add(r-l+1,-1),s.erase(tmp);
            if(p>l)add(p-l,1),s.insert(node(l,p-1));
            return add(r-p+1,1),s.insert(node(p,r)).first;
        }
        return it;
    }//类似 ODT split 出一段区间
} t[maxn*4];
void build(ci id,ci l,ci r) {
    t[id]=(tree) {
        l,r,l+r>>1,r-l+1
    };
    t[id].c.resize(r-l+2),t[id].w.resize(r-l+2);
    for(register int i=l; i<=r; i++)if(b[i])t[id].change1(i);
    if(l==r)return;
    ci mid=l+r>>1;
    build(lc,l,mid),build(rc,mid+1,r);
}
void add(ci id,ci v,const bool p) {
    p?t[id].change1(v):t[id].change0(v);
    if(t[id].l==t[id].r)return;
    v<=t[id].mid?add(lc,v,p):add(rc,v,p);
}
void del(ci id,ci l,ci r) {
    if(!t[id].s.size())return;
    if(t[id].l>=l&&t[id].r<=r) {
        for(register iter it=t[id].s.begin(); it!=t[id].s.end(); it=t[id].s.erase(it))
            t[id].add(it->r-it->l+1,-1);
        if(t[id].l!=t[id].r)del(lc,l,r),del(rc,l,r);
        return;
    }
    for(iter ir=t[id].split(min(t[id].r,r)+1),il=t[id].split(max(t[id].l,l)); il!=ir; il=t[id].s.erase(il))
        t[id].add(il->r-il->l+1,-1);
    if(l<=t[id].mid)del(lc,l,r);
    if(r>t[id].mid)del(rc,l,r);
}//删除 [l,r-1] 内所有 1
int asksum(ci id,ci l,ci r,ci k) {
    if(t[id].l>=l&&t[id].r<=r) {
        if(!t[id].s.size())return 0;
        int sum=t[id].len>=k?t[id].ask(k):0;
        node now=*t[id].s.begin(),nl=*--t[id].s.end();
        if(lst.r+1!=now.l)return lst=nl,sum;
        sum+=max(now.r-lst.l+1-k+1,0)-max(now.r-now.l+1-k+1,0)-max(lst.r-lst.l+1-k+1,0);
        lst=nl==now?node(lst.l,nl.r):nl;
        return sum;
    }
    int sum=0;
    if(l<=t[id].mid)sum+=asksum(lc,l,r,k);
    if(r>t[id].mid)sum+=asksum(rc,l,r,k);
    return sum;
}//3 操作
int askmax(ci id,ci l,ci r) {
    if(t[id].l>=l&&t[id].r<=r) {
        if(!t[id].s.size())return 1;
        int sum=t[id].q.top();
        node now=*t[id].s.begin(),nl=*--t[id].s.end();
        if(lst.r+1!=now.l)return lst=nl,sum+1;
        sum=max(sum,now.r-lst.l+1),lst=nl==now?node(lst.l,nl.r):nl;
        return sum+1;
    }
    int sum=1;
    if(l<=t[id].mid)sum=max(sum,askmax(lc,l,r));
    if(r>t[id].mid)sum=max(sum,askmax(rc,l,r));
    return sum;
}//4 操作
int main() {
    int op,l,r,z;
    n=read(),m=read();
    for(register int i=1; i<=n; i++)a[i]=read();
    Seg::build(1,1,n);
    for(register int i=1; i<n; i++) {
        b[i]=a[i]^a[i+1];
    }
    build(1,1,n-1);
    while(m--) {
        op=read(),l=read(),r=read();
        if(op<=1) {
            if(l<r)del(1,l,r-1);
            if(l>1) {
                ci x=Seg::ask(1,l-1),y=Seg::ask(1,l);
                if(x!=op&&y!=op)add(1,l-1,1);
                if(x==op&&y!=op)add(1,l-1,0);
            }
            if(r<n) {
                ci x=Seg::ask(1,r+1),y=Seg::ask(1,r);
                if(x!=op&&y!=op)add(1,r,1);
                if(x==op&&y!=op)add(1,r,0);
            }
            Seg::change(1,l,r,op);
        }
        if(op==2) {
            if(l>1)Seg::ask(1,l-1)!=Seg::ask(1,l)?add(1,l-1,0):add(1,l-1,1);
            if(r<n)Seg::ask(1,r)!=Seg::ask(1,r+1)?add(1,r,0):add(1,r,1);
            Seg::rev(1,l,r);
        }
        if(op==3)z=read(),lst=node(-1,-1),printnum(asksum(1,l,r-1,z-1),'\n');
        if(op==4)lst=node(-1,-1),printnum(askmax(1,l,r-1),'\n');
    }
    pc(0,1);
    return 0;
}

写在后面：这个树套树题出的还是很不错的，但我实现的树套树常数过大。如果有常数更为优秀的 O(n\log^2n) 做法，请提出来，谢谢。