Fast Matrix Operations wu-kan

题目链接 对蓝书上的懒标记进行加强,将对区间的操作改成区间线性变换,那么区间修改就是区间先乘 0 在修改,区间加就是区间先乘 1 再加。这样敲反而简单很多。

update: 更新了线段树模板。新的模板省去了 build 操作。

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const int NPOS = -1;
struct SegmentTree
{
	struct Val
	{
		int l, r;
		ll min, max, sum;
		Val(int l, int r) : l(l), r(r), min(0), max(0), sum(0) {}
		Val(const Val &lc, const Val &rc) : l(lc.l), r(rc.r), min(std::min(lc.min, rc.min)), max(std::max(lc.max, rc.max)), sum(lc.sum + rc.sum) {}
		void upd(ll mul, ll add) { min = min * mul + add, max = max * mul + add, sum = sum * mul + add * (r - l + 1); }
	};
	struct Node : Val
	{
		int lc, rc;
		ll mul, add;
		Node(Val v) : Val(v), lc(NPOS), rc(NPOS), mul(1), add(0) {}
	};
	vector<Node> v;
	SegmentTree(int l, int r) : v{Val(l, r)} { v.reserve(r - l + 9 << 1); }
	void down(int rt)
	{
		int m = (v[rt].l + v[rt].r) / 2;
		if (v[rt].lc == NPOS)
			v[rt].lc = v.size(), v.push_back(Val(v[rt].l, m));
		if (v[rt].rc == NPOS)
			v[rt].rc = v.size(), v.push_back(Val(m + 1, v[rt].r));
		upd(v[v[rt].lc].l, v[v[rt].lc].r, v[rt].mul, v[rt].add, v[rt].lc);
		upd(v[v[rt].rc].l, v[v[rt].rc].r, v[rt].mul, v[rt].add, v[rt].rc);
		v[rt].mul = 1;
		v[rt].add = 0;
	}
	void upd(int l, int r, ll mul, ll add, int rt = 0)
	{
		if (l <= v[rt].l && v[rt].r <= r)
			return v[rt].mul *= mul, v[rt].add = v[rt].add * mul + add, v[rt].upd(mul, add);
		down(rt);
		if (r <= v[v[rt].lc].r)
			upd(l, r, mul, add, v[rt].lc);
		else if (l >= v[v[rt].rc].l)
			upd(l, r, mul, add, v[rt].rc);
		else
			upd(l, v[v[rt].lc].r, mul, add, v[rt].lc), upd(v[v[rt].rc].l, r, mul, add, v[rt].rc);
		dynamic_cast<Val &>(v[rt]) = Val(v[v[rt].lc], v[v[rt].rc]);
	}
	Val ask(int l, int r, int rt = 0)
	{
		if (l <= v[rt].l && v[rt].r <= r)
			return v[rt];
		down(rt);
		if (r <= v[v[rt].lc].r)
			return ask(l, r, v[rt].lc);
		if (l >= v[v[rt].rc].l)
			return ask(l, r, v[rt].rc);
		return Val(ask(l, v[v[rt].lc].r, v[rt].lc), ask(v[v[rt].rc].l, r, v[rt].rc));
	}
};
int main()
{
	for (int r, c, m, o, b, e, l; ~scanf("%d%d%d", &r, &c, &m);)
		for (vector<SegmentTree> Tree(r, {1, c}); m--;)
		{
			scanf("%d%d%d%d%d", &o, &b, &l, &e, &r);
			if (o == 3)
			{
				SegmentTree::Val ans(l, r);
				for (ans.min = 1e9, --b; b < e; ++b)
					ans = SegmentTree::Val(ans, Tree[b].ask(l, r));
				printf("%d %d %d\n", ans.sum, ans.min, ans.max);
			}
			else
				for (scanf("%d", &c), --b; b < e; ++b)
					Tree[b].upd(l, r, o == 1, c);
		}
}

原:目测是全网最短解法(Vjudge 上 Length1705,比第二名少了 312,同时性能也比较强)。

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct SegmentTree
{
	struct Node
	{
		int l,r;
		ll mul,add,min,max,sum;
		void set(ll m,ll a)
		{
			mul*=m,add=add*m+a,min=min*m+a,max=max*m+a,sum=sum*m+a*(r-l+1);
		}
		void up(const Node &lc,const Node &rc)
		{
			min=std::min(lc.min,rc.min);
			max=std::max(lc.max,rc.max);
			sum=lc.sum+rc.sum;
		}
		void down(Node &lc,Node &rc)
		{
			lc.set(mul,add),rc.set(mul,add),mul=1,add=0;
		}
	};
	vector<Node> v;
	SegmentTree(int N):v(N<<2)
	{
		build(1,N);
	}
	void build(int l,int r,int rt=1)
	{
		v[rt]= {l,r};
		if(l>=r)return;
		int m=l+r>>1;
		build(l,m,rt<<1),build(m+1,r,rt<<1|1),v[rt].up(v[rt<<1],v[rt<<1|1]);
	}
	void set(int l,int r,ll mul,ll add,int rt=1)
	{
		if(l<=v[rt].l&&v[rt].r<=r)return v[rt].set(mul,add);
		v[rt].down(v[rt<<1],v[rt<<1|1]);
		int m=v[rt].l+v[rt].r>>1;
		if(m>=r)set(l,r,mul,add,rt<<1);
		else if(m<l)set(l,r,mul,add,rt<<1|1);
		else set(l,m,mul,add,rt<<1),set(m+1,r,mul,add,rt<<1|1);
		v[rt].up(v[rt<<1],v[rt<<1|1]);
	}
	Node ask(int l,int r,int rt=1)
	{
		if(l<=v[rt].l&&v[rt].r<=r)return v[rt];
		v[rt].down(v[rt<<1],v[rt<<1|1]);
		int m=v[rt].l+v[rt].r>>1;
		if(m>=r)return ask(l,r,rt<<1);
		if(m<l)return ask(l,r,rt<<1|1);
		return v[0].up(ask(l,m,rt<<1),ask(m+1,r,rt<<1|1)),v[0];
	}
};
int main()
{
	for(int r,c,m,o,b,e,l; ~scanf("%d%d%d",&r,&c,&m);)
		for(vector<SegmentTree> tree(r,c); m--;)
		{
			scanf("%d%d%d%d%d",&o,&b,&l,&e,&r);
			if(o==3)
			{
				SegmentTree::Node ans;
				for(ans.min=1e9,ans.max=ans.sum=0,--b; b<e; ++b)
					ans.up(ans,tree[b].ask(l,r));
				printf("%d %d %d\n",ans.sum,ans.min,ans.max);
			}
			else for(scanf("%d",&c),--b; b<e; ++b)
					tree[b].set(l,r,o==1,c);
		}
}