一口气全RE
查看原帖
一口气全RE
239458
cmach_socket楼主2021/8/8 11:45

本地编译器样例可以过,提交上去全部RE了???

暴力线段树,求大佬看看,代码如下:

#include<stdio.h>
#define MAXN 100005
using namespace std;
class node{
	public:
		int l,
			r,
			w;
}tree[MAXN*4+5];
int a[MAXN],n,m,ms,tmpl,tmpr,tmpx;
inline static void build(int k,int l,int r){
	tree[k].l=l,tree[k].r=r;
	if(l==r){
		tree[k].w=a[l];
		return ;
	}
	int mid=(l+r)>>1,lk=k<<1,rk=k<<1|1;
	build(lk,l,mid);
	build(rk,mid+1,r);
	tree[k].w=tree[lk].w+tree[rk].w;
}
inline static void change(int k,int x,int y){
	if(tree[k].l==tree[k].r){
		tree[k].w=y;
		return ;
	}
	int mid=(tree[k].l+tree[k].r)>>1,lk=k<<1,rk=k<<1|1;
	if(x<=mid)change(lk,x,y);
	else change(rk,x,y);
	tree[k].w=tree[lk].w+tree[rk].w;
}
inline static int q_ask(int k,int l,int r){
	if(tree[k].l>=l and tree[k].r<=r){
		return tree[k].w;
	}
	int mid=(tree[k].l+tree[k].r)>>1,lk=k<<1,rk=k<<1|1,ans=0;
	if(tree[k].l<=mid)ans+=q_ask(lk,l,r);
	if(tree[k].r>mid)ans+=q_ask(rk,l,r);
	return ans;
}
int main(){
	scanf("%d%d",&n,&m); 
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		scanf("%d",&ms);
		if(ms==1){
			scanf("%d%d%d",&tmpl,&tmpr,&tmpx);
			for(int i=tmpl;i<=tmpr;i++){
				if(a[i]%tmpx==0){
					a[i]/=tmpx; 
					change(1,i,a[i]);
				}
			}
		}
		else if(ms==2){
			scanf("%d%d",&tmpl,&tmpr);
			printf("%d\n",q_ask(1,tmpl,tmpr));
		}
	}
	return 0;
} 
2021/8/8 11:45
加载中...