P3498 数据结构

题目链接：https://www.luogu.org/problem/P3948

题目大意：给你长度为n的数组，刚开始有m此询问，每次询问为两个操作，在l到r的数据之间加上x，或则是查询l到r之间元素的值乘以

下标后取模大于最小值，小于最大值的个数。最后有opt次询问，每次询问l到r之间符合上述条件的个数

解题思路：在前m次询问的过程中，既有查询又有修改，所以我们可以考虑用差分数组来解决这道题，但是在每次查询的时候并不能

直接修改数组中的值，这样会对后面的结果产生产生影响，所以在查询的时候用一个x记录当前查询到的值即可，在前m次查询完成之后吗，即可累加答案，用以数组sum[i]记录到i这个位置满足条件的数

的个数（前缀和的思想）

差分数组：差分数组记录的是第i个位置和i-1个位置之间的差值即，cnt[i]=a[i]-a[i-1],所以可以得到a[i]=cnt[i]+a[i-1]，这时候只需要遍历一遍即可求的

数组中的值

代码：

 

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+1;
long long num[maxn],sum[maxn];
long long minn,maxx,mode,n,t;
void add()
{
    long long l,r,x;
    cin>>l>>r>>x;
    num[l]+=x;
    num[r+1]-=x;
}
void count()
{
    long long l,r;
    long long x=0,ans=0;
    cin>>l>>r;
    for(int i=1;i<=r;i++)
    {
        //cout<<x<<endl;
        x+=num[i];
        if(((x*i)%mode>=minn)&&((x*i)%mode<=maxx&&i>=l)) ans++;
    }
    cout<<ans<<endl;
}
int main()
{
    cin>>n>>t>>mode>>minn>>maxx;
    while(t--)
    {
        char s[5];
        scanf("%s",s);
        if(s[0]=='A') add();
        else  count();    
    } 
    for(int i=1;i<=n;i++)
    {
        num[i]+=num[i-1];
        if(((num[i]*i)%mode>=minn)&&((num[i]*i)%mode<=maxx)) sum[i]++;
        sum[i]+=sum[i-1];
    }
    int opt;
    cin>>opt;
    while(opt--)
    {
        int l,r;
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]<<endl;
    }
    return 0;
}