3.16 模拟赛 T2 记录

早上打的一场模拟赛，场上没想出来，下来看题解感觉还挺板的？

操作比较复杂，考虑线段树，把 \(n\) 变为 \(2^k\)，这样就可以和树状数组操作的区间 \([i-lowbit(i)+1,i]\) 一一对应，因为此时线段树的每一层的每一段区间都一定是 \(2\) 的整数倍。

维护两个标记一个是区间加标记，一个树状数组的标记。

然后修改的时候下来到一个包含的区间，可以提前预处理贡献打上标记。

再对于一个相交的区间，如果他是一个树状数组区间，就打一个区间加的标记，相当于把这一段的操作加上。

然后好像就没有了。唯一注意 \(n\) 要变成 \(2^k\)，所以空间不能开刚好。

`

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("no-stack-protector")

using namespace std;

typedef long long ll;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar();
    int x = 0,f=1;
    while(!isdigit(c)){
    	if(c=='-') f=-1;
    	c=getchar();
    }
    for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
    return x*f;
}
inline void write(ll x){
    if(x<0){
    	putchar('-');
		x=-x;
	}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}


const int maxn=3e6+5;
ll tr[maxn<<2],tag[maxn<<2],lz[maxn<<2];
ll val[maxn<<2];

inline int lowbit(int x){
	return x&(-x);
}
inline bool check(int l,int r){
	if(r-lowbit(r)+1==l) return 1;
	return 0;
}

void pushdown(int now,int l,int r){
	int mid=(l+r)>>1;
	if(tag[now]){
		tr[now<<1]+=tag[now]*val[now<<1];
		tr[now<<1|1]+=tag[now]*val[now<<1|1];
		if(check(l,mid)) lz[now<<1]+=tag[now];
		if(check(mid+1,r)) lz[now<<1|1]+=tag[now];
		// printf("%lld %lld %lld : %lld %lld\n",l,mid,r,tag[now]*val[now<<1],tag[now]*val[now<<1|1]);
		tag[now<<1]+=tag[now];
		tag[now<<1|1]+=tag[now];
		tag[now]=0;
	}
	if(lz[now]){
		tr[now<<1]+=1ll*(mid-l+1)*lz[now];
		tr[now<<1|1]+=1ll*(r-mid)*lz[now];
		lz[now<<1]+=lz[now];
		lz[now<<1|1]+=lz[now];
		lz[now]=0;
	}
}
void build(int now,int l,int r){
	tr[now]=tag[now]=lz[now]=val[now]=0;
	if(check(l,r)) val[now]=(r-l+1);
	if(l==r) return;
	int mid=(l+r)>>1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	val[now]+=val[now<<1]+val[now<<1|1];
	// printf("%lld %lld %lld : %lld\n",now,l,r,val[now]);
}
void pushup(int now){
	tr[now]=tr[now<<1]+tr[now<<1|1];
}
void update(int now,int l,int r,int ql,int qr,int x){
	if(ql<=l&&qr>=r){
		tr[now]+=1ll*x*val[now];
		tag[now]+=x;
		if(check(l,r)) lz[now]+=x;
		// printf("jj%d %lld : %lld\n",l,r,x*val[now]);
		return;
	}
	if(r<=qr&&check(l,r)){
		tr[now]+=1ll*(r-l+1)*x;
		lz[now]+=x;
		// printf("pp%d %lld : %lld\n",l,r,x*(r-l+1));
	}
	pushdown(now,l,r);
	int mid=(l+r)>>1;
	if(ql<=mid) update(now<<1,l,mid,ql,qr,x);
	if(qr>mid) update(now<<1|1,mid+1,r,ql,qr,x);
	pushup(now);
}
ll query(int now,int l,int r,int ql,int qr){
	if(ql<=l&&qr>=r) return tr[now];
	int mid=(l+r)>>1;
	ll res=0;
	pushdown(now,l,r);
	if(ql<=mid) res+=query(now<<1,l,mid,ql,qr);
	if(qr>mid) res+=query(now<<1|1,mid+1,r,ql,qr);
	return res;
}

int main(){
	
	int n=read(),q=read();
	
	int tn=__lg(n);
	if((1<<tn)<n) tn++;
	
	n=(1<<tn);
	
	// printf("kk%d\n",n);
	
	build(1,1,n);
	
	while(q--){
		int op=read(),l=read(),r=read(),x;
		if(op==1){
			x=read();
			update(1,1,n,l,r,x);
		}else{
			write(query(1,1,n,l,r));
			puts("");
		}
	}
	
	return 0;
}`