UVA11992,二维线段树求调,悬赏关注!!!
  • 板块题目总版
  • 楼主Ferdina_zcjb
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/7/9 10:18
  • 上次更新2023/11/3 10:57:11
查看原帖
UVA11992,二维线段树求调,悬赏关注!!!
797354
Ferdina_zcjb楼主2023/7/9 10:18
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000001
int r,c,m,mm,nn,ss;
struct node{
	int l,r,maxx,minn,sum,la1,la2;
}tree[21][N << 2];
void build(int k,int h,int L,int R);
void change1(int k,int h,int L,int R,int val);
void change2(int k,int h,int L,int R,int val);
void ask1(int k,int h,int L,int R);
//void ask2(int k,int h,int L,int R);
//void ask3(int k,int h,int L,int R);
void push_down(int h,int k);
int len(int h,int k){
	return tree[h][k].r - tree[h][k].l + 1;
}
void push_up(int h,int k){
	tree[h][k].sum = tree[h][k<<1].sum + tree[h][k<<1|1].sum;
	tree[h][k].maxx = max(tree[h][k<<1].maxx,tree[h][k<<1|1].maxx);
	tree[h][k].minn = min(tree[h][k<<1].minn,tree[h][k<<1|1].minn);
}
signed main(){
	while(cin >> r >> c >> m){
	for(int i = 1;i <= r;++i){
		build(1,i,1,c);
	}
	for(int i = 1;i <= m;++i){
		int op,x,y,xx,yy;
		cin >> op >> x >> y >> xx >> yy;
		if(op == 1 || op == 2){
			int v;
			cin >> v;
			if(op == 1){
				for(int j = x;j <= xx;++j){
					change1(1,j,y,yy,v);
				}
			}else{
				for(int j = x;j <= xx;++j){
					change2(1,j,y,yy,v);
				}
			}
		}else{
			int mmm = 0,nnn = 0x7fffffff,sss = 0;
			for(int j = x;j <= xx;++j){
				mm = 0,nn = 0x7fffffff,ss = 0;
				ask1(1,j,y,yy);
				sss += ss;
				//ask2(1,j,y,yy);
				mmm = max(mmm,mm);
				//ask3(1,j,y,yy);
				nnn = min(nn,nnn);
			}
			cout << sss << " " << nnn << " " << mmm << endl;
		}
	}
	}
}
void build(int k,int h,int L,int R){
	tree[h][k].l = L;
	tree[h][k].r = R;
	tree[h][k].maxx = 0;
	tree[h][k].minn = 0;
	tree[h][k].sum = 0;
	tree[h][k].la1 = 0;
	tree[h][k].la2 = -1;
	if(L == R)return ;
	int mid = (L+R) >> 1;
	build(k<<1,h,L,mid);
	build(k<<1|1,h,mid+1,R);
}
void change1(int k,int h,int L,int R,int val){
    if(L > tree[h][k].r || R < tree[h][k].l){
        return ;
    }
    if(L <= tree[h][k].l && R >= tree[h][k].r){
        tree[h][k].sum += len(h,k)*val;
        tree[h][k].maxx += val;
        tree[h][k].minn += val;
        tree[h][k].la1 += val;
        return ;
    }
    push_down(h,k);
    change1(k<<1,h,L,R,val);
    change2(k<<1|1,h,L,R,val);
    push_up(h,k);
}
void change2(int k,int h,int L,int R,int val){
    if(L > tree[h][k].r || R < tree[h][k].l){
        return ;
    }
    if(L <= tree[h][k].l && R >= tree[h][k].r){
        tree[h][k].sum = len(h,k)*val;
        tree[h][k].maxx = val;
        tree[h][k].minn = val;
        tree[h][k].la2 = val;
        tree[h][k].la1 = 0;
        return ;
    }
    push_down(h,k);
    change2(k<<1,h,L,R,val);
    change2(k<<1|1,h,L,R,val);
    push_up(h,k);
}
void ask1(int k,int h,int L,int R){
    if(L > tree[h][k].r || tree[h][k].l > R){
        return;
    }
    if(L <= tree[h][k].l && tree[h][k].r <= R){
        ss += tree[h][k].sum;
        nn = min(nn,tree[h][k].minn);
        mm = max(tree[h][k].maxx,mm);
        return ;
    }
    push_down(h,k);
    ask1(k<<1,h,L,R);
    ask1(k<<1|1,h,L,R);
}
void push_down(int h,int k){
    if(tree[h][k].la2 > -1){
        tree[h][k<<1].sum = len(h,k<<1)*tree[h][k].la2;
        tree[h][k<<1|1].sum = len(h,k<<1|1)*tree[h][k].la2;
        tree[h][k<<1].maxx = tree[h][k].la2;
        tree[h][k<<1|1].maxx = tree[h][k].la2;
        tree[h][k<<1].minn = tree[h][k].la2;
        tree[h][k<<1|1].minn = tree[h][k].la2;
        tree[h][k<<1].la2 = tree[h][k].la2;
        tree[h][k<<1|1].la2 = tree[h][k].la2;
        tree[h][k].la2 = -1;
    }
    if(tree[h][k].la1){
        tree[h][k<<1].sum += len(h,k<<1)*tree[h][k].la1;
        tree[h][k<<1|1].sum += len(h,k<<1|1)*tree[h][k].la1;
        tree[h][k<<1].maxx += tree[h][k].la1;
        tree[h][k<<1|1].maxx += tree[h][k].la1;
        tree[h][k<<1|1].minn += tree[h][k].la1;
        tree[h][k<<1].minn += tree[h][k].la1;
        tree[h][k<<1].la1 += tree[h][k].la1;
        tree[h][k<<1|1].la1 += tree[h][k].la1;
        tree[h][k].la1 = 0;
    }
}
2023/7/9 10:18
加载中...