CF1340F Nastya and CBS

一Iris一 · 2021-08-01 21:55:54 · 题解

首先考虑如何维护一段括号序列。

根据观察可知，对一个括号序列来说，若存在这种形式 '{ )' 则包含该区段的询问均不合法，反之不存在则说明可能构成合法的解。这启发我们可以将一个段都进行这样的缩区间，然后对于一个询问将其全部拼在一起，在拼的时候考虑一下是否满足上述情况。

对于的判断两个括号序列是否相同时采用 Hash 维护，具体来说维护一个左向开始的 Hash 和右向开始的 Hash，同种括号不同方向用绝对值即可

针对上述解法，分块无疑是最好写的，这也是大多数题解采用的方法，，复杂度为 O(n\sqrt n) （这里默认 n 与 q 同阶

这里给出一种官方题解做法：线段树套可持久化文艺平衡树，时间复杂度是 O(n \log^2n),空间复杂度是 O(n\log n + q\log n)。并且因为我太菜了，不会随时回收可持久化平衡树的节点，所以是每 10^4 次扫一遍线段树找出所有废弃节点，回收再利用。（用可持久化平衡树实现细节还挺多的，还是分块好写

虽然看起来是这玩意复杂度更优，但它常数实在是太大了……

#include<bits/stdc++.h>

using namespace std;

#define INF 1ll<<30
#define ill unsigned int

template<typename _T>
inline void read(_T &x)
{
    x=0;char s=getchar();int f=1;
    while(s<'0'||s>'9') {f=1;if(s=='-')f=-1;s=getchar();}
    while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
    x*=f;
}
const int np = 1e5 + 5;
template<typename _T>
inline _T Abs(_T &x)
{
    return x < 0?-x:x;
}
int pare[np];
const int qt = 90;
int ch[2][qt * np],pri[np * qt],val[np * qt];
ill Hashl[np * qt],Hashr[np * qt];
const ill base = 29;
bitset<np * 90> use;
ill p_[np];
int siz[np * qt],tail = 1;//,cnt;//,tail;//,rot[23333]cnt;
#define ls(x) (ch[0][x])
#define rs(x) (ch[1][x])

inline int Rub()
{
    while(use[tail]) tail++;
    return tail++;
}

inline int New(int a)
{
//  ++cnt;
    int cnt;
    cnt = Rub();
    val[cnt] = a;
    Hashl[cnt] = Hashr[cnt] = Abs(a);
    ls(cnt) =rs(cnt) = 0;
    pri[cnt] = rand();
    siz[cnt] = 1;
    return cnt;
}

inline void cop(int x,int y)
{
    ls(x) = ls(y),rs(x) = rs(y);
    pri[x] = pri[y],val[x] = val[y];
    Hashl[x] = Hashl[y],Hashr[x] = Hashr[y];
    siz[x] = siz[y];
}

inline void pushup(int x)
{
    siz[x] = siz[ls(x)] + siz[rs(x)] + 1;
    Hashl[x] = Hashl[rs(x)] + p_[siz[rs(x)]] * Abs(val[x]) + p_[(siz[rs(x)] + 1)] * Hashl[ls(x)]; // 左边比较高的哈希 
    Hashr[x] = Hashr[ls(x)] + p_[siz[ls(x)]] * Abs(val[x]) + p_[(siz[ls(x)] + 1)] * Hashr[rs(x)]; // 右边比较高的哈希 
}
//int flag = 0;
//inline void Debug(){int op;return;}
inline void split(int now,int k,int &x,int &y)
{
//  if(flag == 2333) Debug();
    if(!now) return (void)(x = y = 0);
    if(siz[ls(now)] + 1 <= k)
    {
        x = now;
        split(rs(now),k - siz[ls(now)] - 1,rs(x),y);
    }
    else
    {
        y = now;
        split(ls(now),k,x,ls(y));
    }
    pushup(now);
}

inline int Merge(int x,int y)
{
    if(!x || !y) return x | y;
    if(pri[x] < pri[y])
    {
        rs(x) = Merge(rs(x),y);
        pushup(x);
        return x;
    }
    else
    {
        ls(y) = Merge(x,ls(y));
        pushup(y);
        return y;
    }
}

inline void split_(int now,int k,int &x,int &y)
{
//  if(flag == 23) Debug(); 
    if(!now) return (void)(x = y = 0);
    if(siz[ls(now)] + 1 <= k)
    {
        x = Rub();//++cnt;
        cop(x,now);
        split_(rs(x),k - siz[ls(now)] - 1,rs(x),y);
        pushup(x);
    }
    else
    {
        y = Rub();//++cnt;
        cop(y,now);
        split_(ls(y),k,x,ls(y));
        pushup(y);
    }
}

#define Merge_ Merge

inline ill lHash(int p,int l,int r)
{
    if(l > r) return 0;
    int x,y,z;
    ill Ans(0);
    split(p,r,x,y);
    split(x,l-1,x,z);
    Ans = Hashl[z];
    p = Merge(Merge(x,z),y);
    return Ans;
}

//int flag = 0;
inline ill rHash(int p,int l,int r)//合并分裂之后树的形态是不变的所以不用新建节点
{
//  if(flag && l == 2 && r == 3) Debug();//flag = 2333,cerr<<siz[x]<<'\n',
    if(l > r) return 0;
    int x,y,z;
    ill Ans(0);
    split(p,r,x,y);
//  flag = 1;
    split(x,l-1,x,z);
    Ans = Hashr[z];
    p = Merge(Merge(x,z),y);
    return Ans;
}

inline void FHQ_rec(int x)
{
    if(ls(x)) FHQ_rec(ls(x));
    use[x] = 1;
    if(rs(x)) FHQ_rec(rs(x));
}

struct trans{
    int id,l_,r_;
};

struct Node{//建一棵线段树，每个节点维护一棵平衡树，平衡树中维护所有字符串
//同时维护左向哈希和右向哈希 
//  int l,r;
    int rt;
    short typ;
    int sl,sr;
    Node *ls,*rs;
//  int ls,rs;

    inline void rec()
    {
        if(ls) ls->rec();
        FHQ_rec(rt);
        if(rs) rs->rec();
     } 
//  #define LS(x) 
    inline void cl(){rt = typ = sl = sr = 0;}
    inline bool inrange(int l,int r,int L,int R){return L <= l && r <= R;}
    inline bool outofrange(int l,int r,int L,int R){return r < L || R < l;}
    inline int debug(){int op =1;return op;}
    inline void pushup() // pushup -> O()
    {
//      if(flag && l == 1 && r == 5) debug(),flag = 23;
        typ = ls->typ & rs->typ;
        if(!typ) return;
        int ql , qr , q;
        ql = ls->sr,qr = rs->sl;
        q = min(ql,qr);
        ill a1 = lHash(rs->rt,1,q);
        ill a2 = rHash(ls->rt,siz[ls->rt] - q + 1,siz[ls->rt]);
        if(a1 == a2)
        {
            int x,y,a,b;
            split_(ls->rt,siz[ls->rt] - q,x,y);
            split_(rs->rt,q,a,b);
            rt = Merge_(x,b);
//          printf("ls->sl = %d ls->sr = %d q = %d\n",ls->sl,ls->sr,q);
//          printf("rs->sl = %d rs->sr = %d q = %d\n",rs->sl,rs->sr,q);
            sl =ls->sl + qr - q;
            sr =rs->sr + ql - q;
//          printf("rt = %d sl = %d sr = %d l = %d r = %d typ = %d\n",rt,sl,sr,l,r,typ);
        }
        else typ = 0;
    }

    inline trans query(int l,int r,int L,int R)
    {
        if(inrange(l,r,L,R))
        {
            return typ?(trans){rt,sl,sr}:(trans){-2,0,0};
        }
        else
        {
            if(!outofrange(l,r,L,R))
            {
                int mid = l + r >> 1;
                trans op1 = ls->query(l,mid,L,R),op2 = rs->query(mid+1,r,L,R);
                int r1 = op1.id;
                int r2 = op2.id;
                int x,y,a,b;
                if(r1 == -2 || r2 == -2) return (trans){-2,0,0};
                if(r1 != -1 && r2 != -1) 
                {
                    int ql,qr,q;
                    ql = op1.r_;
                    qr = op2.l_;
                    q = min(ql,qr);
                    ill a1,a2;
                    a1 = lHash(r2,1,q);
                    a2 = rHash(r1,siz[r1] - q + 1,siz[r1]);
                    if(a1 == a2)
                    {
                        split_(r1,siz[r1] - q,x,y);
                        split_(r2,q,a,b);
                        return (trans){Merge_(x,b),op1.l_ + qr - q,op2.r_ + ql - q};
                    }
                    else return (trans){-2,0,0};
                }
                else if(r1 != -1) return op1;
                else if(r2 != -1) return op2;

            }
            else return (trans){-1,0,0};
        }
    }

    inline void upd(int l,int r,int pos,int vl)
    {
        if(inrange(l,r,pos,pos))
        {
            cl();
            rt = New(vl);
//          sl = sr = 0;
            if(vl > 0) typ = sr = 1;
            else typ = sl = 1;
        }
        else
        {
            if(!outofrange(l,r,pos,pos))
            {
                int mid = l + r >> 1;
                ls->upd(l,mid,pos,vl);
                rs->upd(mid+1,r,pos,vl);
                cl();
                pushup();
            }

        }
    }

}mem[np * 2],*pool = mem,*rot;
inline Node *New(){return ++pool;}
inline Node *build(int L,int R)
{
    Node *u = New();
//  u->l = L,u->r = R;
    if(L == R)
    {
        u->ls = u->rs = NULL;
        u->rt = New(pare[L]);
        if(pare[L] > 0) u->typ = u->sr = 1;
        else u->typ=u->sl = 1;
    }
    else
    {
        int mid = L + R >> 1;
        u->ls = build(L,mid);
        u->rs = build(mid + 1,R);
        u->pushup();
    }
    return u;
}

signed  main()
{
    int n,k,q;
    p_[0] = 1;
//  cout<<"*";
//  cerr<<n<<" ";
    for(int i=1;i<=1e5;i++) p_[i] = p_[i - 1] * base;//cerr<<"*";
    read(n);
    read(k);//cerr<<"*";
//  cerr<<n<<'\n';
    for(int i=1;i<=n;i++) read(pare[i]);//,cerr<<i<<" ";
//  cerr<<"*";//scanf("%d",&pare[i]);cerr<<"*";//read(pare[i]),cerr<<"*";
//  cout<<"*";
    rot = build(1,n);
    read(q);

//  q = 30746;
    for(int i=1,opt,pos,vl,l,r;i <= q;i++)
    {
//      if(i == 30742) flag = 1;
//      else flag = 0;
        read(opt);
        switch(opt)
        {
            case 1:{
                read(pos);
                read(vl);
//              if(flag) rot->upd_(pos,vl);
//              else 
                rot->upd(1,n,pos,vl);
//              pare[pos] = vl;
                break;
            }
            case 2:{
//              cout<<i<<" ";
                read(l);
                read(r);
                trans ans = rot->query(1,n,l,r);
                if(ans.id == -2) printf("No\n");
                else if(ans.l_ || ans.r_) printf("No\n");

                else printf("Yes\n");

                break;
            }
        }
        if(i % 10000 == 0) 
        {
            use.reset();
            rot->rec();
            tail = 1;
        }

//      printf("rt = %d sl = %d sr = %d typ = %d\n",rot->rt,rot->sl,rot->sr,rot->typ);

    }
    return 0;
 }

敲了 400+ 行，真是吐了（其实还是代码能力不行