[娱乐向] ABC 381 E 莫队做法

· · 个人记录

极其抽象，开始就想偏了，没有瞪出来咋做所以我用了莫队

记sum1_i表示前i个数中1出现的次数，sum2_i同理

对于一个询问[l,r]，设中间某个斜杠的位置为i

那么它的答案就是min(sum1_{i-1}-sum1_{l-1},sum2_r-sum2_i)

我瞪了30分钟，没啥发现

所以直接暴力拆开

如果左边小

sum1_{i-1}-sum1_{l-1}\leq sum2_r-sum2_i

移项过后是：

sum1_{i-1}+sum2_i\leq sum2_r+sum1_{l-1}

发现对于询问来说右边是常量

第二种情况同理

所以对于一个询问，我们分别可以维护两颗线段树

存储的下标都是sum1_i+sum2_i，对于每个这种下标，按照式子，维护sum1_{i-1}和-sum2_i的最大值

按照式子，分别在线段树中找到下标分别大于和小于sum1_{l-1}+sum2_r的最大值

两者取max即可

然后发现n\leq 1e5

可以O(n\sqrt n\log n) 草过去

然后把它搞成莫队就可以了

有sum1_i+sum2_i=sum1_j+sum2_j的情况，删除的时候拿个set判一下就行了

细节巨多，在90多分钟的时候才过，没时间看F了

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1e5+99;
int n, Q, maxn;
int c[N];
long long sum;
int cnt[N];
char str[N];
long long ans1[N], ans2[N];
struct query {
    int l, r, id;

    bool operator<(const query &x) const {
        if (l / maxn != x.l / maxn) return l < x.l;
        return (l / maxn) & 1 ? r < x.r : r > x.r;
    }
} a[N];
int sum1[N],sum2[N];
struct BIT1 {
    int tree[4*N];
    void build(int bh,int l,int r) {
        if(l==r) {
            tree[bh]=1e8;
        } else {
            int mid=(l+r)/2;
            build(bh*2,l,mid),build(bh*2+1,mid+1,r);
            tree[bh]=min(tree[bh*2],tree[bh*2+1]);
        }
    }
    void update(int bh,int l,int r,int x,int y) {
        if(l==r) {
            tree[bh]=y;
        } else {
            int mid=(l+r)/2;
            if(x<=mid) update(bh*2,l,mid,x,y);
            else update(bh*2+1,mid+1,r,x,y);
            tree[bh]=min(tree[bh*2],tree[bh*2+1]);
        }
    }
    int query(int bh,int l,int r,int L,int R) {
        if(L<=l&&r<=R) {
            return tree[bh];
        } else {
            int mid=(l+r)/2,oo=1e8;
            if(L<=mid) oo=min(oo,query(bh*2,l,mid,L,R));
            if(R>mid) oo=min(oo,query(bh*2+1,mid+1,r,L,R));
            return oo;
        }
    }
} T1;
struct BIT2 {
    int tree[4*N];
    void build(int bh,int l,int r) {
        if(l==r) {
            tree[bh]=0;
        } else {
            int mid=(l+r)/2;
            build(bh*2,l,mid),build(bh*2+1,mid+1,r);
            tree[bh]=max(tree[bh*2],tree[bh*2+1]);
        }
    }
    void update(int bh,int l,int r,int x,int y) {
        if(l==r) {
            tree[bh]=y;
        } else {
            int mid=(l+r)/2;
            if(x<=mid) update(bh*2,l,mid,x,y);
            else update(bh*2+1,mid+1,r,x,y);
            tree[bh]=max(tree[bh*2],tree[bh*2+1]);
        }
    }
    int query(int bh,int l,int r,int L,int R) {
        if(L<=l&&r<=R) {
            return tree[bh];
        } else {
            int mid=(l+r)/2,oo=0;
            if(L<=mid) oo=max(oo,query(bh*2,l,mid,L,R));
            if(R>mid) oo=max(oo,query(bh*2+1,mid+1,r,L,R));
            return oo;
        }
    }
} T2;
int gs=0;
#define pii pair<int,int>
set<pii>st1[N],st2[N];
void add(int i) {
    if(str[i]=='/') {
        gs++;
        st1[sum2[i]+sum1[i-1]].insert(make_pair(sum2[i],i));
        st2[sum2[i]+sum1[i-1]].insert(make_pair(-sum1[i-1],i));
        auto g1=st1[sum2[i]+sum1[i-1]].begin();
        int upd1=1e8,upd2=0;
        if(g1!=st1[sum2[i]+sum1[i-1]].end()) {
            upd1=g1->first;
        }
        auto g2=st2[sum2[i]+sum1[i-1]].begin();
        if(g2!=st2[sum2[i]+sum1[i-1]].end()) {
            upd2=g2->first;
            upd2=-upd2;
        }
        T1.update(1,0,n,sum2[i]+sum1[i-1],upd1);
        T2.update(1,0,n,sum2[i]+sum1[i-1],upd2);
    }
}
void del(int i) {
    if(str[i]=='/') {
        gs--;
        auto v1=st1[sum2[i]+sum1[i-1]].lower_bound(make_pair(sum2[i],i));
        st1[sum2[i]+sum1[i-1]].erase(v1);
        auto v2=st2[sum2[i]+sum1[i-1]].lower_bound(make_pair(-sum1[i],i));
        st2[sum2[i]+sum1[i-1]].erase(v2);
        auto g1=st1[sum2[i]+sum1[i-1]].begin();
        int upd1=1e8,upd2=0;
        if(g1!=st1[sum2[i]+sum1[i-1]].end()) {
            upd1=g1->first;
        }
        auto g2=st2[sum2[i]+sum1[i-1]].begin();
        if(g2!=st2[sum2[i]+sum1[i-1]].end()) {
            upd2=g2->first;
            upd2=-upd2;
        }
        T1.update(1,0,n,sum2[i]+sum1[i-1],upd1);
        T2.update(1,0,n,sum2[i]+sum1[i-1],upd2);
    }
}
int ans[1000008];
int main() {
    cin >> n >> Q;
    maxn = sqrt(n);
    scanf("%s",str+1);
    T1.build(1,0,n);
    T2.build(1,0,n);
    for(int i=1; i<=n; i++) {
        sum1[i]=sum1[i-1]+(str[i]=='1');
        sum2[i]=sum2[i-1]+(str[i]=='2');
    }
    for (int i = 0; i < Q; i++) cin >> a[i].l >> a[i].r, a[i].id = i;
    sort(a, a + Q);
    for (int i = 0, l = 1, r = 0; i < Q; i++) {
        while (l > a[i].l) add(--l);
        while (r < a[i].r) add(++r);
        while (l < a[i].l) del(l++);
        while (r > a[i].r) del(r--);
        ans[a[i].id]=0;
        if(gs) {
            ans[a[i].id]=max(ans[a[i].id],(sum2[a[i].r]-T1.query(1,0,n,sum1[a[i].l-1]+sum2[a[i].r],n))*2+1);
            ans[a[i].id]=max(ans[a[i].id],(T2.query(1,0,n,0,sum1[a[i].l-1]+sum2[a[i].r])-sum1[a[i].l-1])*2+1);
        }

    }
    for (int i = 0; i < Q; i++) {
        cout<<ans[i]<<"\n";
    }
    return 0;
}