求调(玄2关)
查看原帖
求调(玄2关)
1054528
Fa_Nanf1204楼主2024/5/15 16:42

#14WA

#include<bits/stdc++.h> 
#define N 1000005
#define ll long long
#define int long long
#define p2 (p<<1)
#define p3 ((p<<1)|1)
using namespace std;
int n,m;
ll a[N];
struct Tree{
	ll color,sum,add;
	bool flag;
}tree[N<<2];
void push_down(int p,int l,int mid,int r){
	tree[p2].sum+=tree[p].add*(mid-l+1);
	tree[p3].sum+=tree[p].add*(r-mid);
	tree[p2].add+=tree[p].add;
	tree[p3].add+=tree[p].add;
	tree[p].add=0;
}
void push_up(int p){
	tree[p].sum=tree[p2].sum+tree[p3].sum;
	if(tree[p2].flag==1 and tree[p3].flag==1 and tree[p2].color==tree[p3].color and tree[p2].color!=-1) tree[p].flag=1;
	else tree[p].flag=0;
	if(tree[p].flag==1) tree[p].color=tree[p2].color;
	else tree[p].color=-1; 
}
void build(int l,int r,int p){
	if(l==r){
		tree[p].flag=1;
		tree[p].color=l;
		return ;	
	} 
	int mid=l+r>>1;
	build(l,mid,p2);
	build(mid+1,r,p3); 
	push_up(p);
}
ll query(int l,int r,int li,int ri,int p){
	if(l==li and r==ri){
		return tree[p].sum;
	}
	ll ret=0;
	int mid=l+r>>1;
	push_down(p,l,mid,r);
	if(ri<=mid) ret=query(l,mid,li,ri,p2);
	else if(li>mid) ret=query(mid+1,r,li,ri,p3);
	else ret=query(l,mid,li,mid,p2)+query(mid+1,r,mid+1,ri,p3);
	push_up(p);
	return ret;
}
void tree_sqrt(int l,int r,int li,int ri,int v,int p){
	if(l==li and r==ri and tree[p].flag==1){
		tree[p].sum+=(r-l+1)*abs(tree[p].color-v);
		tree[p].add+=abs(tree[p].color-v);
		tree[p].color=v;
		return ;
	}
	if(li==ri and l==li and r==ri){
		tree[p].sum+=abs(tree[p].color-v);
		tree[p].add+=abs(tree[p].color-v);
		tree[p].color=v;
		tree[p].flag=1;
		return ;
	}
	int mid=l+r>>1;
	push_down(p,l,mid,r);
	if(ri<=mid){
		tree_sqrt(l,mid,li,ri,v,p2);
	}
	else if(li>mid){
		tree_sqrt(mid+1,r,li,ri,v,p3);
	} 
	else{
		tree_sqrt(l,mid,li,mid,v,p2);
		tree_sqrt(mid+1,r,mid+1,ri,v,p3);
	} 
	push_up(p);
}
signed main(){
	cin>>n>>m;
	build(1,n,1);
	while(m--){
		int op,l,r;
		ll k;
		cin>>op>>l>>r;
		if(op==1) cin>>k,tree_sqrt(1,n,l,r,k,1);
		else{
			ll x=query(1,n,l,r,1);
			cout<<x<<'\n';
		}	
	}
	return 0;
}
2024/5/15 16:42
加载中...