专栏文章

题解：P11754 [COCI 2024/2025 #5] 绘图 / Crtež

SSunburstFan
P11754题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipzjv7i
此快照首次捕获于
2025/12/03 20:31
3 个月前
此快照最后确认于
2025/12/03 20:31
3 个月前
查看原文

P11753 [COCI 2024/2025 #5] 绘图 / Crtež 题解

题目大意

给定一个长度为 nn 的序列，初始全为 00。每次给定区间 [l,r][l,r]，将区间内的 00 和 −1-1 互相翻转。每次操作后，求出能够以当前序列为基础，进行若干次填数操作得到的互不等价序列数量。

解题思路

对于每个位置，我们只关心它是 00 还是 −1-1。用线段树维护区间翻转操作。
n≤1018n \leq 10^{18}，不能直接建树，考虑离散化，每个 00 可以贡献 33 种状态（保持 00 or −1-1 or 正数）。
因此答案为 3cnt03^{cnt0}。
核心代码如下:
CPP
// 线段树维护区间内0和-1的个数
namespace SGT{
    int tree[N<<2][2],rev[N<<2]; // [0]存0的个数,[1]存-1的个数
    
    void pushup(int rt){
        tree[rt][0]=tree[rt<<1][0]+tree[rt<<1|1][0];
        tree[rt][1]=tree[rt<<1][1]+tree[rt<<1|1][1];
    }

    void upd(int rt){
        swap(tree[rt][0],tree[rt][1]); // 翻转0和-1
        rev[rt]^=1;
    }

    void modify(int rt,int l,int r,int L,int R){
        if(L<=l&&r<=R){
            upd(rt);
            return;
        }
        pushdown(rt);
        int md=(l+r)>>1;
        if(L<=md)modify(lson,L,R);
        if(R>md)modify(rson,L,R);
        pushup(rt);
    }
}

// 每次查询时计算3^cnt0
printf("%lld\n",qpow(3,SGT::tree[1][0]));
时间复杂度 O(qlog⁡q)O(q \log q)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...