Codeforces - 1195E - OpenStreetMap

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);

    }

}

巴特西

Codeforces - 1195E - OpenStreetMap - 单调队列

最新文章

热门文章