文件详细信息

下载本文件

本文件的大小为 3677 字节。

#include<cstdio>
#include<cstring>
namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		bool flag=true;
		int ch=gc();
		num=0;
		while(ch<48||ch>57){
			if(ch=='-')flag=false;
			ch=gc();
		}
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
		flag||(num=-num);
	}
	template<typename T>
	void write(T a){
		static int ch[20],cnt=0;
		if(a<0)pc('-'),a=-a;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::write;
inline int min(const int a,const int b){
	return a<b?a:b;
}
const int maxn=250000,maxlog2n=17,maxq=50000,maxk=4,maxlim=1<<maxk;
int k,n,q,lim,a[maxk][maxn+1];
struct SegmentTree{
	int arr[maxn+1],rt[maxq+1][maxlim],tot,ql,qr,val;
	struct Seg{
		int l,r,tag,mn;
	}T[maxn*(maxlog2n+2)*maxlim/2+1];
	void pushup(const int u){
		T[u].mn=min(T[T[u].l].mn,T[T[u].r].mn)+T[u].tag;
	}
	void build(int&u,const int l,const int r){
		u=++tot;
		if(l==r)T[u].mn=arr[l];
		else{
			const int mid=(l+r)>>1;
			build(T[u].l,l,mid);
			build(T[u].r,mid+1,r);
			pushup(u);
		}
	}
	void modify_add(int&u1,const int u2,const int l,const int r){
		T[u1=++tot]=T[u2];
		if(ql<=l&&r<=qr){
			T[u1].tag+=val;
			T[u1].mn+=val;
		}else{
			const int mid=(l+r)>>1;
			if(ql<=mid)modify_add(T[u1].l,T[u2].l,l,mid);
			if(qr>mid)modify_add(T[u1].r,T[u2].r,mid+1,r);
			pushup(u1);
		}
	}
	void add(const int t,const int p,const int l,const int r,const int x){
		ql=l,qr=r,val=x;
		for(int S=0;S<lim;S++)
			if((S>>p)&1)
				modify_add(rt[t][S],rt[t][S],1,n);
	}
	void modify_cov(int&u1,const int u2,const int u3,const int l,const int r,const int val){
		u1=++tot;
		if(ql<=l&&r<=qr){
			T[u1].l=T[u3].l;
			T[u1].r=T[u3].r;
			T[u1].tag=T[u3].tag+val;
			T[u1].mn=T[u3].mn+val;
		}else{
			T[u1].tag=T[u2].tag;
			const int mid=(l+r)>>1;
			if(ql<=mid)modify_cov(T[u1].l,T[u2].l,T[u3].l,l,mid,val+T[u3].tag-T[u2].tag);
			else T[u1].l=T[u2].l;
			if(qr>mid)modify_cov(T[u1].r,T[u2].r,T[u3].r,mid+1,r,val+T[u3].tag-T[u2].tag);
			else T[u1].r=T[u2].r;
			pushup(u1);
		}
	}
	void cov(const int t,const int p,const int l,const int r,const int x){
		ql=l,qr=r;
		for(int S=0;S<lim;S++)
			if((S>>p)&1)
				modify_cov(rt[t][S],rt[t][S],rt[t][S^(1<<p)],1,n,x);
	}
	int query(const int u,const int l,const int r){
		if(ql<=l&&r<=qr)return T[u].mn;
		const int mid=(l+r)>>1;
		if(qr<=mid)return query(T[u].l,l,mid)+T[u].tag;
		if(ql>mid)return query(T[u].r,mid+1,r)+T[u].tag;
		return min(query(T[u].l,l,mid),query(T[u].r,mid+1,r))+T[u].tag;
	}
}T;
int main(){
	read(k),read(n),read(q),lim=1<<k;
	for(int p=0;p<k;p++)
		for(int i=1;i<=n;i++)
			read(a[p][i]);
	for(int S=0;S<lim;S++){
		memset(T.arr+1,0,sizeof(int)*n);
		for(int p=0;p<k;p++)
			if((S>>p)&1)
				for(int i=1;i<=n;i++)
					T.arr[i]+=a[p][i];
		T.build(T.rt[0][S],1,n);
	}
	for(int i=1,opt,t,p,l,r,x,y;i<=q;i++){
		read(opt),read(t);
		for(int S=0;S<lim;S++)T.rt[i][S]=T.rt[t][S];
		if(opt==1){
			read(p),read(l),read(r),read(x);
			T.add(i,p-1,l,r,x);
		}else if(opt==2){
			read(p),read(l),read(r),read(y);
			T.cov(i,p-1,l,r,y);
		}else{
			read(l),read(r);
			T.ql=l,T.qr=r,write(T.query(T.rt[i][lim-1],1,n)),pc('\n');
		}
	}
	return 0;
}