背景
乌龟仙人又来为难高皓光了,为了避免成为法尸,请你完成下面这道题。
题目描述
给出一个长度为 n 的 01 串(只包含 0,1 的字符串),再给出 m 个互不相交的区间 [li,ri]。形式化地,对于所有 1 到 n 的整数,其至多被包含在一个区间中。
你可以进行若干次操作,每次操作可以任意选择一个区间 [L,R],将区间 [L,R] 内的所有 0 都变成 1,同时所有 1 都变成 0。
求让所有给定的区间中,每一个区间内 0,1 数量都相同的最少操作次数。无解输出 -1。
输入格式
第一行两个整数 n,m。
第二行一个长度为 n 的 01 串。
接下来 m 行,每行两个整数 li,ri,表示一个区间。保证这些区间互不相交。
输出格式
一行一个整数表示最小的操作次数,或者 -1 表示无解。
4 1
1011
1 4
1
提示
样例 #1 解释
操作区间 [3,3],该串将变为 1001。此时区间 [1,4] 中恰有两个 0,1,所以符合题目要求。可以证明这是最少的操作次数。
数据范围
对于 100% 的数据,1≤m≤n≤2×106。保证 m 个区间互不相交。
| 测试点 |
n≤ |
m≤ |
| 1∼2 |
10 |
n |
| 3∼4 |
500 |
| 5∼6 |
2×106 |
1 |
| 7∼10 |
n |