P7204 题解

· · 题解

这题考试的时候想得很顺畅。

首先这题的复杂度肯定带 \log n 因为没学根号科技，然后看到删除，就想到了二分，而且前面有个二分。

这题的 n,q 都是 10^5，所以肯定需要预处理（很明显吧....），我们要看每个区间内删除后没有重复的字母，首先想到权值线段树，然后就放弃了（我没认真学），这里的“重复”可以想到链表，就只需要判断相邻的在区间内就行了，然后就是预处理那个最大的区间了。

这里我们将 l 和 r 预处理，用维护最大值和最小值的线段树分别维护左端点和右端点，注意懒惰标记的下传需要再维护“最大值的最小值”和“最小值的最大值”。

然后二分删到哪里，check() 函数我们需要小于等于 O(n\log n) 的复杂度，因为前面讲到了链表，这里就可以直接构造链表，然后枚举就行了 qwq。

这题为什么是灰呀？

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define ll long long
using namespace std;
inline ll max(const ll &x,const ll &y){return x>y?x:y;}
inline ll min(const ll &x,const ll &y){return x<y?x:y;}
void qr(ll &x){
    bool f=x=0;
    char c=getchar();
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x=f?~(x-1):x;
    return ;
}
struct node{ll l,r,Max,Min,maxtag,mintag,maxmin,minmax;}tr[400005];
char s[100005];
ll n,Q,l,r,L[100005],R[100005],pos[100005],a[100005],id[100005],lst[100005],nxt[100005];
bool flag[100005];
void pushup(ll p){
    tr[p].Max=max(tr[p<<1].Max,tr[p<<1|1].Max);
    tr[p].maxmin=min(tr[p<<1].maxmin,tr[p<<1|1].maxmin);
    tr[p].Min=min(tr[p<<1].Min,tr[p<<1|1].Min);
    tr[p].minmax=max(tr[p<<1].minmax,tr[p<<1|1].minmax);
}
void pushdown(ll p){
    if(~tr[p].mintag) {
        if(tr[p<<1].minmax>tr[p].mintag) tr[p<<1].Min=min(tr[p<<1].Min,tr[p].mintag),tr[p<<1].mintag=tr[p<<1].minmax=tr[p].mintag; 
        if(tr[p<<1|1].minmax>tr[p].mintag) tr[p<<1|1].Min=min(tr[p<<1|1].Min,tr[p].mintag),tr[p<<1|1].mintag=tr[p<<1|1].minmax=tr[p].mintag; 
        tr[p].mintag=-1; 
    }
    if(~tr[p].maxtag) {
        if(tr[p<<1].maxmin<tr[p].maxtag) tr[p<<1].Max=max(tr[p<<1].Max,tr[p].maxtag),tr[p<<1].maxtag=tr[p<<1].maxmin=tr[p].maxtag; 
        if(tr[p<<1|1].maxmin<tr[p].maxtag) tr[p<<1|1].Max=max(tr[p<<1|1].Max,tr[p].maxtag),tr[p<<1|1].maxtag=tr[p<<1|1].maxmin=tr[p].maxtag; 
        tr[p].maxtag=-1;
    }
}
void build(ll l,ll r,ll p){
    tr[p].l=l,tr[p].r=r,tr[p].maxtag=tr[p].mintag=-1;
    if(l==r){
        tr[p].Max=tr[p].maxmin=tr[p].Min=tr[p].minmax=l;
        return ;
    }
    ll mid=l+r>>1;
    build(l,mid,p<<1),build(mid+1,r,p<<1|1);
    pushup(p);
}
void update(ll l,ll r,ll Max,ll Min,ll p){
    if(l<=tr[p].l&&r>=tr[p].r){
        if(tr[p].maxmin<Max){
            tr[p].maxtag=tr[p].maxmin=Max;
            tr[p].Max=max(tr[p].Max,Max);
        }
        if(tr[p].minmax>Min){
            tr[p].mintag=tr[p].minmax=Min;
            tr[p].Min=min(tr[p].Min,Min);
        }
        return ;
    }
    pushdown(p);
    int mid=tr[p].l+tr[p].r>>1;
    if(l<=mid) update(l,r,Max,Min,p<<1);
    if(r>mid) update(l,r,Max,Min,p<<1|1);
    pushup(p);
}
ll askmin(ll x,ll p){
    if(tr[p].l==x&&tr[p].r==x) return tr[p].Min;
    pushdown(p);
    int mid=tr[p].l+tr[p].r>>1;
    if(x<=mid) return askmin(x,p<<1);
    else return askmin(x,p<<1|1);
}
ll askmax(ll x,ll p){
    if(tr[p].l==x&&tr[p].r==x) return tr[p].Max;
    pushdown(p);
    int mid=tr[p].l+tr[p].r>>1;
    if(x<=mid) return askmax(x,p<<1);
    else return askmax(x,p<<1|1);
}
bool check(ll x){
    for(int i=1;i<=x;i++) flag[pos[i]]=1;
    for(int i=0;i<26;i++) id[i]=0;
    for(int i=1;i<=n;i++) {
        if(!flag[i]) {
            lst[i]=id[a[i]];
            if(id[a[i]]) nxt[id[a[i]]]=i;
            id[a[i]]=i;
        }
    }
    for(int i=0;i<26;i++) if(id[i]) nxt[id[i]]=n+1;
    for(int i=1;i<=n;i++) {
        if(!flag[i]&&(L[i]<=lst[i]||R[i]>=nxt[i])) {
            for(int j=1;j<=x;j++) flag[pos[j]]=0;
            return 0;
        }
    }
    for(int i=1;i<=x;i++) flag[pos[i]]=0;
    return 1;
}
int main() {
    scanf("%s",s+1),n=strlen(s+1),build(1,n,1),qr(Q);
    for(int i=1;i<=n;i++) a[i]=s[i]-'a';
    for(int i=1;i<=Q;i++) qr(l),qr(r),update(l,r,r,l,1);
    for(int i=1;i<=n;i++) qr(pos[i]);
    for(int i=1;i<=n;i++) L[i]=askmin(i,1),R[i]=askmax(i,1););
    ll l=0,r=n,mid;
    while(r-l>1){
        mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    if(check(l)) printf("%lld",l);
    else printf("%lld",r);
    return 0;
}