树状数组求助
查看原帖
树状数组求助
399116
LYqwq楼主2022/1/30 21:57
#include <iostream>
using namespace std;
const int N=1e5+5;
int n,m,a,b,op,l,r,k,d,p;

inline int read(){
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-') flag=0;ch=getchar();}
	while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+ch-'0',ch=getchar();
	if(flag) return X;
	return ~(X-1);
}

inline void write(int X){
	if(X<0) putchar('-'),X=~(X-1);
	int s[20],top=0;
	while(X) s[++top]=X%10,X/=10;
	if(!top) s[++top]=0;
	while(top) putchar(s[top--]+'0');
	puts("");
}

template<class T>
class BIT{
	public:
		BIT(){}
		BIT(int _n){
			n=_n;
			for(int i=1; i<=n; i++){
				ca[i]=cb[i]=0;
			}
		}
		void add(int x,T v){
			int i=x-1;
			while(x<=n){
				ca[x]+=v;
				cb[x]+=v*i;
				x+=lowbit(x);
			}
		}
		T sum(T x){
			T res=0,i=x;
			while(x>=1){
				res+=i*ca[x]-cb[x];
				x-=lowbit(x);
			}
			return res;
		}
		void invadd(int l,int r,T v){ //  区间加操作
			this->add(l,v);
			this->add(r+1,-v);
		}
	private:
		T ca[N],cb[N],n;
		inline T lowbit(T x){
			return x&-x;
		}
};

int main(){
    n=read(),m=read();
	BIT<int> bit(n);
    for(int i=1; i<=n; i++){
		b=read();
		bit.add(i,b-a);
		a=b;
	}
    while(m--){
        op=read();
        if(op==1){
            l=read(),r=read(),k=read(),d=read();
			bit.invadd(l,l,k);
			if(l!=r) bit.invadd(l+1,r,d);
			if(r<n) bit.invadd(r+1,r+1,-k-d*(r-l));
        }else{
			p=read();
			write(bit.sum(p));
		}
    }
    return 0;
}

rt,区间改查,按题解里线段树操作方式,样例都过不了QwQ

2022/1/30 21:57
加载中...