悬关求调
查看原帖
悬关求调
738882
OIer_dcy__AK_IOI楼主2024/12/14 15:01
#include<bits/stdc++.h>

using namespace std;

const int maxm=4e5+10;

int n,m;
struct Tree{
	int l,r;
	int tag,sum;
}tree[maxm];

void build(int root,int l,int r){
	tree[root].l=l;
	tree[root].r=r;
	if(l==r){
		tree[root].sum=0;
		tree[root].tag=0;
		return;
	}
	int mid=(tree[root].l+tree[root].r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;
}

void pushdown(int root){
	int l=tree[root].l;
	int r=tree[root].r;
	if(l!=r){
		tree[root<<1].tag+=tree[root].tag;
		tree[root<<1|1].tag+=tree[root].tag;
		tree[root<<1].sum+=tree[root].tag*(tree[root<<1].r-tree[root<<1].l+1)-tree[root<<1].sum;
		tree[root<<1|1].sum+=tree[root].tag*(tree[root<<1|1].r-tree[root<<1|1].l+1)-tree[root<<1|1].sum;
		tree[root].tag=0;
	}
}

void update(int root,int l,int r,int k){
	if(l<=tree[root].l&&r>=tree[root].r){
		tree[root].tag+=k;
		tree[root].sum+=k*(tree[root].r-tree[root].l+1)-tree[root].sum;
		return;
	}
	pushdown(root);
	int mid=(tree[root].l+tree[root].r)>>1;
	if(l<=mid) update(root<<1,l,r,k);
	if(r>mid) update(root<<1|1,l,r,k);
	tree[root].sum=tree[root<<1].sum+tree[root<<1|1].sum;
}

int query(int root,int l,int r){
	if(l<=tree[root].l&&r>=tree[root].r){
		return tree[root].sum;
	}
	pushdown(root);
	int mid=(tree[root].l+tree[root].r)>>1,res=0;
	if(l<=mid) res+=query(root<<1,l,r);
	if(r>mid) res+=query(root<<1|1,l,r);
	return res; 
}

int main(){
	scanf("%d%d",&n,&m);
	
	build(1,1,n);
	
	while(m--){
		int op;
		scanf("%d",&op);
		if(op==0){
			int x,y;
			scanf("%d%d",&x,&y);
			update(1,x,y,1);
		}
		if(op==1){
			int x,y;
			scanf("%d%d",&x,&y);
			printf("%d\n",query(1,x,y));
		}
	}
	return 0;
}
2024/12/14 15:01
加载中...