TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P7708
  • 题目
  • P7708序列研究
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

    有两个 $01$ 序列 \(a_1,a_2,\cdots,a_n\)\(b_1,b_2,\cdots,b_n\) ,初始序列 \(\{a_i\}\) 全是 $0$ 。

    你有 \(m\) 种操作可以执行,第 \(i\) 种操作是将区间 \(a_{l_i}\)\(a_{r_i}\) 全部赋值为 $1$ 。

    你的目标是让 \(\{a_i\},\{b_i\}\) 两个序列尽可能相似,也就是对应项不相等的尽量少。求不相等的对应项最少有多少个。

    输入格式

    第一行一个整数 \(n\)

    第二行 \(n\) 个整数 \(b_i\)

    第三行一个整数 \(m\)

    接下来 \(m\) 行,每行两个整数 \(l_i,r_i\)

    输出格式

    输出一行一个整数答案。

    样例输入 1

    3
    1 0 1
    1
    1 3

    样例输出 1

    1

    样例输入 2

    3
    1 0 1
    2
    1 1
    3 3

    样例输出 2

    0

    样例输入 3

    3
    1 0 1
    2
    1 1
    2 3

    样例输出 3

    1

    样例输入 4

    5
    0 1 0 1 0
    1
    1 5

    样例输出 4

    2

    样例输入 5

    15
    1 1 0 0 0 0 0 0 1 0 1 1 1 0 0
    9
    4 10
    13 14
    1 7
    4 14
    9 11
    2 6
    7 8
    3 12
    7 13

    样例输出 5

    5

    样例输入 6

    10
    0 0 0 1 0 0 1 1 1 0
    7
    1 4
    2 5
    1 3
    6 7
    9 9
    1 5
    7 9

    样例输出 6

    1

    提示

    样例1解释

    \(\{b_i\}\) 序列为 \([1,0,1]\)
    如果不执行操作, \(\{a_i\}\) 序列为 \([0,0,0]\) ,有 $2$ 项不相等;
    执行操作之后, \(\{a_i\}\) 序列变成 \([1,1,1]\) ,有 $1$ 项不相等。

    数据范围

    对于全部测试数据, $1\leq n,m\leq 200\ 000$ , \(b_i\in\{0,1\}\) , $1\leq l_i\leq r_i\leq n$ ,没有重复的操作区间。