看似完美无缺的东西也许是错解

动键盘之前一定再三思考

懵逼的 题目

传送至 BZOJ

扯淡的 题解

这道题…我写了三遍…

前两遍我没考虑到两棵常青树可能会空隙非常大, 直接统计然后GG

后来想了一下, 费尽千辛万苦克服懒惰推了一下式子, 发现在同一空隙的墓地对答案的贡献$ = \sum_i^{i\in[le, ri]} \mathrm C^{up}_{tot_i} \cdot \mathrm C^{down}_{tot_i} \cdot \mathrm C^{left}_{tot_j} \cdot \mathrm C^{right}_{tot_j} = C^{left}_{tot_j} \cdot \mathrm C^{right}_{tot_j} \cdot \sum_i^{i\in[le, ri]} \mathrm C^{up}_{tot_i} \cdot \mathrm C^{down}_{tot_i}$, 然后就转化为了一个区间求和, 单点修改的扫描线了Emmmmmmmmmmm但是为啥舒老师说这不是扫描线啊 这为啥不是扫描线啊QAQ

树状数组记录横向的$\mathrm C$值, 然后扫每一行的时候枚举相邻的两棵树, 计算这一段空隙对答案的贡献即可

复杂度$\mathrm O(n \lg n)$

注意细节:

  • 不要把枚举的两个树的纵坐标当成边界去查询了
  • 适当增长代码以提高可读性
  • 查询放在修改前面, 或者搞清楚变量的实际意义(比如dqy)
  • 不要一不小心把++dqy放在了continue后面

沙茶的 代码

/**************************************************************
    Problem: 1227
    User: Cansult
    Language: C++
    Result: Accepted
    Time:4460 ms
    Memory:24624 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN (100000 + 5)
#define MAXK (10 + 5)
#define MAXL (1000000000 + 5)
#define lowbit(x) ((x) & (-(x)))
#define LL long long
#define pll pair<LL, LL>
#define CA (2147483648ll)
using namespace std;
struct tree
{
    LL x, y, xx, yy;
}a[MAXN];
LL b[MAXN], c[MAXN][MAXK], n, chang, kuan, ans, sora[MAXN << 2];
LL tchang, tkuan, dq[MAXN], tot[MAXN], tto[MAXN], kn;
vector<int> bh[MAXN];
void xg(int wz, LL zh)
{
    for (int i = wz; i <= tchang; i += lowbit(i))
        b[i] += zh;
}
LL cx(int le, int ri)
{
    LL rel = 0, rer;
    for (int i = le - 1; i; i -= lowbit(i))
        rel = (rel + b[i]) % CA;
    rer = -rel;
    for (int i = ri; i; i -= lowbit(i))
        rer = (rer + b[i]), rer = (rer > 0 ? (rer % CA) : rer);
    return rer;
}
void initc()
{
    c[0][0] = 1;
    for (int i = 1; i < MAXN; i++)
        for (int j = 0; j < MAXK; j++)
            c[i][j] = (c[i - 1][j] + (j ? c[i - 1][j - 1] : 0)) % CA;
}
bool cmp(tree x, tree y)
{
    if (x.x == y.x) return x.y < y.y;
    else    return x.x < y.x;
}
void init()
{
    scanf("%lld%lld", &kuan, &chang);
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld", &a[i].xx, &a[i].yy);
        sora[++sora[0]] = a[i].xx;
        sora[++sora[0]] = a[i].yy;
    }
    sort(sora + 1, sora + sora[0] + 1);
    sora[0] = unique(sora + 1, sora + sora[0] + 1) - sora - 1;
    for (int i = 1; i <= n; i++)
        a[i].x = lower_bound(sora + 1, sora + sora[0] + 1, a[i].xx) - sora, 
        a[i].y = lower_bound(sora + 1, sora + sora[0] + 1, a[i].yy) - sora, 
        tchang = max(tchang, a[i].y), 
        tkuan = max(tkuan, a[i].x);
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; i++)
        bh[a[i].x].push_back(i), ++tot[a[i].x], ++tto[a[i].y];
    scanf("%lld", &kn);
}
void solve()
{
    for (int i = 1; i <= tkuan; i++)
    {
        int dqy = 0;
        for (int j = 1; j < bh[i].size(); j++)
        {
            tree& ri = a[bh[i][j]], le = a[bh[i][j - 1]];
            ++dqy;
            if (ri.yy == le.yy + 1)
                continue;
            LL dqsx = c[dqy][kn];
            dqsx = dqsx * c[tot[i] - dqy][kn] % CA;
            LL dqcx = cx(le.y + 1, ri.y - 1);
            ans = (ans + dqcx * dqsx % CA) % CA;
        }
        for (int j = 0; j < bh[i].size(); j++)
        {
            tree& x = a[bh[i][j]];
            LL dqzy = -((c[dq[x.y]][kn] * c[tto[x.y] - dq[x.y]][kn]) % CA);
            ++dq[x.y];
            dqzy += (c[dq[x.y]][kn] * c[tto[x.y] - dq[x.y]][kn]) % CA;
            dqzy %= CA;
            xg(x.y, dqzy);
        }   
    }
    printf("%lld\n", ans);
}
int main()
{
//  freopen("religious.in", "r", stdin);
//  freopen("religious.out", "w", stdout);
    initc();
    init();
    solve();
    return 0;
}

/*
5 6
13
0 2
0 3
1 2
1 3
2 0
2 1
2 4
2 5
2 6
3 2
3 3
4 3
5 2
2
*/

By 沙茶 Cansult