教主的魔法

灰太狼 2022-03-15 10:04 194阅读 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;
    }