题解：P11619 [PumpkinOI Round 1] 种南瓜

· · 题解

前置知识：线段树分治。

下面都用形式化题意描述题目内容。

Step 1

首先我们想一下没有删除的操作应该怎么做。对于一对括号，只要维护有没有与它相交的其他括号对即可。

我们可以记 l_i 为右括号在 i 点的所有括号对中左括号所在的最小下标，r_i 为左括号在 i 点的所有括号对中右括号所在的最大下标。

每次插入一对括号 [x,y]，如果 \max_{i=x+1}^y l_i \ge x \land \min_{i=x}^{y-1}r_i \le y，那么就相当于没有与它相交的其他括号对，若之前是合法的，则现在也是合法的；否则不能取出合法括号序列。

然后把 l_y 和 r_x 更新即可，使用线段树维护就能这个区间最小、最大值。

Step 2

我们发现更新 \max \min 之类的东西是没法直接在线段树上撤销的。考虑线段树分治。对时间段建立一棵线段树。这样，我们保证了删除操作一定是删除上一次插入的操作。

那么就很好做了，对于每个操作的单点改最值，记录一下原来这个点的值是多少，在删除的时候搞回去就行了。

时间复杂度 O(n \log^2n)（视 n,q 同阶）。

Step 3

哦对了，记得优化一下，如果当前这个区间已经不成立，那么就不用再递归了，直接输出。

笔者代码把两棵线段树建在了一起。

#include<bits/stdc++.h>
#define i128 __int128
#define ll long long
#define ull unsigned long long
#define db long double
#define Pii pair<int,int>
#define fi first
#define se second
#define inline
#define f(x,y) fixed<<setprecision(y)<<x
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,rp,stdin),p1==p2)?EOF:*p1++)

#define mi ((L+R)>>1)
#define idl (id<<1)
#define idr (id<<1|1)

using namespace std;
const int N=2e5+10;
const int rp=1e6+10;

int n,q,cnt,pos[N]; Pii la[N*30];
vector<Pii> vt[N<<2];
struct node{int l,r,minl,maxr;}tr[N<<2];
struct ask{int l,r,t;}a[N];
char buf[rp],*p1=buf,*p2=buf;

inline int read()
{
    int x=0,f=1; char c=0;
    while(!isdigit(c)) {if(c=='-') f=-1; c=gc();}
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=gc();
    return x*f;
}

inline char read_ch()
{
    char c=0;
    while((!isalpha(c))&&(!isdigit(c))) c=gc();
    return c;
}

inline void build(int id,int L,int R)
{
    tr[id]={L,R,(int)2e9,(int)-2e9}; if(L==R) {pos[L]=id; return;}
    build(idl,L,mi); build(idr,mi+1,R);
}

inline void update_vt(int id,int L,int R,Pii as)
{
    if(tr[id].l>R||tr[id].r<L) return;
    if(L<=tr[id].l&&tr[id].r<=R) {vt[id].push_back(as); return;}//存修改
    update_vt(idl,L,R,as); update_vt(idr,L,R,as);
}

inline int get_minl(int id,int L,int R)
{
    if(tr[id].l>R||tr[id].r<L) return 2e9;
    if(L<=tr[id].l&&tr[id].r<=R) return tr[id].minl;
    return min(get_minl(idl,L,R),get_minl(idr,L,R));
}//询问 max minl

inline int get_maxr(int id,int L,int R)
{
    if(tr[id].l>R||tr[id].r<L) return -2e9;
    if(L<=tr[id].l&&tr[id].r<=R) return tr[id].maxr;
    return max(get_maxr(idl,L,R),get_maxr(idr,L,R));
}//询问 min maxr

inline void dfs(int id,int L,int R,int fl)
{
    if(!fl)//优化
    {
        for(int i=L;i<=min(R,q);++i) cout<<"No\n";
        return;//因为建在一起，所以要判右端点
    }
    int nw=0;
    for(;nw<vt[id].size();++nw)
    {
        Pii a=vt[id][nw]; int fa;
        if(get_minl(1,a.fi,a.se-1)<a.fi) fl=0;
        if(get_maxr(1,a.fi+1,a.se)>a.se) fl=0;//判断是否可以
        if(!fl) break;//优化*2
        fa=pos[a.se]; la[++cnt].fi=tr[fa].minl;//记录原来的值
        tr[fa].minl=min(tr[fa].minl,a.fi);
        while(fa) fa>>=1,tr[fa].minl=min(tr[fa<<1].minl,tr[fa<<1|1].minl);
        //反正是单点，就不用写 update 了
        fa=pos[a.fi]; la[cnt].se=tr[fa].maxr;
        tr[fa].maxr=max(tr[fa].maxr,a.se);
        while(fa) fa>>=1,tr[fa].maxr=max(tr[fa<<1].maxr,tr[fa<<1|1].maxr);
    }
    if(L!=R) dfs(idl,L,mi,fl),dfs(idr,mi+1,R,fl);
    else if(L<=q) cout<<(fl?"Yes":"No")<<"\n";
    //因为建在一起，所以要判右端点
    for(--nw;nw>=0;--nw)//倒着删
    {
        Pii a=vt[id][nw]; int fa;
        fa=pos[a.se]; tr[fa].minl=la[cnt].fi;//还原回去
        while(fa) fa>>=1,tr[fa].minl=min(tr[fa<<1].minl,tr[fa<<1|1].minl);
        fa=pos[a.fi]; tr[fa].maxr=la[cnt--].se;
        while(fa) fa>>=1,tr[fa].maxr=max(tr[fa<<1].maxr,tr[fa<<1|1].maxr);
    }
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>q; int op,l,r;
    for(int i=1;i<=q;++i)
    {
        cin>>op>>l;
        if(op==1) cin>>r,a[i]={l,r,q+1};//插入，离线下来
        else a[l].t=i-1;//给删除操作赋结束时间
    }
    build(1,1,max(n,q+1));//线段树分治
    for(int i=1;i<=q;++i)
        if(a[i].l&&i<=a[i].t)
            update_vt(1,i,a[i].t,{a[i].l,a[i].r});
    dfs(1,1,max(n,q+1),1);
    return 0;
}

//足りねー 足りねー キャッシュが足りねー
//今日も唱う How much