题目描述

蒟蒻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次），但是保证这些延后的询问操作之后不会再次有修改操作

（就是在最后会有很多次询问，但不会进行修改）

戳

Solve

有点混乱，其实有用的话就这两句。
（数组的从L到R的每个元素都加上X），（元素的值*数组下标%mod在min到max范围内）
差分处理，对于前面的询问暴力处理。
而后面的询问用前缀和优化。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 80001
#define ll long long
using namespace std;
ll n,opt,mod,mint,maxt,final;
ll l,r,w;
ll a[N],sum[N];
int main()
{
	scanf("%lld%lld%lld%lld%lld",&n,&opt,&mod,&mint,&maxt);
	for(ll i=1;i<=opt;i++){
		char c;
		cin>>c;
		if(c=='A'){
			scanf("%lld%lld%lld",&l,&r,&w);
			a[l]+=w;
			a[r+1]-=w;
		}
		else{
			scanf("%lld%lld",&l,&r);
			ll now=0,ans=0;
			for(ll j=1;j<=r;j++){
				now+=a[j];
				if(j>=l){
					if((now*j)%mod>=mint&&(now*j)%mod<=maxt) ans++;
				}
			}
			printf("%lld\n",ans);
		}
	}
	for(ll i=1;i<=n;i++){
		a[i]+=a[i-1];
		sum[i]=sum[i-1];
		if((a[i]*i)%mod>=mint&&(a[i]*i)%mod<=maxt) sum[i]++;
	}
	scanf("%lld",&final);
	for(ll i=1;i<=final;i++){
		scanf("%lld%lld",&l,&r);
		printf("%lld\n",sum[r]-sum[l-1]);
	}
	return 0;
}