CF1340F

Purslane · 2024-01-30 21:42:09 · 题解

Solution

今天 lxl 在第一课堂讲的题。相信大家都会了，所以我不写可持久化平衡树。

考虑单次询问使用暴力的 O(n) 的查询，只需要维护一个表示左括号的栈，从左到右扫描的时候遇到左括号直接入栈，遇到右括号看栈顶元素是否与这个右括号匹配。

考虑优化这个过程。如果在一段匹配的括号串上截取连续的一端，每次删去相邻两个匹配的左右括号，最终必定形成“一段连续的右括号+一端连续的左括号”这种形态。（证明：使用反证法。假设最后剩下的括号中，有一对相邻的左右括号，但他们并不匹配，这种情况下必定不能形成合法的括号串。）

那么考虑使用分块，在每个块内维护一下我们扫描这个块内所有的节点最后剩下的左右括号分别是哪些。

询问区间 [l,r] 的时候，我们按照“散块-整块-散块”的顺序合并。

很容易发现，每次没有匹配的括号只能是左括号，且如果这些括号原来在整块中，最后剩下来的必定是连续的一段。

每次加入一段右括号的时候，使用哈希判断是否能用栈顶的左括号把这些右括号完全抵消掉。如果不能，无解。左括号直接怼到栈顶。

复杂度 O(n \sqrt n)。(认为 n 和 q 同阶）

代码：

#include<bits/stdc++.h> 
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10,MAXK=400+10,MOD=1e9+9;
int n,k,q,blc,tp[MAXN],bl[MAXN],pw[MAXN],L[MAXK],R[MAXK],flg[MAXK];
int lenl[MAXK],hshl[MAXK][MAXK];
int lenr[MAXK],hshr[MAXK][MAXK];
void rebuild(int id) {
    flg[id]=lenl[id]=lenr[id]=0;
    stack<int> ll,rr;
    ffor(i,L[id],R[id]) {
        if(tp[i]>0) ll.push(tp[i]); 
        else if(!ll.empty()) {if(ll.top()!=-tp[i]) return ;ll.pop();}
        else rr.push(-tp[i]);
    }
    vector<int> lb,rb;
    while(!ll.empty()) lb.push_back(ll.top()),ll.pop(); reverse(lb.begin(),lb.end());
    while(!rr.empty()) rb.push_back(rr.top()),rr.pop();
    flg[id]=1,lenl[id]=lb.size(),lenr[id]=rb.size();
    ffor(i,1,lenl[id]) hshl[id][i]=(hshl[id][i-1]*(k+1)+lb[i-1])%MOD;   
    ffor(i,1,lenr[id]) hshr[id][i]=(hshr[id][i-1]*(k+1)+rb[i-1])%MOD;
    return ;
}
struct Node {int op,st,len;};
int get_hash_l(int op,int id,int l,int r) {if(op==0) return id; int ans=hshl[id][r]-hshl[id][l-1]*pw[r-l+1]; return (ans%MOD+MOD)%MOD;}
int get_hash_r(int op,int id,int l,int r) {if(op==0) return id; int ans=hshr[id][r]-hshr[id][l-1]*pw[r-l+1]; return (ans%MOD+MOD)%MOD;}
int solve(int l,int r) {
    stack<Node> ll;
    if(bl[l]==bl[r]) {
        ffor(i,l,r) {
            if(tp[i]>0) ll.push({0,tp[i],1});
            else {
                if(!ll.empty()) {
                    if(get_hash_l(ll.top().op,ll.top().st,ll.top().len,ll.top().len)!=-tp[i]) return 0;
                    ll.top().len--;
                    if(ll.top().len==0) ll.pop();
                }
                else return 0;
            }
        }
        if(ll.empty()) return 1;
        return 0;
    }
    ffor(i,l,R[bl[l]]) {
        if(tp[i]>0) ll.push({0,tp[i],1});
        else {
            if(!ll.empty()) {
                if(get_hash_l(ll.top().op,ll.top().st,ll.top().len,ll.top().len)!=-tp[i]) return 0;
                ll.top().len--;
                if(ll.top().len==0) ll.pop();
            }
            else return 0;
        }
    }
    ffor(i,bl[l]+1,bl[r]-1) {
        if(!flg[i]) return 0;
        int len=lenr[i];
        while(len) {
            if(ll.empty()) break ;
            int Len=min(len,ll.top().len);
            if(get_hash_l(ll.top().op,ll.top().st,ll.top().len-Len+1,ll.top().len)!=get_hash_r(1,i,len-Len+1,len)) return 0;
            ll.top().len-=Len,len-=Len;
            if(!ll.top().len) ll.pop();
        }
        if(len) return 0;
        if(lenl[i]) ll.push({1,i,lenl[i]});
    }
    ffor(i,L[bl[r]],r) {
        if(tp[i]>0) ll.push({0,tp[i],1});
        else {
            if(!ll.empty()) {
                if(get_hash_l(ll.top().op,ll.top().st,ll.top().len,ll.top().len)!=-tp[i]) return 0;
                ll.top().len--;
                if(ll.top().len==0) ll.pop();
            }
            else return 0;
        }
    }
    if(ll.empty()) return 1;
    return 0;
}
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>k,blc=sqrt(n); pw[0]=1; ffor(i,1,n) pw[i]=pw[i-1]*(k+1)%MOD;
    ffor(i,1,n) cin>>tp[i];
    ffor(i,1,blc) L[i]=R[i-1]+1,R[i]=i*blc;
    if(R[blc]<n) ++blc,L[blc]=R[blc-1]+1,R[blc]=n;
    ffor(i,1,blc) ffor(j,L[i],R[i]) bl[j]=i;
    ffor(i,1,blc) rebuild(i);
    cin>>q;
    ffor(i,1,q) {
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1) tp[l]=r,rebuild(bl[l]);
        else {
            if(solve(l,r)) cout<<"Yes\n";
            else cout<<"No\n";  
        }
    }
    return 0;
}