BZOJ 2104 [선분 수]
정보 통합 에 주의해 야 합 니 다. 아래 표 시 된 우선 순위 입 니 다. 오류 가 발생 하기 쉽 습 니 다.
/* I will wait for you */
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<string>
#define make(a,b) make_pair(a,b)
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int maxn=100010;
const int maxm=100010;
const int maxs=6;
const int INF=0x3f3f3f3f;
const int P=1000000007;
const double error=1e-4;
inline int read()
{
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0') f=(c=='-'?-1:1),c=getchar();
while(c<='9'&&c>='0') (x*=10)+=c-'0',c=getchar();
return x*f;
}
struct node
{
int ll[6][6],lr[6][6],rr[6][6];
inline void clear()
{
memset(ll,0x3f,sizeof(ll));
memset(lr,0x3f,sizeof(lr));
memset(rr,0x3f,sizeof(rr));
}
inline bool empty()
{
return ll[1][1]==INF;
}
}e[4*maxn];
inline node operator + (node li,node ri)
{
node ans;ans.clear();
if(li.empty()) return ri;
if(ri.empty()) return li;
int lm[6][6],rm[6][6];
memset(lm,0x3f,sizeof(lm));
memset(rm,0x3f,sizeof(rm));
for(int k=0;k<6;k++) for(int i=0;i<6;i++) for(int j=0;j<6;j++)
{
lm[i][j]=min(lm[i][j],li.lr[i][k]+ri.ll[k][j]);
rm[i][j]=min(rm[i][j],li.rr[j][k]+ri.lr[k][i]);
}
for(int i=0;i<6;i++) for(int j=0;j<6;j++)
{
ans.ll[i][j]=li.ll[i][j],ans.rr[i][j]=ri.rr[i][j];
for(int k=0;k<6;k++)
{
ans.ll[i][j]=min(ans.ll[i][j],lm[i][k]+li.lr[j][k]);
ans.rr[i][j]=min(ans.rr[i][j],rm[i][k]+ri.lr[k][j]);
ans.lr[i][j]=min(ans.lr[i][j],li.lr[i][k]+ri.lr[k][j]);
ans.lr[i][j]=min(ans.lr[i][j],lm[i][k]+rm[j][k]);
}
}
return ans;
}
int n,m,wi[maxn][6],sum[6];
inline node init(int y)
{
node ans;ans.clear();
for(int i=0;i<6;i++) ans.ll[i][i]=ans.lr[i][i]=ans.rr[i][i]=wi[y][i];
for(int i=0;i<6;i++) sum[i]=sum[i-1]+wi[y][i];
for(int i=0;i<6;i++) for(int j=0;j<6;j++)
ans.ll[i][j]=ans.lr[i][j]=ans.rr[i][j]=sum[max(i,j)]-sum[min(i,j)-1];
return ans;
}
inline void build(int o,int l,int r)
{
if(l==r) e[o]=init(l);
else
{
int mid=(l+r)/2;
build(2*o,l,mid),build(2*o+1,mid+1,r);
e[o]=e[2*o]+e[2*o+1];
}
}
inline void change(int o,int l,int r,int c)
{
if(l==r) e[o]=init(l);
else
{
int mid=(l+r)/2;
c<=mid?change(2*o,l,mid,c):change(2*o+1,mid+1,r,c);
e[o]=e[2*o]+e[2*o+1];
}
}
inline node qmin(int o,int l,int r,int x,int y)
{
node ans;ans.clear();
if(l>=x&&r<=y) ans=e[o];
else
{
int mid=(l+r)/2;
if(x<=mid) ans=qmin(2*o,l,mid,x,y)+ans;
if(y>mid) ans=ans+qmin(2*o+1,mid+1,r,x,y);
}
return ans;
}
inline int query(int x1,int y1,int x2,int y2)
{
node li=qmin(1,1,n,1,y1);
node mi=qmin(1,1,n,y1,y2);
node ri=qmin(1,1,n,y2,n);
int ans=mi.lr[x1][x2];
for(int i=0;i<6;i++) for(int j=0;j<6;j++)
{
ans=min(ans,mi.ll[x1][i]+li.rr[i][j]+mi.lr[j][x2]-wi[y1][i]-wi[y1][j]);
ans=min(ans,mi.lr[x1][i]+ri.ll[i][j]+mi.rr[j][x2]-wi[y2][i]-wi[y2][j]);
ans=min(ans,li.rr[x1][i]+mi.lr[i][j]+ri.ll[j][x2]-wi[y1][i]-wi[y2][j]);
}
return ans;
}
int main()
{
n=read();
for(int i=0;i<6;i++) for(int j=1;j<=n;j++) wi[j][i]=read();
build(1,1,n);
m=read();
while(m--)
{
int t=read();
if(t==1)
{
int x=read(),y=read(),z=read();
wi[y][x-1]=z,change(1,1,n,y);
}
if(t==2)
{
int x1=read(),y1=read(),x2=read(),y2=read();
if(y1>y2) swap(x1,x2),swap(y1,y2);
printf("%d
",query(x1-1,y1,x2-1,y2));
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.