#P11754. [COCI 2024/2025 #5] 绘图 / Crtež

    ID: 13124 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>线段树2025COCI(克罗地亚)Ad-hoc

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

题目背景

译自 COCI 2024/2025 #5 T4。2s,0.5G\texttt{2s,0.5G}。满分为 120120

题目描述

考虑一个长度为 nn 的整数序列 a1,,ana_1,\ldots,a_n,初始时 ai{1,0}a_i\in \{-1,0\}

你可以按照如下的步骤操作任意多次(包括零次):

  • 令这是第 xx 次操作。首先选择 ii 满足 1in1\le i\le n,且 ai=0a_i=0。(如果不存在,则无法继续操作)
  • 从如下的操作中二选一:
    • ai1a_i\gets -1,然后终止本次操作。
    • aixa_i\gets x。若 i2i\ge 2ai1=0a_{i-1}=0,令 ii1i\gets i-1,然后重新开始二选一(注意,若下一次二选一中选择令 ai1xa_{i-1}\gets x,则有 ai1=aia_{i-1}=a_i)。

操作完后会得到若干个结果序列 aa

我们称两个序列 a,ba,b 等价,当且仅当,能够重标号 aa 序列中 >0>0 的元素,使得重标号后这两个序列相等。

例如,[1,1,1,5,1,0][1,1,-1,5,1,0][2,2,1,6,2,0][2,2,-1,6,2,0] 等价。

更为精确地说,如果能构造一个双射 f:{1,0,}{1,0,}f: \{-1,0,\ldots\}\to \{-1,0,\ldots\},满足:

  • f(1)=1f(-1)=-1f(0)=0f(0)=0
  • 对于 i>0i\gt 0f(i)>0f(i)\gt 0
  • [f(a1),f(a2),,f(an)]=[b1,b2,,bn][f(a_1),f(a_2),\ldots,f(a_n)]=[b_1,b_2,\ldots,b_n]

那我们就说,aabb 等价。


一开始 ai=0a_i=0

接着有 qq 个操作,每个操作给定 l,rl,r,将 al,al+1,,ara_l,a_{l+1},\ldots,a_r 中的 00 同时替换成 1-11-1 同时替换成 00

每次操作后,求出以当前的 aa 序列为起始序列,操作得到的互不等价的结果序列的数量模 (109+7)(10^9+7) 后的结果。

输入格式

第一行,正整数 n,qn,q

接下来 qq 行,每行两个正整数 l,rl,r,描述一次操作。

输出格式

输出 qq 行,第 ii 行一个非负整数,表示第 ii 次操作得到的互不等价的序列数量模 (109+7)(10^9+7) 后的结果。

1 2
1 1
1 1
1
3
3 2
2 2
1 3
9
3
57 2
13 39
6 42
130653412
804077942

提示

样例解释

样例 11 解释:

第一次操作后,a=[1]a=[-1]。无法操作。互不等价的序列只有 [1][-1]

第二次操作后,a=[0]a=[0]。互不等价的序列有 [0],[1],[1][0],[1],[-1]

数据范围

对于 100%100\% 的数据,保证:

  • 1n10181\le n\le 10^{18}
  • 1q1051\le q\le 10^5
  • 1lrn1\le l\le r\le n
子任务编号 nn\le 特殊性质 得分
1 1 2×1032\times 10^3 A 20 20
2 2 10610^6 55 55
3 3 101810^{18} 45 45

特殊性质 A:q2×103q\le 2\times 10^3