33OJ
登录 注册

#P17539. 日月同错

    ID: 20111 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度普及+/提高− 上传者: 标签>贪心洛谷原创O2优化洛谷月赛

日月同错

背景

乌龟仙人又来为难高皓光了,为了避免成为法尸,请你完成下面这道题。

题目描述

给出一个长度为 nn 的 01\texttt{01} 串(只包含 0,1\texttt{0,1} 的字符串),再给出 mm 个互不相交的区间 [li,ri][l_i,r_i]。形式化地,对于所有 11 到 nn 的整数,其至多被包含在一个区间中。

你可以进行若干次操作,每次操作可以任意选择一个区间 [L,R][L,R],将区间 [L,R][L,R] 内的所有 0\texttt{0} 都变成 1\texttt{1},同时所有 1\texttt{1} 都变成 0\texttt{0}。

求让所有给定的区间中,每一个区间内 0,1\texttt{0},\texttt{1} 数量都相同的最少操作次数。无解输出 -1。

输入格式

第一行两个整数 n,mn,m。

第二行一个长度为 nn 的 01\texttt{01} 串。

接下来 mm 行,每行两个整数 li,ril_i,r_i,表示一个区间。保证这些区间互不相交。

输出格式

一行一个整数表示最小的操作次数,或者 -1 表示无解。

4 1
1011
1 4
1

提示

样例 #1 解释

操作区间 [3,3][3,3],该串将变为 1001\texttt{1001}。此时区间 [1,4][1,4] 中恰有两个 0,1\texttt{0},\texttt{1},所以符合题目要求。可以证明这是最少的操作次数。

数据范围

对于 100%100\% 的数据,1≤m≤n≤2×1061\le m\le n\le 2\times 10^6。保证 mm 个区间互不相交。

测试点 n≤n\le m≤m\le
1∼21\sim 2 1010 nn
3∼43\sim 4 500500
5∼65\sim 6 2×1062\times 10^6 11
7∼107\sim 10 nn