NC20380. [SDOI2015]道路修建
描述
输入描述
第一行，两个整数N、M。
第二行，N-1个整数，其中第i个整数表示初始时第1行第i列的城市和第1行第i+1列的城市之间修建一条专用道路的费用。
第三行，N-1个整数，其中第i个整数表示初始时第2行第i列的城市和第2行第i+1列的城市之间修建一条专用道路的费用。
第四行，N个整数，其中第i个整数表示初始时第1行第i列的城市和第2行第i列的城市之间修建一条专用道路的费用。
接下来的M行，每行一个操作。
输出描述
对于每个询问操作，输出一行，表示你计算出的政府的最小开支。
示例1
输入:
3 3 1 2 2 1 3 1 2 Q 1 3 C 1 2 2 2 3 Q 2 3
输出:
7 5
C++14(g++5.4) 解法, 执行用时: 147ms, 内存消耗: 6092K, 提交时间: 2020-02-19 14:55:52
#include<bits/stdc++.h>
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
using namespace std;
const int MX=6e4+9;
int n,m,row[2][MX],clm[MX];
char order[2];
struct node{
int l,r,cnt,sum;
int l_val,r_val,l_max,r_max,row_max;
void init(int pos){
l=r=pos,cnt=1,row_max=0;
sum=l_max=r_max=l_val=r_val=clm[pos];
}
friend inline node operator+(const node &L,const node &R){
node ret;
ret.l=L.l,ret.r=R.r;
ret.row_max=max(max(row[0][L.r],row[1][L.r]),max(L.row_max,R.row_max));
int del=max(max(row[0][L.r],row[1][L.r]),max(L.r_max,R.l_max));
ret.sum=row[0][L.r]+row[1][L.r]+L.sum+R.sum-del;
ret.cnt=L.cnt+R.cnt;
ret.l_val=L.l_val,ret.r_val=R.r_val;
ret.l_max=L.l_max,ret.r_max=R.r_max;
if( L.r_val==del ){
ret.cnt--;
if( L.cnt==1 ){
ret.l_val=R.l_val;
ret.l_max=max(max(row[0][L.r],row[1][L.r]),max(L.row_max,R.l_max));
}
}
else if( R.l_val==del ){
ret.cnt--;
if( R.cnt==1 ){
ret.r_val=L.r_val;
ret.r_max=max(max(row[0][L.r],row[1][L.r]),max(R.row_max,L.r_max));
}
}
return ret;
}
}t[MX<<2];
void build(int k,int l,int r){
if( l==r ){
t[k].init(l);
return ;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
t[k]=t[k<<1]+t[k<<1|1];
}
void update_row(int k,int l,int r,int pos){
int mid=(l+r)>>1;
if( mid==pos ){
t[k]=t[k<<1]+t[k<<1|1];
return;
}
if( pos<=mid )
update_row(lson,pos);
else
update_row(rson,pos);
t[k]=t[k<<1]+t[k<<1|1];
}
void update_clm(int k,int l,int r,int pos){
if( l==r ){
t[k].init(pos);
return ;
}
int mid=(l+r)>>1;
if( pos<=mid )
update_clm(lson,pos);
else
update_clm(rson,pos);
t[k]=t[k<<1]+t[k<<1|1];
}
node que(int k,int l,int r,int L,int R){
if( L<=l && r<=R )
return t[k];
int mid=(l+r)>>1;
if( R<=mid )
return que(lson,L,R);
if( L>mid )
return que(rson,L,R);
else
return que(lson,L,R)+que(rson,L,R);
}
int main()
{
//freopen("input.txt","r",stdin);
scanf("%d %d",&n,&m);
for( int i=1 ; i<=n-1 ; i++ )
scanf("%d",&row[0][i]);
for( int i=1 ; i<=n-1 ; i++ )
scanf("%d",&row[1][i]);
for( int i=1 ; i<=n ; i++ )
scanf("%d",&clm[i]);
build(1,1,n);
while( m-- ){
scanf("%s",order);
int x1,x2,y1,y2,w,l,r;
if( order[0]=='C' ){
scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2,&w);
if( x1==x2 ){
if( y1>y2 )
swap(y1,y2);
row[x1-1][y1]=w;
update_row(1,1,n,y1);
}
else{
clm[y1]=w;
update_clm(1,1,n,y1);
}
}
else{
scanf("%d %d",&l,&r);
printf("%d\n",que(1,1,n,l,r).sum);
}
}
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 269ms, 内存消耗: 17208K, 提交时间: 2023-01-12 19:21:53
#include <bits/stdc++.h>
#define val sum
#define rp mxr
#define lp mxl
#define int long long
const int N = 6e4+1;
int mp[3][N];
int mp1[N];
int n,m;
struct node{
int l,r;
int mxl,mxr;
int id;
int mx;
int sum=0;
};
node tree[N<<2];
int querymx(int u, int x, int y){
if(x>y) return 0;
if(tree[u].l>=x&&tree[u].r<=y) return tree[u].mx;
int minn=-1;
if(tree[u<<1].r>=x) minn=querymx(u<<1,x,y);
if(tree[u<<1|1].l<=y) minn=std::max(querymx(u<<1|1,x,y),minn);
return minn;
}
void update(node &u,node l,node r,int mid){
u.l=l.l,u.r=r.r;
u.val=l.val+r.val+mp[1][mid]+mp[2][mid];
u.mx=std::max(std::max(l.mx,r.mx),std::max(mp[1][mid],mp[2][mid]));
int mx=std::max(querymx(l.id,l.rp,mid),querymx(r.id,mid+1,r.lp-1)),tmp=std::max(mp1[l.rp],mp1[r.lp]);
if(tmp<=mx)u.val-=mx,u.lp=l.lp,u.rp=r.rp;
else if(tmp==mp1[l.rp])u.val-=tmp,u.lp=(l.lp==l.rp?r.lp:l.lp),u.rp=r.rp;
else u.val-=tmp,u.lp=l.lp,u.rp=(r.rp==r.lp?l.rp:r.rp);
}
void build(int u, int l, int r){
tree[u].l=l,tree[u].r=r;
tree[u].id=u;
if(l==r){
tree[u].mxl=tree[u].mxr=l;
tree[u].mx=std::max(mp[1][l],mp[2][l]);
tree[u].sum=mp1[l];
return;
}
int mid=l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
update(tree[u],tree[u<<1],tree[u<<1|1],mid);
}
void change(int u, int y){
if(tree[u].l==tree[u].r){
tree[u].sum=mp1[y];
tree[u].mx=std::max(mp[1][y],mp[2][y]);
return;
}
int mid=tree[u].l+tree[u].r>>1;
if(y<=mid) change(u<<1,y);
else change(u<<1|1,y);
update(tree[u],tree[u<<1],tree[u<<1|1],mid);
}
node query(int u, int x, int y){
if(tree[u].l==x&&tree[u].r==y) return tree[u];
int mid=tree[u].l+tree[u].r>>1;
if(y<=mid) return query(u<<1,x,y);
else if(x>mid) return query(u<<1|1,x,y);
node l=query(u<<1,x,mid),r=query(u<<1|1,mid+1,y),res;
l.id=u<<1,r.id=u<<1|1,res.id=u;
update(res,l,r,mid);
return res;
}
signed main()
{
std::ios::sync_with_stdio(0);
std::cin.tie(0),std::cout.tie(0);
std::cin >> n >> m;
for(int i=1; i<=2; i++){
for(int j=1; j<n; j++) std::cin >> mp[i][j];
}
for(int i=1; i<=n; i++) std::cin >> mp1[i];
build(1,1,n);
while(m--){
char op;
std::cin >> op;
if(op=='Q'){
int x,y;
std::cin >> x >> y;
std::cout << query(1,x,y).sum << '\n';
}
else{
int a,b,c,d,e;
std::cin >> a >> b >> c >> d >> e;
if(a==c){
if(b>d) mp[a][d]=e,change(1,d);
else mp[a][b]=e,change(1,b);
}
else{
mp1[b]=e;
change(1,b);
}
}
}
return 0;
}
C++(clang++11) 解法, 执行用时: 95ms, 内存消耗: 6008K, 提交时间: 2021-02-15 09:04:31
#include <bits/stdc++.h>
using namespace std;
#define N 60005
#define mid ((l+r)>>1)
int a,b,c,d,e,n,m,v[N][3];char o[5];
struct nod{int l,r,lm,rm,ls,rs,am,ans,cnt;void init(int x){lm=rm=ls=rs=ans=v[x][2];cnt=1;am=0;}}s[N*4];
nod merge(nod x,nod y)
{
nod z;z.l=x.l;z.r=y.r;
int mxh=max(v[x.r][0],v[x.r][1]),mx=max(max(x.rm,y.lm),mxh);
z.ans=x.ans+y.ans+v[x.r][0]+v[x.r][1]-mx;z.am=max(max(x.am,y.am),mxh);z.cnt=x.cnt+y.cnt;
if(mx==x.rs&&x.cnt==1) z.lm=max(x.am,max(y.lm,mxh)),z.rm=y.rm,z.ls=y.ls,z.rs=y.rs,z.cnt--;
else if(mx==y.ls&&y.cnt==1) z.lm=x.lm,z.rm=max(y.am,max(mxh,x.rm)),z.ls=x.ls,z.rs=x.rs,z.cnt--;
else z.lm=x.lm,z.rm=y.rm,z.ls=x.ls,z.rs=y.rs,z.cnt-=(mx==x.rs||mx==y.ls);
return z;
}
void bud(int x,int l,int r)
{
if(l==r){s[x].init(l);s[x].l=l;s[x].r=r;return;}
bud(x*2,l,mid);bud(x*2+1,mid+1,r);s[x]=merge(s[x*2],s[x*2+1]);
}
void upd(int x,int l,int r,int p)
{
if(l==r){s[x].init(l);return;}
if(p<=mid) upd(x*2,l,mid,p);else upd(x*2+1,mid+1,r,p);s[x]=merge(s[x*2],s[x*2+1]);
}
nod que(int x,int l,int r,int b,int e)
{
if(b<=l&&r<=e) return s[x];
if(e<=mid) return que(x*2,l,mid,b,e);if(b>mid) return que(x*2+1,mid+1,r,b,e);
return merge(que(x*2,l,mid,b,e),que(x*2+1,mid+1,r,b,e));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++) scanf("%d",&v[i][0]);
for(int i=1;i<n;i++) scanf("%d",&v[i][1]);
for(int i=1;i<=n;i++) scanf("%d",&v[i][2]);
bud(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%s",o);
if(o[0]=='Q') scanf("%d%d",&a,&b),printf("%d\n",que(1,1,n,a,b).ans);
else
{
scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);if(b>d) swap(b,d);
if(a!=c) v[b][2]=e,upd(1,1,n,b);else v[b][a-1]=e,upd(1,1,n,b);
}
}
}