mykKgO - Online C++0x Compiler & Debugging Tool

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second

const int maxN=1e3+5;
struct ez
{
	int sum, mn, mx;
};
int n, m, q, a[maxN][maxN];
ez segtree[4*maxN][4*maxN];

ez merge_segtree(ez l, ez r)
{
	ez res;
	res.sum=l.sum+r.sum;
	res.mn=min(l.mn, r.mn);
	res.mx=max(l.mx, r.mx);
	return res;
}

void build_y(int nodex, int lx, int rx, int nodey, int ly, int ry)
{
	if(ly==ry)
	{
		if(lx==rx) segtree[nodex][nodey].mn=segtree[nodex][nodey].sum=segtree[nodex][nodey].mx=a[lx][ly];
		else segtree[nodex][nodey]=merge_segtree(segtree[nodex*2][nodey],segtree[nodex*2+1][nodey]);
	}
	else
	{
		int midy=(ly+ry)>>1;
		build_y(nodex, lx, rx, nodey*2, ly, midy);
		build_y(nodex, lx, rx, nodey*2+1, midy+1, ry);
		segtree[nodex][nodey]=merge_segtree(segtree[nodex][nodey*2],segtree[nodex][nodey*2+1]);
	}
}

void build_x(int nodex, int lx, int rx)
{
	if(lx!=rx)
	{
		int midx=(lx+rx)>>1;
		build_x(nodex*2, lx, midx);
		build_x(nodex*2+1, midx+1, rx);
	}
	build_y(nodex, lx, rx, 1, 1, m);
}

void update_y(int nodex, int lx, int rx, int nodey, int ly, int ry, int x, int y, int val)
{
	if(ly==ry)
	{
		if(lx==rx) segtree[nodex][nodey].mn=segtree[nodex][nodey].sum=segtree[nodex][nodey].mx=val;
		else segtree[nodex][nodey]=merge_segtree(segtree[nodex*2][nodey],segtree[nodex*2+1][nodey]);
	}
	else
	{
		int midy=(ly+ry)>>1;
		if(y<=midy) update_y(nodex, lx, rx, nodey*2, ly, midy, x, y, val);
		else update_y(nodex, lx, rx, nodey*2+1, midy+1, ry, x, y, val);
		segtree[nodex][nodey]=merge_segtree(segtree[nodex][nodey*2],segtree[nodex][nodey*2+1]);
	}
}

void update_x(int nodex, int lx, int rx, int x, int y, int val)
{
	if(lx!=rx)
	{
		int midx=(lx+rx)>>1;
		if(x<=midx) update_x(nodex*2, lx, midx, x, y, val);
		else update_x(nodex*2+1, midx+1, rx, x, y, val);
	}
	update_y(nodex, lx, rx, 1, 1, m, x, y, val);
}

ez get_y(int nodex, int nodey, int tl_y, int tr_y, int ly, int ry)
{
	if(ly>ry) return {0,(int)1e18,(int)-1e18};
	if(tl_y==ly && tr_y==ry) return segtree[nodex][nodey];
	int tmid_y=(tl_y+tr_y)>>1;
	return merge_segtree(get_y(nodex, nodey*2, tl_y, tmid_y, ly, min(tmid_y, ry)),
	get_y(nodex, nodey*2+1, tmid_y+1, tr_y, max(ly, tmid_y+1), ry));
}

ez get_x(int nodex, int tlx, int trx, int lx, int rx, int ly, int ry)
{
	if(lx>rx) return {0,(int)1e18,(int)-1e18};
	if(lx==tlx && rx==trx) return get_y(nodex, 1, 1, m, ly, ry);
	int tmidx=(tlx+trx)>>1;
	return merge_segtree(get_x(nodex*2, tlx, tmidx, lx, min(rx,tmidx), ly, ry),
	get_x(nodex*2+1, tmidx+1, trx, max(lx, tmidx+1), rx, ly, ry));
}


void solve()
{
	build_x(1,1,n);
	while(q--)
	{
		int type; cin>>type;
		if(type==1)
		{
			int l,r,x; cin>>l>>r>>x;
			update_x(1,1,n,l,r,x);
		}
		else
		{
			int lx,rx,ly,ry; cin>>lx>>ly>>rx>>ry;
			if(type==2) cout<<get_x(1,1,n,lx,rx,ly,ry).sum<<'\n';
			if(type==3) cout<<get_x(1,1,n,lx,rx,ly,ry).mx<<'\n';
			if(type==4) cout<<get_x(1,1,n,lx,rx,ly,ry).mn<<'\n';
		}
	}
}

int32_t main()
{
	cin>>n>>m>>q;
	for(int i=1; i<=n; i+=1)
	{
		for(int j=1; j<=m; j+=1)
		{
			cin>>a[i][j];
		}
	}
	solve();
}