Good Bye 2015 F - New Year and Cleaning

这题简直是丧心病狂折磨王。。

思路：容易想到这样一个转换，把整个矩形一起移动，矩形移出去的时候相当于一行或者一列。

为了优化找到下一个消去的点，我先把原数组扩大两倍，用了st表加二分去找，然后就MLE，我又换了

线段树TLE，最后不把数组扩大两倍ST表+二分过的。。

每次消去的点都是不变的，所以可以做到线性复杂度。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PII pair<int, int>

#define PLI pair<LL, int>

#define ull unsigned long long

using namespace std;

const int N = 5e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

int k, n, m, X[N], Y[N], Log[N];

char s[N];

struct ST {

    int dp[N][],ty;

    void build(int n, int b[], int _ty) {

        ty = _ty;

        for(int i = ; i <= n; i++) dp[i][] = ty * b[i];

        for(int j = ; j <= Log[n]; j++)

            for(int i = ; i+(<<j)- <= n; i++)

                dp[i][j] = max(dp[i][j-], dp[i+(<<(j-))][j-]);

    }

    int query(int x, int y) {

        int k = Log[y - x + ];

        return ty * max(dp[x][k], dp[y-(<<k)+][k]);

    }

} mxx, mnx, mxy, mny;

void walk(int &x, int &y, char c) {

    if(c == 'R') y++;

    else if(c == 'L') y--;

    else if(c == 'U') x--;

    else x++;

}

bool check(int l, int r, int x, int y, int lenr, int lenc) {

    int mxX = mxx.query(l, r) - X[l-];

    int mnX = mnx.query(l, r) - X[l-];

    int mxY = mxy.query(l, r) - Y[l-];

    int mnY = mny.query(l, r) - Y[l-];

    if(x+mxX+lenr > n || x+mnX <  || y+mxY+lenc > m || y+mnY < ) return true;

    return false;

}

int main() {

    for(int i = -(Log[]=-); i < N; i++)

        Log[i] = Log[i - ] + ((i & (i - )) == );

    scanf("%d%d%d%s", &k, &n, &m, s + );

    int x = , y = , L = , R = , D = , U = , p = ;

    for(int i = ; i <= k; i++) {

        walk(x, y, s[i]);

        L = min(L, y); R = max(R, y);

        U = min(U, x); D = max(D, x);

    }

    if(!x && !y) {

        if(R - L +  <= m && D - U +  <= n) {

            puts("-1");

            return ;

        }

    }

    x = , y = ;

    for(int i = ; i <= k; i++) {

        walk(x, y, s[i]);

        X[i] = x; Y[i] = y;

    }

    mxx.build(k, X, );

    mnx.build(k, X, -);

    mxy.build(k, Y, );

    mny.build(k, Y, -);

    x = , y = ;

    int lenr = n, lenc = m;

    LL ans = , t = ;

    while(lenr && lenc) {

        int l = p + , r = min(k, p + k), pos = -;

        while(l <= r) {

            int mid = l + r >> ;

            if(check(p + , mid, x, y, lenr, lenc)) r = mid - , pos = mid;

            else l = mid + ;

        }

        if(pos != -) {

            x += X[pos] - X[p];

            y += Y[pos] - Y[p];

            t = (t + pos - p) % mod;

            p = pos;

            if(s[p] == 'U') {

                lenr--; ans = (ans + 1ll*t*lenc) % mod;

                x = ;

            } else if(s[p] == 'D') {

                lenr--; ans = (ans + 1ll*t*lenc) % mod;

            } else if(s[p] == 'L') {

                lenc--; ans = (ans + 1ll*t*lenr) % mod;

                y = ;

            } else {

                lenc--; ans = (ans + 1ll*t*lenr) % mod;

            }

            if(p == k) p = ;

        } else {

            x += X[k] - X[p];

            y += Y[k] - Y[p];

            t = (t + k - p) % mod;

            p = ;

        }

    }

    printf("%lld\n", ans);

    return ;

}

/*

*/

巴特西

Good Bye 2015 F - New Year and Cleaning

最新文章

热门文章