NC20702. 机房网络
描述
输入描述
第一行，三个整数𝑛，𝑚，𝑄。
接下来一行，𝑛 −1个数𝑎𝑖，表示𝐴𝑖到𝐴𝑖+1的网线容量为𝑎𝑖。
接下来一行，𝑛 −1个数𝑏𝑗，表示𝐵𝑗到𝐵𝑗+1的网线容量为𝑏𝑗。之后有𝑚行，每行三个数𝑢,𝑣,𝑐，表示一条从𝐴𝑢连向𝐵𝑣的容量为𝑐的网线（可能会有重边）。最后𝑄行，每行两个整数𝑡,𝑐，表示将𝐴𝑡到𝐴𝑡+1的网线的容量上限调整至𝑐， 代表每次操作
输出描述
第一行，输出一个整数，表示初始状态时从𝐴1到𝐵𝑛的最大流量。
接下来𝑄行，每行一个整数，表示每次修改后从𝐴1到𝐵𝑛的最大流量。
示例1
输入:
3 1 2 1 4 2 8 2 2 5 1 10 2 100
输出:
1 5 5
C++14(g++5.4) 解法, 执行用时: 600ms, 内存消耗: 39776K, 提交时间: 2018-10-21 12:42:25
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=301000;
const long long inf=1e18;
struct node{
long long a,b,c;
}s[maxn];
bool cmp(node x,node y){
return x.a<y.a;
}
int n,m,q,p;
long long ANS,ans,lazy[maxn<<2],w[maxn],c,a[maxn],b[maxn];
inline void read(long long &n){
char c=getchar(); n=0; bool flag=0;
while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
while(c>='0'&&c<='9') n=n*10+c-48,c=getchar(); if(flag) n=-n;
}
struct tree{
int l,r; long long num;
}t[maxn<<2];
void build(int x,int l,int r){
t[x].l=l; t[x].r=r;
if(l==r){
t[x].num=b[l-1]; return ;
}
int mid=(l+r)>>1;
build(x<<1,l,mid); build((x<<1)|1,mid+1,r);
t[x].num=min(t[x<<1].num,t[(x<<1)|1].num);
}
void pushdown(int x){
t[x<<1].num+=lazy[x]; t[(x<<1)|1].num+=lazy[x];
lazy[x<<1]+=lazy[x]; lazy[(x<<1)|1]+=lazy[x]; lazy[x]=0;
}
void update(int x,int l,int r,long long c){
if(t[x].l>r||t[x].r<l) return ;
if(t[x].l>=l&&t[x].r<=r){
t[x].num+=c; lazy[x]+=c; return;
}
if(lazy[x]) pushdown(x);
update(x<<1,l,r,c); update((x<<1)|1,l,r,c);
t[x].num=min(t[x<<1].num,t[(x<<1)|1].num);
}
long long query(int x,int l,int r){
if(t[x].l>r||t[x].r<l) return inf;
if(t[x].l>=l&&t[x].r<=r) return t[x].num;
if(lazy[x]) pushdown(x);
return min(query(x<<1,l,r),query((x<<1)|1,l,r));
}
int main(){
cin>>n>>m>>q;
for(int i=1;i<n;i++) read(a[i]);
for(int i=1;i<n;i++) read(b[i]);
for(int i=1;i<=m;i++) read(s[i].a),read(s[i].b),read(s[i].c);
build(1,1,n);
sort(s+1,s+m+1,cmp); int head=1;
for(int i=1;i<=n;i++){
while(s[head].a<=i&&head<=m) update(1,1,s[head].b,s[head].c),head++;
w[i]=a[i]+query(1,1,n);
}
for(int i=1;i<=n;i++) b[i-1]=w[i];
build(1,1,n); memset(lazy,0,sizeof(lazy));
printf("%lld\n",query(1,1,n));
while(q--){
scanf("%d%lld",&p,&c); update(1,p,p,c-a[p]); a[p]=c;
printf("%lld\n",query(1,1,n));
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 390ms, 内存消耗: 28996K, 提交时间: 2018-10-21 09:15:13
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=301000;
const long long inf=1e18;
struct node{
long long a,b,c;
}s[maxn];
bool cmp(node x,node y){
return x.a<y.a;
}
int n,m,q,p;
long long ANS,ans,lazy[maxn<<2],w[maxn],c,a[maxn],b[maxn];
inline void read(long long &n){
char c=getchar(); n=0; bool flag=0;
while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
while(c>='0'&&c<='9') n=n*10+c-48,c=getchar(); if(flag) n=-n;
}
struct tree{
int l,r; long long num;
}t[maxn<<2];
void build(int x,int l,int r){
t[x].l=l; t[x].r=r;
if(l==r){
t[x].num=b[l-1]; return ;
}
int mid=(l+r)>>1;
build(x<<1,l,mid); build((x<<1)|1,mid+1,r);
t[x].num=min(t[x<<1].num,t[(x<<1)|1].num);
}
void pushdown(int x){
t[x<<1].num+=lazy[x]; t[(x<<1)|1].num+=lazy[x];
lazy[x<<1]+=lazy[x]; lazy[(x<<1)|1]+=lazy[x]; lazy[x]=0;
}
void update(int x,int l,int r,long long c){
if(t[x].l>r||t[x].r<l) return ;
if(t[x].l>=l&&t[x].r<=r){
t[x].num+=c; lazy[x]+=c; return;
}
if(lazy[x]) pushdown(x);
update(x<<1,l,r,c); update((x<<1)|1,l,r,c);
t[x].num=min(t[x<<1].num,t[(x<<1)|1].num);
}
long long query(int x,int l,int r){
if(t[x].l>r||t[x].r<l) return inf;
if(t[x].l>=l&&t[x].r<=r) return t[x].num;
if(lazy[x]) pushdown(x);
return min(query(x<<1,l,r),query((x<<1)|1,l,r));
}
int main(){
cin>>n>>m>>q;
for(int i=1;i<n;i++) read(a[i]);
for(int i=1;i<n;i++) read(b[i]);
for(int i=1;i<=m;i++) read(s[i].a),read(s[i].b),read(s[i].c);
build(1,1,n);
sort(s+1,s+m+1,cmp); int head=1;
for(int i=1;i<=n;i++){
while(s[head].a<=i&&head<=m) update(1,1,s[head].b,s[head].c),head++;
w[i]=a[i]+query(1,1,n);
}
for(int i=1;i<=n;i++) b[i-1]=w[i];
build(1,1,n); memset(lazy,0,sizeof(lazy));
printf("%lld\n",query(1,1,n));
while(q--){
scanf("%d%lld",&p,&c); update(1,p,p,c-a[p]); a[p]=c;
printf("%lld\n",query(1,1,n));
}
return 0;
}