P4891 序列

    • 202通过
    • 1.6K提交
  • 题目提供者 Created_equal1 管理员
  • 评测方式 云端评测
  • 标签 块状链表,块状数组,分块 枚举,暴力 线段树
  • 难度 省选/NOI-
  • 时空限制 5000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    本题数据已更新

    题目描述

    给定两个长度为 $n$ 的序列 $A$ 和 $B$,定义序列 $C_i=\max\limits_{j=1}^i A_j$。

    定义当前的价值是 $\prod\limits_{i=1}^n \min(B_i,C_i)$。

    现在有 $q$ 次操作,每次操作将会修改序列 $A$ 或者 $B$ 中的一个位置,将会把数字变大。现在请求出每次修改之后的价值。

    输入输出格式

    输入格式:

    第一行两个整数 $n,q$。

    第二行 $n$ 个整数表示 $A_i$。

    第三行 $n$ 个整数表示 $B_i$。

    接下来 $q$ 行,每行三个整数 $opt,x,y$,如果 $opt=0$ 表示对序列 A 操作,如果 $opt=1$ 则是对序列 $B$ 操作,把序列中第 $x$ 个元素变成 $y$,保证 $y$ 不小于原来的元素。

    输出格式:

    输出 $q$ 行,表示每次修改之后的价值。

    由于答案很大,请对 $10^9+7$ 取模后输出。

    输入输出样例

    输入样例#1: 复制
    3 1
    2 1 3
    1 2 3
    1 3 5
    
    输出样例#1: 复制
    6

    说明

    对于所有数据,满足 $1 \le n,q\le 10^5,0\le A_i,B_i,y \le 10^9$。

    对于 20% 的数据范围,满足 $1\le n,q\le 1000$

    对于另外 10% 的数据范围,满足 $opt=1$

    对于另外 20% 的数据范围,满足 $opt=0$

    对于 80% 的数据范围,满足 $n,q\le 50000$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。