差分数组

雨点打透心脏的1/2处 2024-04-18 09:43 49阅读 0赞

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int M=1e6+50;
    ll n,op,mi,mx,mod,fina,d[M],pre[M];
    int main(){
        scanf("%lld%lld%lld%lld%lld",&n,&op,&mod,&mi,&mx);
    
        char s[5];int x,y,c;
    
        for(int i=1;i<=op;i++){
            scanf("%s",s);
            scanf("%d%d",&x,&y);
            if(s[0]=='A'){
                scanf("%d",&c);
                d[x]+=c;
                d[y+1]-=c;
            }else{
                ll res=0,ans=0;
                for(long long i=1;i<=y;i++){
                    ans+=d[i];
                    if(i>=x&&mi<=(ans*i)%mod&&(ans*i)%mod<=mx)res++;
                }
                printf("%lld\n",res);
            }
        }
        scanf("%lld",&fina);
        long long now=0;
        for(long long i=1;i<=n;i++){
            now+=d[i];
            if(mi<=(now*i)%mod&&(now*i)%mod<=mx)pre[i]++;
            pre[i]+=pre[i-1];
        }
        while(fina--){
            scanf("%d%d",&x,&y);
            printf("%lld\n",pre[y]-pre[x-1]);
        }
        return 0;
    }

# P3948 数据结构 #

发表评论取消回复

表情：

评论列表（有 0 条评论，49人围观）

还没有评论，来说两句吧...

相关阅读

相关差分数组

include<bits/stdc++.h> using namespace std; define ll long long const ...

雨点打透心脏的1/2处/ 2024年04月18日 09:43/ 0 赞/ 50 阅读

相关差分数组的使用

一、问题现在，输入一个数组 `nums`，然后又要求给区间 `nums[2..6]` 全部加 1，再给 `nums[3..9]` 全部减 3，再给 `nums[0..4

绝地灬酷狼/ 2024年04月01日 16:30/ 0 赞/ 53 阅读

相关【算法】差分数组

目录 1.概述 2.代码实现 3.应用 > 本文参考： > [LABULADONG 的算法网站][LABULADONG] 1.概述（1）

骑猪看日落/ 2023年10月07日 22:37/ 0 赞/ 30 阅读

相关前缀和差分数组编程题集合

> 给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。 > > 示例 1： > > 输入：nums = \[1,1,1\

太过爱你忘了你带给我的痛/ 2023年09月25日 22:08/ 0 赞/ 38 阅读

相关差分数组+Tallest Cow

差分数组的定义和用途 1.定义：对于已知有n个元素的数列d，建立记录它每一项和前一项差值的差分数组f,f\[1\]=d\[1\]-0=d\[1\]。可以得到f\[i\

红太狼/ 2023年07月08日 02:49/ 0 赞/ 4 阅读

相关差分数组

文章目录差分数组 1.问题背景 2.解决方案 3.差分构造 4.应用差分数组 1.问题背景

清疚/ 2022年12月25日 06:57/ 0 赞/ 185 阅读

相关 php 平均/拆分数组array_chunk() 函数

<?php $cars=array("Volvo","BMW","Toyota","Honda","Mercedes","Opel"); print_r

傷城~/ 2022年10月22日 10:50/ 0 赞/ 190 阅读

相关算法 -- 对等差分数组

创建一个函数，接受两个或多个数组，返回所给数组的对等差分(symmetric difference) (△ or ⊕)数组. 给出两个集合 (如集合 A = \{1, 2,

╰+攻爆jí腚メ/ 2022年05月14日 09:52/ 0 赞/ 198 阅读

相关差分数组

先来看一道例题，给定一个长度为n(n≤107)的数列\{a1,a2,…,an\}，初始状态为0，m(m≤107)次操作，每次可以选择一个区间\[l,r\]，使下标在这个区间内的

小咪咪/ 2021年12月24日 15:23/ 0 赞/ 208 阅读

相关数据结构之差分数组

2019-06-25 推荐博客阅读：[https://www.sohu.com/a/271430685\_100201031][https_www.sohu.com_a_27

太过爱你忘了你带给我的痛/ 2021年12月15日 04:09/ 0 赞/ 210 阅读