题解：UVA11402 Ahoy, Pirates!

Bobi2014 · 2025-10-04 18:15:32 · 题解

这是一道可癌的线段树题。

前置知识

• 线段树
• 谷歌翻译

思路

考虑使用 3 个懒标记，分别记录是否全 1、是否全 0、是否需要翻转。

pushdown 时先考虑 0 和 1 再考虑是否翻转，修改时如果改成 0 或 1，那么清除其他的 tag，把对应的 tag 改成 true。

接下来就是普通的线段树了，一组测试数据的时间复杂度为 O(Q \log n)。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1024010;
int Q,n,m,T;
string s,str;
namespace SegmentTree{
    struct node{
        int l,r,sum;
        bool tag_0,tag_1,tag_inv;
    } tri[N << 2];
    void build(int p,int l,int r){
        tri[p].l = l,tri[p].r = r;
        tri[p].tag_0 = tri[p].tag_1 = tri[p].tag_inv = false;
        if(l == r){
            tri[p].sum = str[l] - '0';
            return;
        }
        int mid = (l + r) >> 1;
        build(p << 1,l,mid);
        build(p << 1 | 1,mid + 1,r);
        tri[p].sum = tri[p << 1].sum + tri[p << 1 | 1].sum;
    }
    void pushdown(int p){
        if(tri[p].tag_0 == true){
            tri[p << 1].tag_0 = tri[p << 1 | 1].tag_0 = true;
            tri[p << 1].tag_1 = tri[p << 1 | 1].tag_1 = false;
            tri[p << 1].tag_inv = tri[p << 1 | 1].tag_inv = false;
            tri[p << 1].sum = 0;
            tri[p << 1 | 1].sum = 0;
            tri[p].tag_0 = false;
        }
        if(tri[p].tag_1 == true){
            tri[p << 1].tag_0 = tri[p << 1 | 1].tag_0 = false;
            tri[p << 1].tag_1 = tri[p << 1 | 1].tag_1 = true;
            tri[p << 1].tag_inv = tri[p << 1 | 1].tag_inv = false;
            tri[p << 1].sum = tri[p << 1].r - tri[p << 1].l + 1;
            tri[p << 1 | 1].sum = tri[p << 1 | 1].r - tri[p << 1 | 1].l + 1;
            tri[p].tag_1 = false;
        }
        if(tri[p].tag_inv == true){
            tri[p << 1].tag_inv ^= true;
            tri[p << 1 | 1].tag_inv ^= true;
            tri[p << 1].sum = (tri[p << 1].r - tri[p << 1].l + 1) - tri[p << 1].sum;
            tri[p << 1 | 1].sum = (tri[p << 1 | 1].r - tri[p << 1 | 1].l + 1) - tri[p << 1 | 1].sum;
            tri[p].tag_inv = false;
        }
    }
    void update_0(int p,int l,int r){
        if(tri[p].l >= l and tri[p].r <= r){
            tri[p].tag_0 = true;
            tri[p].tag_1 = false;
            tri[p].tag_inv = false;
            tri[p].sum = 0;
            return;
        }
        pushdown(p);
        int mid = (tri[p].l + tri[p].r) >> 1;
        if(l <= mid){
            update_0(p << 1,l,r);
        }
        if(r > mid){
            update_0(p << 1 | 1,l,r);
        }
        tri[p].sum = tri[p << 1].sum + tri[p << 1 | 1].sum;
    }
    void update_1(int p,int l,int r){
        if(tri[p].l >= l and tri[p].r <= r){
            tri[p].tag_0 = false;
            tri[p].tag_1 = true;
            tri[p].tag_inv = false;
            tri[p].sum = tri[p].r - tri[p].l + 1;
            return;
        }
        pushdown(p);
        int mid = (tri[p].l + tri[p].r) >> 1;
        if(l <= mid){
            update_1(p << 1,l,r);
        }
        if(r > mid){
            update_1(p << 1 | 1,l,r);
        }
        tri[p].sum = tri[p << 1].sum + tri[p << 1 | 1].sum;
    }
    void invert(int p,int l,int r){
        if(tri[p].l >= l and tri[p].r <= r){
            tri[p].tag_inv ^= true;
            tri[p].sum = (tri[p].r - tri[p].l + 1) - tri[p].sum;
            return;
        }
        pushdown(p);
        int mid = (tri[p].l + tri[p].r) >> 1;
        if(l <= mid){
            invert(p << 1,l,r);
        }
        if(r > mid){
            invert(p << 1 | 1,l,r);
        }
        tri[p].sum = tri[p << 1].sum + tri[p << 1 | 1].sum;
    }
    int query(int p,int l,int r){
        if(tri[p].l >= l and tri[p].r <= r){
            return tri[p].sum;
        }
        pushdown(p);
        int mid = (tri[p].l + tri[p].r) >> 1,ans = 0;
        if(l <= mid){
            ans += query(p << 1,l,r);
        }
        if(r > mid){
            ans += query(p << 1 | 1,l,r);
        }
        return ans;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> Q;
    for(int i = 1;i <= Q;i ++){
        cout << "Case " << i << ":\n";
        str = " ";
        cin >> n;
        while(n --){
            cin >> m >> s;
            while(m --){
                str += s;
            }
        }
        n = str.size() - 1;
        SegmentTree::build(1,1,n);
        cin >> T;
        m = 0;
        while(T --){
            char op;
            int l,r;
            cin >> op >> l >> r;
            l ++,r ++;
            if(op == 'F'){
                SegmentTree::update_1(1,l,r);
            }else if(op == 'E'){
                SegmentTree::update_0(1,l,r);
            }else if(op == 'I'){
                SegmentTree::invert(1,l,r);
            }else{
                cout << "Q" << ++m << ": " << SegmentTree::query(1,l,r) << "\n";
            }
        }
    }
    return 0;
}