线段树全 WA 求调 /kk
查看原帖
线段树全 WA 求调 /kk
511609
无钩七不改名楼主2023/5/7 08:50

rt.

代码:

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

long long n,m,a[100005];

struct emm{
	long long ad1,ad2;
	int l,r;
}s[400005];

void build(int x,int l,int r){
	s[x].l=l;s[x].r=r;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(x*2,l,mid);
	build(x*2+1,mid+1,r);
	return;
}

void sp(int x){
	if(s[x].ad1||s[x].ad2){
		if(s[x*2].l==s[x*2].r)
			a[s[x*2].l]+=s[x].ad1;
		else{
			s[x*2].ad1+=s[x*2].ad1;
			s[x*2].ad2+=s[x].ad2;
		}
		if(s[x*2+1].l==s[x*2+1].r)
			a[s[x*2+1].l]+=s[x].ad1+s[x].ad2*(s[x*2].r-s[x].l+1);
		else{
			s[x*2+1].ad1+=s[x].ad1+s[x].ad2*(s[x*2].r-s[x].l+1);
			s[x*2].ad2+=s[x].ad2;
		}
		s[x].ad1=0;s[x].ad2=0;
	}
	return;
}

void change(int x,int l,int r,long long k,long long d){
	//cout<<x<<" "<<s[x].l<<" "<<s[x].r<<endl;
	if(l>s[x].r||r<s[x].l)return;
	if(s[x].l==s[x].r){
		a[s[x].l]+=k+d*(s[x].l-l);
		return;
	}
	if(l<=s[x].l&&r>=s[x].r){
		s[x].ad1+=k+d*(s[x].l-l);
		s[x].ad2+=d;
		return;
	}
	sp(x);
	change(x*2,l,r,k,d);
	change(x*2+1,l,r,k,d);
	return;
}

int find(int x,int p){
	if(p==s[x].l&&p==s[x].r)return a[s[x].l];
	sp(x);
	int mid=(s[x].r+s[x].l)>>1;
	if(p<=mid)return find(x*2,p);
	return find(x*2+1,p);
}

int main(){
	scanf("%lld%lld",&n,&m);
	for(int i(1);i<=n;i++)scanf("%lld",a+i);
	build(1,1,n);
	while(m--){
		int opt;
		scanf("%d",&opt);
		if(opt==1){
			int l,r;
			long long k,d;
			scanf("%d%d%lld%lld",&l,&r,&k,&d);
			change(1,l,r,k,d);
		}
		else{
			int p;
			scanf("%d",&p);
			printf("%lld\n",find(1,p));
		}
	}
	return 0;
} 

感觉哪里有问题,但是不知道哪里有问题

2023/5/7 08:50
加载中...