求赞,题解
2025-08-09 19:20:26
发布于:广东
2阅读
0回复
0点赞
#include <cstdio>
#include <cctype>
#include <cstring>
namespace quick {
#define tp template<typename Type>
namespace in {
inline char getc() {
static char buf[1<<21],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
inline int read(char *s) {
*s=getc();
while(isspace(*s)) {*s=getc();if(*s==EOF) return 0;}
while(!isspace(*s)&&*s!=EOF) {s++;*s=getc();}
*s='\0'; return 1;
}
tp inline int read(Type &x) {
x=0;bool k=false;char c=getc();
while(!isdigit(c)) {k|=(c=='-');c=getc();if(c==EOF) return 0;}
while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^48);c=getc();}
x*=(k?-1:1); return 1;
}
template <typename Type,typename... Args>
inline int read(Type &t,Args &...args) {
int res=0;
res+=read(t);res+=read(args...);
return res;
}
}
using in::read;
namespace out {
char buf[1<<21];int p1=-1;const int p2=(1<<21)-1;
inline void flush() {
fwrite(buf,1,p1+1,stdout);
p1=-1;
}
inline void putc(const char &c) {
if(p1==p2) flush();
buf[++p1]=c;
}
inline void write(char *s) {
while(*s!='\0') putc(*s),s++;
}
inline void write(const char *s) {
while(*s!='\0') putc(*s),s++;
}
tp inline void write(Type x) {
static char buf[30];int p=-1;
if(x<0) {putc('-');x=-x;}
if(x==0) putc('0');
else for(;x;x/=10) buf[++p]=x%10+48;
for(;p!=-1;p--) putc(buf[p]);
}
inline void write(const char &c) {putc(c);}
template <typename Type,typename... Args>
inline void write(Type t,Args ...args) {
write(t);write(args...);
}
}
using out::write;
using out::flush;
tp inline Type max(const Type &a,const Type &b) {
if(a<b) return b;
return a;
}
tp inline Type min(const Type &a,const Type &b) {
if(a<b) return a;
return b;
}
tp inline void swap(Type &a,Type &b) {
a^=b^=a^=b;
}
tp inline Type abs(const Type &a) {
return a>=0?a:-a;
}
#undef tp
}
using namespace quick;
const int maxn=1e5+10,inf=0x3f3f3f3f;
int n,m,val[6][maxn];
#define clr(x,y) memset(x,y,sizeof(x))
namespace SegmentTree {
struct Node {
int ll[6][6],rr[6][6],lr[6][6];
}st[maxn<<2];
Node operator + (const Node &lc,const Node &rc) {
static Node res;
static int lm[6][6],rm[6][6];
clr(lm,0x3f);clr(rm,0x3f);
for(int i(0);i<6;i++)
for(int j(0);j<6;j++)
for(int k(0);k<6;k++) {
lm[i][j]=min(lm[i][j],lc.lr[i][k]+rc.ll[k][j]+lc.rr[j][j]);
rm[i][j]=min(rm[i][j],rc.ll[i][i]+lc.rr[i][k]+rc.lr[k][j]);
}
for(int i(0);i<6;i++)
for(int j(0);j<6;j++) {
res.ll[i][j]=lc.ll[i][j];
res.rr[i][j]=rc.rr[i][j];
res.lr[i][j]=inf;
for(int k(0);k<6;k++) {
res.ll[i][j]=min(res.ll[i][j],lm[i][k]+lc.lr[j][k]-lc.rr[k][k]);
res.rr[i][j]=min(res.rr[i][j],rm[k][i]+rc.lr[k][j]-rc.ll[k][k]);
res.lr[i][j]=min(res.lr[i][j],min(lm[i][k]+rm[k][j]-lc.rr[k][k]-rc.ll[k][k],lc.lr[i][k]+rc.lr[k][j]));
}
}
return res;
}
#define lc (a<<1)
#define rc ((a<<1)|1)
inline void Calc(const int &a,const int &l) {
static int sum[6],tmp;
for(int i(0);i<6;i++) sum[i]=val[i][l]+(i?sum[i-1]:0);
for(int i(0);i<6;i++)
for(int j(0);j<6;j++) {
if(i<j) tmp=sum[j]-(i?sum[i-1]:0);
else tmp=sum[i]-(j?sum[j-1]:0);
st[a].ll[i][j]=st[a].rr[i][j]=st[a].lr[i][j]=tmp;
}
}
void Build(const int &a=1,const int &l=1,const int &r=n) {
if(l==r) return Calc(a,l);
int mid=(l+r)>>1;
Build(lc,l,mid);
Build(rc,mid+1,r);
st[a]=st[lc]+st[rc];
}
void Modify(const int &x,const int &y,const int &k,const int &a=1,const int &l=1,const int &r=n) {
if(l==r) {
val[x][y]=k;
Calc(a,l);
return;
}
int mid=(l+r)>>1;
if(y<=mid) Modify(x,y,k,lc,l,mid);
else Modify(x,y,k,rc,mid+1,r);
st[a]=st[lc]+st[rc];
}
Node Query(const int &left,const int &right,const int &a=1,const int &l=1,const int &r=n) {
if(left<=l&&right>=r) return st[a];
int mid=(l+r)>>1;
if(right<=mid) return Query(left,right,lc,l,mid);
if(left>mid) return Query(left,right,rc,mid+1,r);
return Query(left,right,lc,l,mid)+Query(left,right,rc,mid+1,r);
}
inline int Solve(const int &x1,const int &y1,const int &x2,const int &y2) {
static Node l,mid,r;
l=Query(1,y1);
mid=Query(y1,y2);
r=Query(y2,n);
int ans=inf;
for(int i(0);i<6;i++)
for(int j(0);j<6;j++)
for(int k(0);k<6;k++)
for(int p(0);p<6;p++)
ans=min(ans,mid.ll[x1][i]+l.rr[i][j]+mid.lr[j][k]+r.ll[k][p]
+mid.rr[p][x2]-mid.ll[i][i]-mid.ll[j][j]-mid.rr[k][k]-mid.rr[p][p]);
// int ans=mid.lr[x1][x2];
// for(int i(0);i<6;i++)
// for(int j(0);j<6;j++) {
// ans=min(ans,mid.ll[x1][i]+l.rr[i][j]+mid.lr[j][x2]-val[i][y1]-val[j][y1]);
// ans=min(ans,mid.lr[x1][i]+r.ll[i][j]+mid.rr[j][x2]-val[i][y2]-val[j][y2]);
// ans=min(ans,l.rr[x1][i]+mid.lr[i][j]+r.ll[j][x2]-val[i][y1]-val[j][y2]);
// }
return ans;
}
#undef lc
#undef rc
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("load.in","r",stdin);
#endif
read(n);
for(int i(0);i<6;i++)
for(int j(1);j<=n;j++)
read(val[i][j]);
SegmentTree::Build();
read(m);
for(int i(1);i<=m;i++) {
int opt,x1,y1,x2,y2;
read(opt);
if(opt==1) {
read(x1,y1,x2);
SegmentTree::Modify(x1-1,y1,x2);
}
else if(opt==2) {
read(x1,y1,x2,y2);
if(y1>y2) swap(x1,x2),swap(y1,y2);
write(SegmentTree::Solve(x1-1,y1,x2-1,y2),'\n');
}
}
flush();
return 0;
}
这里空空如也
有帮助,赞一个