线段树求调
查看原帖
线段树求调
572193
witness_cy楼主2022/11/13 21:43
#include<iostream>
using namespace std;

int n,m,op,k,d,x,y,a[100005];

struct node{
	int l,r,val,tag1,tag2;
}seg[400005];

bool in(int L,int R,int nl,int nr){
	return L>=nl&&R<=nr;
}
bool out(int L,int R,int nl,int nr){
	return L>nr||R<nl;
}
long long f(int t1,int t2,int t3){
	return (((t3-1)*t2+t1)+t1)*t3/2;
}
void mtag(int u,int nl,int nr,int k1,int k2){
	seg[u].val+=f(k1,k2,nr-nl+1),seg[u].tag1+=k1,seg[u].tag2+=k2; 
}

void pushdown(int u,int nl,int nr){
	int mid=(nl+nr)/2;
	mtag(2*u,nl,mid,seg[u].tag1,seg[u].tag2);
	mtag(2*u+1,mid+1,nr,seg[u].tag1,seg[u].tag2);
	seg[u].tag1=seg[u].tag2=0;
}

void pushup(int u){
	seg[u].val=seg[2*u].val+seg[2*u+1].val;
}

void build(int u,int nl,int nr){
	
	seg[u].l=nl,seg[u].r=nr;
	if(nl==nr){seg[u].val=a[nl];return;}
	
	int mid=(nr+nl)/2;
	build(u*2,nl,mid),build(u*2+1,mid+1,nr);
	pushup(u);
}

int query(int u,int nl,int nr,int p){
	if(nl==nr) return seg[u].val;
    int mid=(nl+nr)/2;
    if(mid>=p) query(u*2,nl,mid,p);
    else query(u*2+1,mid+1,nr,p);
}

void update(int u,int nl,int nr,int L,int R,int K,int D){
	if(in(nl,nr,L,R)) mtag(u,nl,nr,K,D);
	else if(!out(nl,nr,L,R)){
		pushdown(u,nl,nr);
		int mid=(nl+nr)/2;
		update(u*2,nl,mid,L,R,K,D),update(u*2+1,mid+1,nr,L,R,K,D);
		pushup(u);
	} 
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	
	while(m--){
		cin>>op;
		if(op==1)
		    cin>>x>>y>>k>>d,update(1,1,n,x,y,k,d);
		else
		    cin>>x,cout<<query(1,1,n,x)<<endl;
	}
	return 0;
}
2022/11/13 21:43
加载中...