【2018-国庆雅礼-NOIP-培训】 D2T2 蔬菜

发表于

题面在这里

这题暴力我居然拿了58分耶

暴力思路：

复杂度为 O(rcq) 都明白吧，这里要说的是一位大佬的做法—>这位大佬写了暴力+特判左上角为（1，1）的情况居然直接A了（果然咱连骗分都不会啊），代码的话明天要一下。

正解如下：

当蔬菜的出现次数较少时考虑平方的转化, 相当于计算有多少个 点对被询问区域包含, 实际上等价于四维偏序这个名词我也是第一次听qwq。

当蔬菜的出现次数较多时可以对每种蔬菜维护二维前缀和并根据定义计算答案;

综合分析两种算法的复杂的并选取合适的出现次数的分界值$k$ ,

复杂度为 $O(\frac{n^2}{k} (n^2 + q) + (n^2k + q) \log^3 n)$

取 $k = \sqrt{\frac{n^2+q}{\log^3 n}}$ 最优.

显然，这题不是那么好过的，反正这种题分类骗分讨论就可以了，标程写的很优美。

题解程序

这里先发标程，剩下的以后再发

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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <bits/stdc++.h>

using std::pair;
using std::vector;

typedef long long ll;
typedef pair<int, int> pii;

#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)

const int oo = 0x3f3f3f3f;

template <typename T> T read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x *= f;
}

const int K = 40;
const int N = 200;
const int Q = 100000;

int n, m, q;

struct BIT {
#define lowbit(x) (x & -x)
    int c[N + 5][N + 5][N + 5]; 

    void add(int x, int y, int z) 
    {
        for(int i = x; i <= m; i += lowbit(i))
            for(int j = y; j <= n; j += lowbit(j))
                for(int k = z; k <= m; k += lowbit(k))
                    c[i][j][k]++;
    }

    int query(int x, int y, int z) 
    {
        int res = 0;
        for(int i = x; i > 0; i -= lowbit(i))
            for(int j = y; j > 0; j -= lowbit(j))
                for(int k = z; k > 0; k -= lowbit(k))
                    res += c[i][j][k];
        return res;
    }
} bit;

struct query {
    int x1, y1, x2, y2, id;

    void input(int _id)
    {
        id = _id;
        read(x1), read(y1);
        read(x2), read(y2);
    }

    bool operator < (const query& rhs) const 
    {
        return x1 > rhs.x1;
    }
};

vector <int> d;
vector <query> mod;
vector <pii> p[Q + 5];

query que[Q + 5];
int ans[Q + 5], cnt[N*N + 5];
int a[N + 5][N + 5], b[N + 5][N + 5];

inline int pw2(int x) { return x * x; }

void calc(int col) 
{
    for(int i = 1; i <= n; ++i) 
    {
        for(int j = 1; j <= m; ++j) 
            b[i][j] = b[i][j-1] + (a[i][j] == col);
        for(int j = 1; j <= m; ++j) 
            b[i][j] = b[i][j] + b[i-1][j];
    }
    for(int i = 1; i <= q; ++i) 
    {
        int x1 = que[i].x1, y1 = que[i].y1;
        int x2 = que[i].x2, y2 = que[i].y2;

        ans[que[i].id] += pw2(b[x2][y2] - b[x1-1][y2] - b[x2][y1-1] + b[x1-1][y1-1]);
    }
}

void input() 
{
    read(n), read(m); read(q);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) 
            d.pb(read(a[i][j]));
    for(int i = 1; i <= q; ++i) 
        que[i].input(i);
}

void solve() 
{
    std::sort(d.begin(), d.end());
    d.erase(std::unique(d.begin(), d.end()), d.end());

    for(int i = 1; i <= n; ++i) 
        for(int j = 1; j <= m; ++j) 
        {
            a[i][j] = std::lower_bound(d.begin(), d.end(), a[i][j]) - d.begin();
            ++ cnt[a[i][j]];
            p[a[i][j]].pb(mp(i, j)); 
        }

    for(int i = 0; i < (int) d.size(); ++i) 
    {
        if(cnt[i] >= K) 
            calc(i);
        else 
        {
            for(auto x : p[i])
                for(auto y : p[i]) 
                {
                    query temp;
                    temp.x1 = x.fst, temp.y1 = x.snd;
                    temp.x2 = y.fst, temp.y2 = y.snd;
                    if(temp.x1 > temp.x2) 
                        std::swap(temp.x1, temp.x2);
                    if(temp.y1 > temp.y2) 
                        std::swap(temp.y1, temp.y2);

                    mod.pb(temp);
                }
        }
    }

    std::sort(que + 1, que + q + 1);
    std::sort(mod.begin(), mod.end());

    for(int i = 1, j = 0; i <= q; ++i) 
    {
        while(j < (int) mod.size() && mod[j].x1 >= que[i].x1) 
        {
            bit.add(m - mod[j].y1 + 1, mod[j].x2, mod[j].y2);
            ++ j;
        }
        ans[que[i].id] += bit.query(m - que[i].y1 + 1, que[i].x2, que[i].y2);
    }
    for(int i = 1; i <= q; ++i) 
        printf("%d\n", ans[i]);
}

int main() 
{
    input();
    solve();
    return 0;
}