教主的魔法

灰太狼 2022-03-15 10:04 177阅读 0赞

代码没有测试 ：今天有点累，写一个思路吧。

数据存在两个数组内，首先进行分块，然后对第二个数组块内排序，接下来就是分块算法的常见操作了，对块内的个数查询是通过lower\_bound 来实现的。

贴代码：

#include<bits/stdc++.h>
    using namespace std;
    int n,m,d[1000005],pos[100005],l[100005],r[100005],t[1000005],a,b,c,ad[100006];
    void ask(int l1,int r1,int k){
    	int sum=0;
    	if(pos[l1]==pos[r1]){
    		for(int i=l1;i<=r1;i++)if(d[i]>=k)sum++;
    	}else{
    		int left=pos[l1]+1,right=pos[r1]-1,tem=0;
    		for(int i=left;i<=right;i++){
    			tem=(int)(lower_bound(t+l[i],t+r[i]+1,k-ad[i])-(t+l[i]));//看返回的位置 
    			if(tem==r[i]+1-l[i])continue;//返回的位置是end() 
    			sum+=r[i]+1-l[i]-tem;//返回的位置不是最后一个 
    		}
    		for(int i=l1;i<=r[pos[l1]];i++)if(d[i]>=k)sum++;
    		for(int i=l[pos[r1]];i<=r1;i++)if(d[i]>=k)sum++;
    	}
    	printf("%d\n",sum);
    }
    void update(int l1,int r1,int w){
    	if(pos[l1]==pos[r1]){
    		for(int i=l1;i<=r1;i++)d[i]+=w;
    	}else{
    		int left=pos[l1]+1,right=pos[r1]-1;
    		for(int i=left;i<=right;i++){
    			ad[i]+=w;
    		}
    		for(int i=l1;i<=r[pos[l1]];i++)d[i]+=w;
    		for(int i=l[pos[r1]];i<=r1;i++)d[i]+=w;
    	}
    }
    
    int main(){
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++){
    		scanf("%d",d+i);
    		t[i]=d[i];
    	}
    	int w=sqrt(n);
    	for(int i=1;i<=w;i++){
    		l[i]=(i-1)*sqrt(n)+1;
    		r[i]=i*sqrt(n);
    	}
    	if(r[w]<n){
    		w++;
    		l[w]=r[w-1]+1;
    		r[w]=n;
    	}
    	for(int i=1;i<=w;i++){
    		for(int j=l[i];j<=r[i];j++)
    			pos[j]=i;//分块成功
    		sort(t+l[i],t+r[i]+1);
    	}//初始化成功 
    	char x;
    	for(int i=1;i<=m;i++){
    		cin>>x>>a>>b>>c;
    		if(x=='A'){
    			ask(a,b,c);
    		}else{
    			update(a,b,c);
    		}
    	} 
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关菜鸟，大牛，教主的区别

对菜鸟来说题目有三种：会算法且能AC的，会算法但不能AC的，不会做的对大牛来说题目有两种：会做的，不会做的对教主来说题目有两种：能AC的，数据有错的

Myth丶恋晨/ 2022年08月09日 12:55/ 0 赞/ 150 阅读

相关【ACM】:菜鸟，大牛跟教主的区别

对菜鸟来说题目有三种：会算法且能AC的，会算法但不能AC的，不会做的对大牛来说题目有两种：会做的，不会做的对教主来说题目有两种：能AC的，数据有错的菜鸟提交WA了，

àì夳堔傛蜴生んèń/ 2022年07月21日 00:26/ 0 赞/ 142 阅读

相关楼教主

提问：天城，你是如何成长为这么好的程序员？天城：首先，你得数学很强。我从小就对数学有极大的兴趣，这为我打下良好的基础。其次，实践、实践、实践！过去十年里，我参加了100多个

墨蓝/ 2022年06月13日 12:47/ 0 赞/ 167 阅读

相关天气晴朗的魔法

> 这样阴沉的天气持续下去，我们不免担心起他的健康。 51nod魔法学校近日开展了主题为“天气晴朗”的魔法交流活动。 N名魔法师按阵法站好，之后选取N

不念不忘少年蓝@/ 2022年06月11日 06:41/ 0 赞/ 151 阅读

相关 Python的魔法方法

据说，Python 的对象天生拥有一些神奇的方法，它们总被双下划线所包围，他们是面向对象的 Python 的一切。他们是可以给你的类增加魔力的特殊方法，如果你的对象

我不是女神ヾ/ 2022年06月10日 02:40/ 0 赞/ 226 阅读

相关 Java的魔法数字

所谓魔法数值：是指在代码中直接出现的数值，只有在这个数值记述的那部分代码中才能明确了解其含义。　　魔法数值使代码的可读性大大下降。而且，如果同样的数值多次出现时

今天药忘吃喽~/ 2022年05月26日 02:19/ 0 赞/ 225 阅读

相关 setTimeout 的黑魔法

> setTimeout 的黑魔法原文：[http://web.jobbole.com/86022/][http_web.jobbole.com_86022] [http

ゝ一纸荒年。/ 2022年05月09日 13:20/ 0 赞/ 154 阅读

相关教主的魔法

代码没有测试：今天有点累，写一个思路吧。数据存在两个数组内，首先进行分块，然后对第二个数组块内排序，接下来就是分块算法的常见操作了，对块内的个数查询是通过lower\_b

灰太狼/ 2022年03月15日 10:04/ 0 赞/ 178 阅读

相关【luogu P2801】教主的魔法

传送门：[https://www.luogu.org/problemnew/show/P2801][https_www.luogu.org_problemnew_show_P2

左手的ㄟ右手/ 2021年12月09日 07:27/ 0 赞/ 277 阅读

相关 P2801 教主的魔法 (分块）

[题目传送][Link 1] 长度为\\(n(n\\le 1000000)\\)的数组，\\(q(q\\le 3000)\\) 次操作。修改操作即将某个区间的值增加某个不大于

喜欢ヅ旅行/ 2021年10月19日 04:48/ 0 赞/ 247 阅读