顾 z

你没有发现两个字里的blog都不一样嘛 qwq

题目描述-->p3948 数据结构

分析

其实这题完全没有分析的 qwq.

只是因为写了差分数组相关知识,所以顺便写一下题解 qwq.

对于前面几种操作,我们无法确定A和Q哪个先出现.

出题人先给你一个Q再给你个A,再给你个Q,再给你个A,\(\dots\) 这就搞得很无奈啊.

因此,对于前面的询问操作我们可以暴力去求.

而对于后面的操作,我们可以通过差分数组预处理出来一个\(sum\)数组来\(O(1)\)输出\(ans\)

如果不了解差分的话,可以来这里看看 qwq

-----------------代码----------------

#include<bits/stdc++.h>

#define IL inline

#define int long long

#define R register

using namespace std;

IL void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(s>'9' or s<'0'){if(s=='-')f=-1;s=getchar();}

	while(s>='0' and s<='9'){x=x*10+s-'0';s=getchar();}

	x*=f;

}

char op;

int b[80008],n,m,mod,mnn,mxx,Final,sum[80008];

main()

{

	in(n),in(m),in(mod),in(mnn),in(mxx);

	for(R int  i=1,l,r,x;i<=m;i++)

	{

		R char op;

		cin>>op;

		in(l),in(r);

		switch(op)

		{

			case 'A':in(x);b[l]+=x;b[r+1]-=x;break;

			case 'Q':

				{

					R int  ans=0,now=0;

            		for(R int  i=1;i<=r;i++)

					{

                		now+=b[i];

                		if(i>=l  and (now*i)%mod>=mnn and (now*i)%mod<=mxx)ans++;

            		}

            		printf("%lld\n",ans);

            		break;

				}

		}

	}

	R int now=0;

	for(R int i=1;i<=n;i++)

	{

		now+=b[i];

		if((now*i)%mod>=mnn and (now*i)%mod<=mxx )sum[i]=sum[i-1]+1;

		else sum[i]=sum[i-1];

	}

	in(Final);

	for(R int l,r;Final;Final--)

	{

		in(l),in(r);

		printf("%lld\n",sum[r]-sum[l-1]);

	}

}

巴特西

差分【p3948】数据结构

顾 z

分析

最新文章

热门文章

巴特西

差分【p3948】 数据结构

顾z

分析

最新文章

热门文章

差分【p3948】数据结构

顾 z