被教训了，以后要踏实一点，不懂的题都尽量写题解吧（希望明天jklover来的时候不要被虐爆）。

Solution

经典矩阵无覆盖问题，但是$R\times C$都无法跑，一般的做法显然是不行的，于是我们需要开始观察题目的特殊地方~~然后耍杂技~~。

可以发现数据保证数据一定随机，于是我们考虑从这个地方下手，发现如果正着做这道题的话需要用容斥，复杂度我们显然是无法接受的，于是考虑这个问题的补问题：有多少个矩阵没有被覆盖（下文称其为空矩阵）。

对于这个问题，我们考虑扫描线（行），即有多少个空矩阵的下界在当前的线上，令$w[x]$为第$x$列所扫描到的最低的覆盖点，那么目前的图就应该是这样的：

可以发现当前最低点的贡献就是其左边的列的数量+1$\times$右边列的数量+1（+1是因为当前列也行）。

而且当我们将空列补$0$（在$0$行插入一个覆盖点），那么这个贡献的列就会被转化成点，而且是可以递归处理的（断开已统计过的列即可），这就是一颗笛卡尔树。

又因为数据随机，所以用平衡树维护笛卡尔树的复杂度有保证。

时间复杂度：$O(l+(r+n)\log r)$。

Code

#include<bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0');
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res), putchar('\n');
}
const int N = 4e4 + 5;
int n, m, l, r, root;
vector<int>s[N];
namespace pol{
    int x, y, z, tot;
    struct Node{
        int s[2], id, v, sz;
        LL val;
        #define l(x) tr[x].s[0]
        #define r(x) tr[x].s[1]
    }tr[N << 2];
    inline void pushup(int x)
    {
        tr[x].sz = tr[l(x)].sz + tr[r(x)].sz + 1;
        tr[x].val = tr[l(x)].val + tr[r(x)].val + 1ll * (tr[l(x)].sz + 1) * (tr[r(x)].sz + 1) * tr[x].v;
    }
    inline int make(int id, int v)
    {
        tr[++ tot].id = id, tr[tot].v = v, tr[tot].sz = 1;
        return tot;
    }
    int merge(int x, int y)
    {
        if(!x || !y) return x | y;
        if(tr[x].v > tr[y].v)
        {
            r(x) = merge(r(x), y);
            pushup(x);
            return x;
        }
        else{
            l(y) = merge(x, l(y));
            pushup(y);
            return y;
        }
    }
    void split(int now, int k, int &x, int &y)
    {
        if(!now) x = 0, y = 0;
        else{
            if(tr[now].id <= k) x = now, split(r(now), k, r(now), y);
            else y = now, split(l(now), k, x, l(now));
            pushup(now);
        }
    }
    inline void modify(int id, int v)
    {
        split(root, id - 1, x, y), split(y, id, y, z);
        tr[y].v = v;
        root = merge(x, merge(y, z)); 
    }
    inline void insert(int id, int v)
    {
        split(root, id - 1, x, y);
        root = merge(x, merge(make(id, v), y));
    }
}
LL ans;
int main()
{
    read(l, r, n);
    for(int i = 1, st, ed;i <= n;i ++) read(st, ed), s[st].push_back(ed);
    for(int i = 1;i <= r;i ++) pol:: insert(i, 0);
    for(int i = 1;i <= l;i ++)
    {
        for(int j : s[i]) pol:: modify(j, i);
        ans += 1ll * r * (r + 1) / 2 * i - pol:: tr[root].val;
    }
    write(1ll * l * (l + 1) / 2 * r * (r + 1) / 2 - ans);
    return 0;
}

Luckyleaves's Blog

ZJOI2012 小蓝的好友

Solution

Code