生活随笔
收集整理的這篇文章主要介紹了
LuoguP5897 [IOI2013]wombats
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
LuoguP5897 [IOI2013]wombats
題目描述
簡要題意：有一個R?CR*CR?C的網格圖，邊有邊權，支持修改，多次詢問V1,V2V_1,V_2V1?,V2?，求點(0,V1)(0,V_1)(0,V1?)到(R?1,V2)(R-1,V_2)(R?1,V2?)的最短路（只能往左右和往下走）。
Solution
記f[i][j]f[i][j]f[i][j]表示從(0,i)(0,i)(0,i)到(0,j)(0,j)(0,j)的最短路，可以通過一行一行DPDPDP在O(R?C2)O(R*C^2)O(R?C2)的時間內求得，而每次修改需要重新求答案，所以時間復雜度為O(R?C2?Q)O(R*C^2*Q)O(R?C2?Q)。
但我們發現這題的RRR很大，而CCC很小，所以我們考慮把RRR這一位扔到線段樹上，線段樹的一個區間記錄了一個C?CC*CC?C的矩陣。線段[l,r][l,r][l,r]中矩陣的一個點Di,jD_{i,j}Di,j?記錄從(l,i)(l,i)(l,i)到(r,j)(r,j)(r,j)的距離，這樣每次修改就只需要修改lognlog^nlogn。
接下來考慮兩個線段怎么合并，如果暴力枚舉的話時間復雜度為O(n3)O(n^3)O(n3)（類似floydfloydfloyd的方法，枚舉i,ji,ji,j和中間點kkk），但我們發現這里有決策單調性，我們固定一個點iii，枚舉jjj，假設jjj的最優決策點為kkk，那么對于任意的j′>jj'>jj′>j，j′j'j′的最優決策點k′>kk'>kk′>k，這樣就可以通過分治做到O(n2lgn)O(n^2lgn)O(n2lgn)或直接記錄決策點位置做到O(n2)O(n^2)O(n2)。
這樣優化之后時間復雜度就OKOKOK了。然而空間還是太大了，于是有一個神奇的套路：在線段樹中，若線段的長度小于一個閾值ttt，則通過之前說的O(n3)O(n^3)O(n3)暴力求解DDD矩陣。
我的程序當閾值設為20的時候能過。
所以時空復雜度就是O(能過)O(能過)O(能過)了（懶得算QAQ）
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define fi first
#define se secondusing namespace std
;template<typename T
>inline bool upmin(T
&x
,T y
) { return y
<x
?x
=y
,1:0; }
template<typename T
>inline bool upmax(T
&x
,T y
) { return x
<y
?x
=y
,1:0; }typedef long long ll
;
typedef unsigned long long ull
;
typedef long double lod
;
typedef pair
<int,int> PR
;
typedef vector
<int> VI
;const lod eps
=1e-11;
const lod pi
=acos(-1);
const int oo
=1<<30;
const ll loo
=1ll<<62;
const int mods
=998244353;
const int MAXN
=5005;
const int INF
=0x3f3f3f3f;
inline int read()
{int f
=1,x
=0; char c
=getchar();while (c
<'0'||c
>'9') { if (c
=='-') f
=-1; c
=getchar(); }while (c
>='0'&&c
<='9') { x
=(x
<<3)+(x
<<1)+(c
^48); c
=getchar(); }return x
*f
;
}
int n
,m
,d1
[MAXN
][205],d2
[MAXN
][205],s
[MAXN
][205],tmp
[205][205];
struct Matrix
{int A
[205][205],l
,r
;void clear(int L
,int R
) {l
=L
,r
=R
;for (int i
=1;i
<=m
;i
++) for (int j
=1;j
<=m
;j
++) A
[i
][j
]=INF
;}Matrix(int L
=0,int R
=0) { clear(L
,R
); }void rebuild(int L
,int R
){l
=L
,r
=R
;for (int i
=1;i
<=m
;i
++) for (int j
=1;j
<=m
;j
++) A
[i
][j
]=abs(s
[l
][i
]-s
[l
][j
]);for (int k
=l
+1;k
<=r
;k
++){for (int i
=1;i
<=m
;i
++)for (int j
=1;j
<=m
;j
++) A
[i
][j
]+=d2
[k
][j
],tmp
[i
][j
]=A
[i
][j
];for (int i
=1,smin
;i
<=m
;i
++){smin
=tmp
[i
][1];for (int j
=2;j
<=m
;j
++) smin
+=d1
[k
][j
],upmin(smin
,tmp
[i
][j
]),upmin(A
[i
][j
],smin
);smin
=tmp
[i
][m
];for (int j
=m
-1;j
>=1;j
--) smin
+=d1
[k
][j
+1],upmin(smin
,tmp
[i
][j
]),upmin(A
[i
][j
],smin
);}}}void print(){cout
<<l
<<" "<<r
<<endl
;for (int i
=1;i
<=m
;i
++){for (int j
=1;j
<=m
;j
++) cout
<<A
[i
][j
]<<" ";cout
<<endl
;}cout
<<endl
;}
} ans
;
struct Segment_Tree
{Matrix tree
[1005];void Solve(Matrix
&x
,Matrix
&y
,int t
,int l
,int r
,int L
,int R
){ int mid
=(l
+r
)>>1,k
=L
;for (int i
=L
+1;i
<=R
;i
++)if (x
.A
[t
][i
]+d2
[y
.l
][i
]+y
.A
[i
][mid
]<x
.A
[t
][k
]+d2
[y
.l
][k
]+y
.A
[k
][mid
]) k
=i
;ans
.A
[t
][mid
]=x
.A
[t
][k
]+d2
[y
.l
][k
]+y
.A
[k
][mid
];if (l
==r
) return;Solve(x
,y
,t
,l
,mid
,L
,k
);Solve(x
,y
,t
,mid
+1,r
,k
,R
);}Matrix
Merge(Matrix
&x
,Matrix
&y
){ ans
.clear(x
.l
,y
.r
);for (int i
=1;i
<=m
;i
++) Solve(x
,y
,i
,1,m
,1,m
);return ans
;}void up(int x
) { tree
[x
]=Merge(tree
[x
<<1],tree
[x
<<1|1]); }void build(int x
,int l
,int r
){if (r
-l
<=20) { tree
[x
].rebuild(l
,r
); return; }int mid
=(l
+r
)>>1;build(x
<<1,l
,mid
);build(x
<<1|1,mid
+1,r
);up(x
);}void change(int x
,int l
,int r
,int y
){if (r
-l
<=20) { tree
[x
].rebuild(l
,r
); return; }int mid
=(l
+r
)>>1;if (y
<=mid
) change(x
<<1,l
,mid
,y
);else change(x
<<1|1,mid
+1,r
,y
);up(x
);}
} segment
;int main()
{n
=read(),m
=read();for (int i
=1;i
<=n
;i
++)for (int j
=2;j
<=m
;j
++) d1
[i
][j
]=read(),s
[i
][j
]=s
[i
][j
-1]+d1
[i
][j
];for (int i
=2;i
<=n
;i
++)for (int j
=1;j
<=m
;j
++) d2
[i
][j
]=read();segment
.build(1,1,n
);int Case
=read();while (Case
--){int opt
=read();if (opt
==1) { int x
=read()+1,y
=read()+2;d1
[x
][y
]=read(); for (;y
<=m
;y
++) s
[x
][y
]=s
[x
][y
-1]+d1
[x
][y
];segment
.change(1,1,n
,x
);}else if (opt
==2) {int x
=read()+2,y
=read()+1;d2
[x
][y
]=read(),segment
.change(1,1,n
,x
);}else printf("%d\n",segment
.tree
[1].A
[read()+1][read()+1]);}return 0;
}
總結
以上是生活随笔為你收集整理的LuoguP5897 [IOI2013]wombats的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
