Codeforces - 1195E - OpenStreetMap - 单调队列

清疚 2021-11-13 19:02 282阅读 0赞

[https://codeforc.es/contest/1195/problem/E][https_codeforc.es_contest_1195_problem_E]

一个能运行但是会T的版本，因为本质上还是\\(O(nmab)\\)的算法。每次\\(O(ab)\\)初始化矩阵中的可能有用的点，然后\\(O(n-a)\\)往下推。

#include<bits/stdc++.h> using namespace std; typedef long long ll; #define ERR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); } void err(istream_iterator<string> it) {cerr << "\n";} template<typename T, typename... Args> void err(istream_iterator<string> it, T a, Args... args) { cerr << *it << "=" << a << ", "; err(++it, args...); } #define ERR1(arg,n) { cerr<<""<<#arg<<"=\n "; for(int i=1;i<=n;i++) cerr<<arg[i]<<" "; cerr<<"\n"; } #define ERR2(arg,n,m) { cerr<<""<<#arg<<"=\n"; for(int i=1;i<=n;i++) { cerr<<" "; for(int j=1;j<=m;j++)cerr<<arg[i][j]<<" "; cerr<<"\n"; } } int n, m, a, b; int x, y, z; int g[3000 * 3000 + 5]; int h[3005][3005]; struct node { int v, x; node(int vv, int xx) { v = vv; x = xx; } }; int curx, cury; deque<node> dq; void calc(int x, int y) { curx = x, cury = y; while(!dq.empty()) dq.pop_back(); for(int i = 1; i <= a; i++) { int minline = h[x + i - 1][y]; for(int j = 2; j <= b; j++) { minline = min(minline, h[x + i - 1][y + j - 1]); } while(!dq.empty() && minline <= dq.back().v) { dq.pop_back(); } if(dq.empty() || minline > dq.back().v) { dq.push_back(node(minline, x + i - 1)); } } } void move_to_nextline() { curx++; if(dq.front().x < curx) dq.pop_front(); int minline = h[curx + a - 1][cury]; for(int j = 2; j <= b; j++) { minline = min(minline, h[curx + a - 1][cury + j - 1]); } while(!dq.empty() && minline <= dq.back().v) { dq.pop_back(); } if(dq.empty() || minline > dq.back().v) { dq.push_back(node(minline, curx + a - 1)); } } ll ans = 0; int main() { #ifdef Yinku freopen("Yinku.in", "r", stdin); //freopen("Yinku.out", "w", stdout); #endif // Yinku while(~scanf("%d%d%d%d", &n, &m, &a, &b)) { scanf("%d%d%d%d", &g[1], &x, &y, &z); for(int i = 2; i <= n * m; i++) g[i] = (1ll * g[i - 1] * x % z + y) % z; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) h[i][j] = g[(i - 1) * m + j]; //ERR2(h, n, m); ans = 0; for(int i = 1; i + a - 1 <= n; i++) { for(int j = 1; j + b - 1 <= m; j++) { calc(i, j); ans += dq.front().v; for(int di = 1; di <= a; di++) { move_to_nextline(); } //ERR(ans); } } printf("%lld\n", ans); } }

其实不需要重复计算这么多的单调队列。  
具体的思路是这样：  
先把左侧的n行b列插入各行的单调队列dq\[i\]，然后取出各个队列的队首竖着组成单调队列dq2，这个单调队列dq2就可以回答左侧n行b列的所有的最小值，复杂度O(nb)。  
向右移动n个dq\[i\]，再回答左侧n行，\[2,b+1\]列的所有的最小值，复杂度O(n)。

总体复杂度O(nm)。

先用STL写了一个

#include<bits/stdc++.h> using namespace std; typedef long long ll; namespace Debug { #define ERR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); } void err(istream_iterator<string> it) {cerr << "\n";} template<typename T, typename... Args> void err(istream_iterator<string> it, T a, Args... args) { cerr << *it << "=" << a << ", "; err(++it, args...); } #define ERR1(arg,n) { cerr<<""<<#arg<<"=\n "; for(int i=1;i<=n;i++) cerr<<arg[i]<<" "; cerr<<"\n"; } #define ERR2(arg,n,m) { cerr<<""<<#arg<<"=\n"; for(int i=1;i<=n;i++) { cerr<<" "; for(int j=1;j<=m;j++)cerr<<arg[i][j]<<" "; cerr<<"\n"; } } } int n, m, a, b; int x, y, z; int g[3005 * 3005]; int h[3005][3005]; ll ans; struct Node { int val; int id; Node() {} Node(int val, int id): val(val), id(id) {} friend bool operator>=(const Node& n, const int& v) { return n.val >= v; } friend bool operator>=(const Node& n1, const Node& n2) { return n1.val >= n2.val; } }; deque<Node> dq[3005]; void init_deque(int i) { dq[i].clear(); for(int j = 1; j <= b; j++) { while(!dq[i].empty() && dq[i].back() >= h[i][j]) { dq[i].pop_back(); } dq[i].push_back({h[i][j], j}); } } void move_deque(int j) { for(int i = 1; i <= n; i++) { if(dq[i].front().id < j - b + 1) { dq[i].pop_front(); } while(!dq[i].empty() && dq[i].back() >= h[i][j]) { dq[i].pop_back(); } dq[i].push_back({h[i][j], j}); } } deque<Node> dq2; void calc_ans(int oj) { dq2.clear(); for(int i = 1; i <= a; i++) { while(!dq2.empty() && dq2.back() >= dq[i].front()) dq2.pop_back(); dq2.push_back({dq[i].front().val, i}); } ans += dq2.front().val; for(int i = a + 1; i <= n; i++) { if(dq2.front().id < i - a + 1) dq2.pop_front(); while(!dq2.empty() && dq2.back() >= dq[i].front()) dq2.pop_back(); dq2.push_back({dq[i].front().val, i}); ans += dq2.front().val; } } int main() { #ifdef Yinku freopen("Yinku.in", "r", stdin); //freopen("Yinku.out", "w", stdout); #endif // Yinku while(~scanf("%d%d%d%d", &n, &m, &a, &b)) { scanf("%d%d%d%d", &g[1], &x, &y, &z); for(int i = 2; i <= n * m; i++) g[i] = (1ll * g[i - 1] * x % z + y) % z; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) h[i][j] = g[(i - 1) * m + j]; for(int i = 1; i <= n; i++) { init_deque(i); } ans = 0; calc_ans(b); for(int nj = b + 1; nj <= m; nj++) { move_deque(nj); calc_ans(nj); } printf("%lld\n", ans); } }

转载于:https://www.cnblogs.com/Yinku/p/11205792.html

[https_codeforc.es_contest_1195_problem_E]: https://codeforc.es/contest/1195/problem/E