第1题     统计数量 
查看测评数据信息

给一个长度是n的正整数数组,a[1],a[2],a[3],…a[n-1],a[n], 其中1<=a[i]<=1000。现在在数组a上进行m次 操作:

1.M x y z, 表示对a数组的闭区间[x,y]内所有a[i]的值分别加上z

2.A x y zz, 询问a数组闭区间[x,y]内有多少a[i]的值大于等于zz

输入格式

 

第一行两个整数n,m

接下来一行n个整数,表示a[1],a[2],a[3],…a[n-1],a[n]

接下来m个询问:

若第一个字母为M,则紧接着有三个数字x,y,z

若第一个字母为A,则紧接着有三个数字x,y,zz

部分数据 n<=1000, m<=1000

100%的数据 n<=1e6, m<=3000, 1<=z<=1000, 1<=zz<=1e9

 

输出格式

 

对每个A询问输出一行,仅含一个整数,表示闭区间[x,y]内大于等于zz的a[i]的个数。

 

输入/输出例子1

输入:

5 3

1 2 3 4 5

A 1 5 4

M 3 5 1

A 1 5 4

 

输出:

2

3

 

样例解释

    原题:
https://www.luogu.com.cn/problem/P2801     注意操作二 区间数大于等于某个数

int query(int L, int R, int d)
{
	int ans=0;
	for (int i=L; i<=R; i++)
		if (a[i]+add[pos[i]]>=d) ans++;
	return ans;
}

查找的时候可以考虑暴力,但这样肯定会超时,不妨考虑查找元素时用二分,

例如3,4,5,6,6,7,7,8,我要找>=5的数的个数

只要找第一个<5的数的位置,便可以得出>=5的数的个数

 

也是用分块思想,中间段二分,两边二分即可

int query(int L, int R, int k)
{
	int p=pos[L], q=pos[R], ans=0;
	if (p==q)
	{
		for (int i=L; i<=R; i++) 
			if (a[i]+add[p]>=k) ans++;
	}
	else
	{
		for (int i=L; i<=ed[p]; i++) 
			if (a[i]+add[p]>=k) ans++;
		for (int i=st[q]; i<=R; i++) 
			if (a[i]+add[q]>=k) ans++;
			
//中间段二分 for (int i=p+1; i<=q-1; i++) { int L=st[i], R=ed[i], res=0; while (L<=R) { int mid=L+R>>1; if (d[mid]+add[i]>=k) { R=mid-1;//因为要找<k的,尝试调整右端点 res=ed[i]-mid+1; //记得+1 } else L=mid+1; } ans+=res; } } return ans; }

 

但是要注意,这里原先的数组是无序的,所以要新开一个数组存着有序的数列

 

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e6+5;
int n, m, a[N], d[N], st[N], ed[N], pos[N], add[N];
char op;
int x, y, k;
void init()
{
	int block=sqrt(n);
	int t=n/block;
	
	if (n%block) t++;
	
	for (int i=1; i<=t; i++)
	{
		st[i]=(i-1)*block+1;
		ed[i]=i*block;
	}
    ed[t]=n;
	for (int i=1; i<=n; i++) d[i]=a[i], pos[i]=(i-1)/block+1;
	
	for (int i=1; i<=t; i++)
		sort(d+st[i], d+ed[i]+1);
}
void Add(int L, int R, int k)
{
	int p=pos[L], q=pos[R];
	if (p==q)
	{
		for (int i=L; i<=R; i++) a[i]+=k;
		for (int i=st[p]; i<=ed[p]; i++) d[i]=a[i];
		sort(d+st[p], d+ed[p]+1);
	}
	else
	{
		for (int i=p+1; i<=q-1; i++) add[i]+=k;
		
		for (int i=L; i<=ed[p]; i++) a[i]+=k;
		for (int i=st[p]; i<=ed[p]; i++) d[i]=a[i];
		sort(d+st[p], d+ed[p]+1);
		
		for (int i=st[q]; i<=R; i++) a[i]+=k;
		for (int i=st[q]; i<=ed[q]; i++) d[i]=a[i];
		sort(d+st[q], d+ed[q]+1);
	}
}
int query(int L, int R, int k)
{
	int p=pos[L], q=pos[R], ans=0;
	if (p==q)
	{
		for (int i=L; i<=R; i++) 
			if (a[i]+add[p]>=k) ans++;
	}
	else
	{
		for (int i=L; i<=ed[p]; i++) 
			if (a[i]+add[p]>=k) ans++;
		for (int i=st[q]; i<=R; i++) 
			if (a[i]+add[q]>=k) ans++;
			
		for (int i=p+1; i<=q-1; i++) 
		{
			int L=st[i], R=ed[i], res=0;
			while (L<=R)
			{
				int mid=L+R>>1;
				if (d[mid]+add[i]>=k) 
				{
					R=mid-1;
					res=ed[i]-mid+1;
				}
				else L=mid+1;
			}
			ans+=res;
		}
	}
	return ans; 
}
signed main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++) scanf("%lld", &a[i]);
	init();
	
	while (m--)
	{
		cin>>op;
		if (op=='M')
		{
			scanf("%d%d%lld", &x, &y, &k);
			Add(x, y, k);
		}
		else if (op=='A')
		{
			scanf("%d%d%lld", &x, &y, &k);
			printf("%lld\n", query(x, y, k));
		}
	}
	return 0;
}

  

声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。