2020牛客NOIP赛前集训营-提高组（第六场）B 艰难睡眠

什么泄出题人比赛开始了两个小时才改好题面。

首先枚举连续睡觉时间的开始，则可以算出在这一段时间内吵闹的人转移到的可行区间。

这样问题就变成每次有一段可行区间求区间最小值。

直接st表肯定是不行的，但是注意到每次睡觉时间只会往后移动1，那么吵闹的人转移到的可行区间的l和r也只会变化1。

这样我们可以用单调队列维护，具体的在时间1把可行区间里的所有吵闹的人加入单调队列，然后右移左右端点，加入右端点的权值，更新即可。

注意到每个人对答案的贡献是独立的，所以可以每个人分开算，即每个人算出睡眠左端点为i时的最小值，最后把所有人的答案相加即可。

然后这题是个环，为了方便处理可以断环成链。

/*
    _______                       ________                        _______
   / _____ \                     / ______ \                      / _____ \
  / /     \_\  _     __     _   / /      \ \   _     __     _   / /     \_\
 | |          | |   |  |   | | | |        | | | |   |  |   | | | |
 | |          | |   |  |   | | | |     __ | | | |   |  |   | | | |
 | |       __ \  \  |  |  /  / | |     \ \| | \  \  |  |  /  / | |       __
  \ \_____/ /  \  \/ /\ \/  /   \ \_____\  /   \  \/ /\ \/  /   \ \_____/ /
   \_______/    \___/  \___/     \______/\__\   \___/  \___/     \_______/
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

#define ll long long

const int N = 5000;
const ll INF = 1e18;

int n, m, k, c[N + 50];

ll ans[2050];

struct Node
{
    int a, b;
} a[N + 50];

void Read(int &x)
{
    x = 0; int p = 0; char st = getchar();
    while (st < '0' || st > '9') p = (st == '-'), st = getchar();
    while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) + st - '0', st = getchar();
    x = p ? -x : x;
    return;
}

struct Nod
{
    int id, qz;
};

deque<Nod> q; 

namespace io {
const int L = (1 << 21) + 1;
char ibuf[L], *iS, *iT, obuf[L], *oS = obuf, *oT = obuf + L - 1, c, st[55];
int f, tp;
#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,L,stdin),(iS==iT?EOF:*iS++)):*iS++)
inline void gi(int& x) { //get
    for (f = 1, c = gc(); c < '0' || c > '9'; c = gc())
        if (c == '-') f = -1;
    for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15);
    x *= f;
}
};  // namespace io
using io::gi;

int main()
{
    gi(n); gi(m); gi(k);
    for (int i = 1; i <= n; i++) 
    {
        gi(a[i].a), gi(a[i].b);
        if (a[i].b > m - k) 
        {
            puts("-1");
            return 0;
        }
    }
    int l, r;
    for (int i = 1; i <= n; i++)
    {
        while (!q.empty()) q.pop_front();
        for (int j = 1; j <= m; j++)
            gi(c[j]), c[j + m] = c[j];
        l = k + 1;
        r = m - a[i].b + 1;
        for (int j = l; j <= r; j++)
        {
            while (!q.empty() && q.back().qz >= c[j]) q.pop_back();
            q.push_back((Nod){j, c[j]});
        }
        ans[1] += q.front().qz;
        for (int j = 2; j <= m; j++)
        {
            l++; r++;
            while (!q.empty() && q.front().id < l) q.pop_front();
            while (!q.empty() && q.back().qz >= c[r]) q.pop_back();
            q.push_back((Nod){r, c[r]});
            ans[j] += q.front().qz;
        }
    }
    ll answer = ans[1];
    for (int i = 2; i <= m; i++) answer = min(answer, ans[i]);
    printf("%lld", answer);
    return 0;
}