tin print 变化 mes sin void n-2 下标
X 国的地图可以被看作一个两行 nn 列的网格状图。现在 X 国需要修建铁路,然而该国的国王非常小气,他只想保证位于某两列之间的所有城市互相可以到达就行了,在此基础上,他希望所花费的代价最小。
铁路可以建在任何两个相邻的点之间,使他们可以互相到达。可以作为工作人员,你已经整理出了为每一对相邻城市架设铁路所需要的花费。你需要准备好回答国王如下形式的问题。
对于 (i,j)(i,j):当前情况下,使第 ii 列到第 jj 列之间的所有城市连通的最小代价是多少(列下标从 11 开始)?注意不能用其他列的城市。
然而你还有更大的困难,随着时间变化,使用某些边作为铁路的代价会发生改变,你必须有效率地处理这些变化。
输入格式
第一行两个正整数 n,m,表示该国有 2 行 n 列以及 m个询问或者操作。
第二行 3n-2个数,前 n-1个数依次表示在第一行的 n-1 条边上修建铁路的代价。
接下来 n-1 个数,依次表示在第二行的 n-1 条边上修建铁路的代价。
最后 n 个数,依次表示在第 1列到第 n列的边上修建铁路的代价。
接下来 m 行的输入具有如下形式,K,S,T其中
若 K=1,则表示询问当前状态下,使所有第 S 列到第 T 列之间的城市连通需要的最小代价。
若 K=2,则表示位于第 1 行第 S 列的点到第 1 行第 S+1 列的点之间的边上修建铁路的代价变为 T。
若 K=3,则表示位于第 2 行第 S 列的点和第 2 行第 S+1 列的点之间的边上修建铁路的代价变为 T。
若 K=4,则表示第 S 列的边上修建铁路的代价变为 T。
输出格式
依次对每个询问,用一行输出相应的答案。
数据范围与约定
对于 30% 的数据:n,m≤2000。
另有 30% 的数据:所有竖边的代价为 0 且永不改变。
对于全部数据:n,m<10^5
所有输入和输出数据保证合法,且不超过 2^{31}-1
样例输入
4 14
2 3 4 3 1 1 1 5 4 7
1 1 2
1 2 3
1 1 3
1 2 4
2 1 5
1 1 4
4 2 1
1 1 3
1 2 3
1 2 4
3 3 100
1 3 4
1 2 4
1 1 4
样例输出
6
8
10
13
17
9
5
10
15
16
20
今天有点晚了,明天更
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- typedef long long lol;
- struct XXX
- {
- lol a[2][2];
- };
- lol w[800001][2][2],a[200001],b[200001],c[200001];
- int n,m;
- void pushup(int rt,int mid)
- {int i,j;
- for (i=0;i<=1;i++)
- for (j=0;j<=1;j++)
- {
- w[rt][i][j]=1e9;
- lol cost=w[rt*2][i][1]+w[rt*2+1][1][j]-c[mid+1];
- w[rt][i][j]=min(w[rt][i][j],cost);
- cost=w[rt*2][i][0]+w[rt*2+1][1][j]-c[mid+1];
- w[rt][i][j]=min(w[rt][i][j],cost);
- cost=w[rt*2][i][1]+w[rt*2+1][0][j]-c[mid+1];
- w[rt][i][j]=min(w[rt][i][j],cost);
- }
- }
- void build(int rt,int l,int r)
- {
- if (l>r) return;
- if (l==r)
- {
- lol tot=a[l]+b[l]+c[l]+c[l+1];
- w[rt][1][0]=tot-c[l+1];
- w[rt][1][1]=tot-(a[l]+b[l]+abs(b[l]-a[l]))/2;
- w[rt][0][0]=1e9;
- w[rt][0][1]=tot-c[l];
- return;
- }
- int mid=(l+r)/2;
- build(rt*2,l,mid);
- build(rt*2+1,mid+1,r);
- pushup(rt,mid);
- }
- void ask(int rt,int l,int r,int L,int R,XXX &p)
- {int i,j;
- if (l>r) return;
- if (l>=L&&r<=R)
- {
- for (i=0;i<=1;i++)
- for (j=0;j<=1;j++)
- p.a[i][j]=w[rt][i][j];
- return;
- }
- XXX p1,p2;
- if (l==r) return;
- int mid=(l+r)/2;
- if (L>=mid+1)
- {
- ask(rt*2+1,mid+1,r,L,R,p2);
- for (i=0;i<=1;i++)
- for (j=0;j<=1;j++)
- p.a[i][j]=p2.a[i][j];
- return;
- }
- if (R<=mid)
- {
- ask(rt*2,l,mid,L,R,p1);
- for (i=0;i<=1;i++)
- for (j=0;j<=1;j++)
- p.a[i][j]=p1.a[i][j];
- return;
- }
- ask(rt*2,l,mid,L,R,p1);
- ask(rt*2+1,mid+1,r,L,R,p2);
- for (i=0;i<=1;i++)
- for (j=0;j<=1;j++)
- {
- p.a[i][j]=1e9;
- lol cost=p1.a[i][1]+p2.a[1][j]-c[mid+1];
- p.a[i][j]=min(p.a[i][j],cost);
- cost=p1.a[i][0]+p2.a[1][j]-c[mid+1];
- p.a[i][j]=min(p.a[i][j],cost);
- cost=p1.a[i][1]+p2.a[0][j]-c[mid+1];
- p.a[i][j]=min(p.a[i][j],cost);
- }
- }
- void update(int rt,int l,int r,lol k,lol x,lol d)
- {
- if (l>r) return;
- if (l==r)
- {
- if (k==2) a[x]=d;
- if (k==3) b[x]=d;
- if (k==4) c[x]=d;
- lol tot=a[l]+b[l]+c[l]+c[l+1];
- w[rt][1][0]=tot-c[l+1];
- w[rt][1][1]=tot-(a[l]+b[l]+abs(b[l]-a[l]))/2;
- w[rt][0][0]=1e9;
- w[rt][0][1]=tot-c[l];
- return;
- }
- int mid=(l+r)/2;
- if (k==4)
- {
- if (x<=mid+1) update(rt*2,l,mid,k,x,d);
- if (x>=mid+1) update(rt*2+1,mid+1,r,k,x,d);
- }
- else
- {
- if (x<=mid) update(rt*2,l,mid,k,x,d);
- else update(rt*2+1,mid+1,r,k,x,d);
- }
- pushup(rt,mid);
- }
- int main()
- {int i;
- lol k,s,t;
- XXX p;
- cin>>n>>m;
- for (i=1;i<=n-1;i++)
- scanf("%lld",&a[i]);
- for (i=1;i<=n-1;i++)
- scanf("%lld",&b[i]);
- for (i=1;i<=n;i++)
- scanf("%lld",&c[i]);
- build(1,1,n-1);
- while (m--)
- {lol ans=2e9;
- scanf("%lld%lld%lld",&k,&s,&t);
- if (k==1)
- {
- if (s==t)
- {printf("%lld\n",c[s]);continue;}
- ask(1,1,n-1,s,t-1,p);
- ans=min(min(p.a[0][0],p.a[0][1]),min(p.a[1][0],p.a[1][1]));
- printf("%lld\n",ans);
- }
- else
- {
- update(1,1,n-1,k,s,t);
- }
- }
- }
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- typedef long long lol;
- struct XXX
- {
- lol a[2][2];
- };
- lol w[800001][2][2],a[200001],b[200001],c[200001];
- int n,m;
- void pushup(int rt,int mid)
- {int i,j;
- for (i=0;i<=1;i++)
- for (j=0;j<=1;j++)
- {
- w[rt][i][j]=1e9;
- lol cost=w[rt*2][i][1]+w[rt*2+1][1][j]-c[mid+1];
- w[rt][i][j]=min(w[rt][i][j],cost);
- cost=w[rt*2][i][0]+w[rt*2+1][1][j]-c[mid+1];
- w[rt][i][j]=min(w[rt][i][j],cost);
- cost=w[rt*2][i][1]+w[rt*2+1][0][j]-c[mid+1];
- w[rt][i][j]=min(w[rt][i][j],cost);
- }
- }
- void build(int rt,int l,int r)
- {
- if (l>r) return;
- if (l==r)
- {
- lol tot=a[l]+b[l]+c[l]+c[l+1];
- w[rt][1][0]=tot-c[l+1];
- w[rt][1][1]=tot-(a[l]+b[l]+abs(b[l]-a[l]))/2;
- w[rt][0][0]=1e9;
- w[rt][0][1]=tot-c[l];
- return;
- }
- int mid=(l+r)/2;
- build(rt*2,l,mid);
- build(rt*2+1,mid+1,r);
- pushup(rt,mid);
- }
- void ask(int rt,int l,int r,int L,int R,XXX &p)
- {int i,j;
- if (l>r) return;
- if (l>=L&&r<=R)
- {
- for (i=0;i<=1;i++)
- for (j=0;j<=1;j++)
- p.a[i][j]=w[rt][i][j];
- return;
- }
- XXX p1,p2;
- if (l==r) return;
- int mid=(l+r)/2;
- if (L>=mid+1)
- {
- ask(rt*2+1,mid+1,r,L,R,p2);
- for (i=0;i<=1;i++)
- for (j=0;j<=1;j++)
- p.a[i][j]=p2.a[i][j];
- return;
- }
- if (R<=mid)
- {
- ask(rt*2,l,mid,L,R,p1);
- for (i=0;i<=1;i++)
- for (j=0;j<=1;j++)
- p.a[i][j]=p1.a[i][j];
- return;
- }
- ask(rt*2,l,mid,L,R,p1);
- ask(rt*2+1,mid+1,r,L,R,p2);
- for (i=0;i<=1;i++)
- for (j=0;j<=1;j++)
- {
- p.a[i][j]=1e9;
- lol cost=p1.a[i][1]+p2.a[1][j]-c[mid+1];
- p.a[i][j]=min(p.a[i][j],cost);
- cost=p1.a[i][0]+p2.a[1][j]-c[mid+1];
- p.a[i][j]=min(p.a[i][j],cost);
- cost=p1.a[i][1]+p2.a[0][j]-c[mid+1];
- p.a[i][j]=min(p.a[i][j],cost);
- }
- }
- void update(int rt,int l,int r,lol k,lol x,lol d)
- {
- if (l>r) return;
- if (l==r)
- {
- if (k==2) a[x]=d;
- if (k==3) b[x]=d;
- if (k==4) c[x]=d;
- lol tot=a[l]+b[l]+c[l]+c[l+1];
- w[rt][1][0]=tot-c[l+1];
- w[rt][1][1]=tot-(a[l]+b[l]+abs(b[l]-a[l]))/2;
- w[rt][0][0]=1e9;
- w[rt][0][1]=tot-c[l];
- return;
- }
- int mid=(l+r)/2;
- if (k==4)
- {
- if (x<=mid+1) update(rt*2,l,mid,k,x,d);
- if (x>=mid+1) update(rt*2+1,mid+1,r,k,x,d);
- }
- else
- {
- if (x<=mid) update(rt*2,l,mid,k,x,d);
- else update(rt*2+1,mid+1,r,k,x,d);
- }
- pushup(rt,mid);
- }
- int main()
- {int i;
- lol k,s,t;
- XXX p;
- cin>>n>>m;
- for (i=1;i<=n-1;i++)
- scanf("%lld",&a[i]);
- for (i=1;i<=n-1;i++)
- scanf("%lld",&b[i]);
- for (i=1;i<=n;i++)
- scanf("%lld",&c[i]);
- build(1,1,n-1);
- while (m--)
- {lol ans=2e9;
- scanf("%lld%lld%lld",&k,&s,&t);
- if (k==1)
- {
- if (s==t)
- {printf("%lld\n",c[s]);continue;}
- ask(1,1,n-1,s,t-1,p);
- ans=min(min(p.a[0][0],p.a[0][1]),min(p.a[1][0],p.a[1][1]));
- printf("%lld\n",ans);
- }
- else
- {
- update(1,1,n-1,k,s,t);
- }
- }
- }
计蒜客NOIP模拟赛(3)D1T3 任性的国王
来源: http://www.bubuko.com/infodetail-2311853.html