P3948 数据结构

    • 1.2K通过
    • 4.3K提交
  • 题目提供者 APIO
  • 评测方式 云端评测
  • 标签 前缀和 差分 树状数组 概率论,统计 线段树
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    引言

    数据结构学的好,未来工作没烦恼。

    Edgration 是一个喜欢乱搞数据结构的蒟蒻(以下简称edt),有一天,他作死想去刁难一下dalao:

    edt想求一种数据结构,使得可以实现区间加,求出某一区间大于k的元素的个数

    dalao1:sb线段树

    dalao2:sb分块

    dalao3:sb平衡树

    edt: 不行,那就加上取模,求区间取膜mod后大于MIN小于MAX的元素个数

    dalao1:线段树&……¥#&……%……&*&%¥

    dalao2:sb分块 &%¥……%#¥#&……&*

    dalao3:*&……%&¥LCT维护SBT水题 &……%&……%

    edt:那不仅取模,每个数乘上数组下标再取模

    dalao:¥%¥¥&*(#¥% 叽里呱啦叽里呱啦

    edt:不行,在把取模的值丢到一棵树上,维护一棵仙人掌乘积方差的最小极差

    dalao:替罪羊树上用sb块状链表维护Toptree上的最小费用最大流和可持久化仙人掌,算出来在基尔霍夫矩阵中反演后跑一遍fft维护的插头DP就好了,给我三分钟轻松水过。。

    edt:mmp

    题目描述

    蒟蒻Edt把这个问题交给了你 ———— 一个精通数据结构的大犇,由于是第一题,这个题没那么难。。

    edt 现在对于题目进行了如下的简化:

    最开始的数组每个元素都是0

    给出$n$,$opt$,$mod$,$min$,$max$,$mod$在int范围内

    操作$A$,$Q$

    $A$: $L$,$R$,$X$ 表示把$[l,R]$这个区间加上$X$

    (数组的从L到R的每个元素都加上X)

    $Q$: $L$,$R$ 表示询问$[L,R]$这个区间中元素T满足 $min<=(T*i$%$ mod)<=max$ 的 T这样的数的个数(i是数组下标)

    (元素的值*数组下标%mod在min到max范围内)

    由于 edt 请来了一位非三次元的仓鼠,他帮你用延后了部分问题,将这些询问打入了混乱时空,你的询问操作不会超过1000次,不幸的是,对于延后的询问操作可能有很多次(小于1e7次),但是保证这些延后的询问操作之后不会再次有修改操作

    (就是在最后会有很多次询问,但不会进行修改)

    输入输出格式

    输入格式:

    给出n,opt,mod,min,max表示序列大小,操作次数,取膜,最小值,最大值

    下面opt行,给出

    $A$: $L$,$R$,$X$表示区间加,保证X在int范围内(<2147483647)

    $Q$:$L$,$R$表示区间查询满足条件的个数

    再给出一个$Final$值,表示后面有$Final$个询问

    下面$Final$行,给出

    $L$,$R$表示询问区间$[L,R]$表示询问$[L,R]$之间满足条件的个数

    输出格式:

    每行对于每个$Q$操作输出$Q$个数表示每次询问的值,

    下面$Final$行表示$Final$个询问的值

    输入输出样例

    输入样例#1: 复制
    3 2 4 0 2
    A 1 3 5
    Q 2 3 
    5
    1 3
    2 3
    1 1 
    2 2 
    3 3
    
    输出样例#1: 复制
    1
    2
    1
    1
    1
    0
    
    输入样例#2: 复制
    17 25 4098 310 2622
    A 10 16 657212040
    A 4 15 229489140
    A 1 2 -433239891
    A 3 12 532385784
    A 10 17 56266644
    A 8 10 10038874
    A 6 9 13084764
    A 4 5 -9206340
    Q 2 8
    A 2 4 -43223955
    A 6 9 31478706
    A 2 4 189818310
    A 2 8 179421180
    A 2 8 40354938
    Q 8 14
    A 3 6 57229575
    A 6 13 132795740
    A 2 17 14558022
    A 14 15 -552674185
    A 5 11 -1104138
    Q 2 12
    Q 1 14
    A 3 9 524902182
    A 8 12 114291440
    A 3 7 107531442
    1
    11 12
    
    输出样例#2: 复制
    3
    6
    7
    8
    2
    
    输入样例#3: 复制
    20 3 4317 1020 2232
    A 8 15 -434078222
    A 1 2 54988154
    A 13 19 81757858
    15
    7 11
    3 5
    3 9
    6 9
    9 13
    6 19
    1 20
    3 5
    3 10
    1 7
    2 14
    6 10
    2 3
    2 3
    10 12
    
    输出样例#3: 复制
    0
    0
    0
    0
    0
    2
    2
    0
    0
    0
    0
    0
    0
    0
    0
    

    说明

    样例说明

    给出样例1的解释:

    样例1中,$a$数组修改为$5$,$5$,$5$

    每个$a[i]*i$%$4$ 的值为$1$,$2$,$3$

    对于Final的询问

    询问$[1$,$3]$中大于等于0小于等于2的个数为2个

    剩下的询问类似

    题目说明

    注意

    1.关于负数取模问题,请以 c++ 的向0取整为标准,即如:

    [ $ -7 $%$ 3 = -1 $ ] [ $ 7 $%$ 3 = 1 $ ]

    2.一共会有50个测试点,每个点分值为2分。

    因为测试点数较多,请oier们自觉地不要故意多次提交来卡评测机,出题人 edt 在这里表示由衷的感谢

    数据范围

    如果你不能作对所有点,请尝试获得部分分,所有数据都是随机生成

    img

    标程展开

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