#Pbit19. 3.维护差数

    ID: 188 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及+/提高- 上传者: 标签>树状数组赛制:OI来源:wyfoj http://127.0.0.1

3.维护差数

3.维护差数

题目描述

给定一个长度为n的序列a,对于一个i,记它的贡献为ai+j−i<aj的个数,求贡献和。给定一个长度为n的序列a,对于一个i,记它的贡献为a_i+j-i<a_j的个数,求贡献和。

输入格式

第一行一个n,表示序列长度。第一行一个n,表示序列长度。

第二行n个数字,第i个数表示ai。第二行n个数字,第i个数表示a_i。

输出格式

输出一个值表示答案对12345取模后的值。

数据范围

(原站未提供,导入后需人工补齐)

样例

4
1 3 3 5
3

提示

对于40%的数据,有n<=1000。

对于100%的数据,有n<=200000。