Cansult's blog

即使愿望永远无法实现
我也不愿就这样放手

0%

水题笔记 SDOI2009 虔诚的墓主人[树状数组, 扫描线]

Posted on Edited on In

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

动键盘之前一定再三思考

懵逼的 题目

传送至 BZOJ

扯淡的 题解

这道题...我写了三遍...

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

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

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

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

注意细节:

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

沙茶的 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/**************************************************************
    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