FZOJ 182 - 定价

堆题果然一般都是思维题和细节题……

这题其实就是一个进位题,只不过加了无数限制。

首先,进位可以表示为:从高往低,找到第一个不能为 $1$ 位,往前找到一个可以为 $1$ 并且此时不为 $1$ 的位,将其置为 $1$ ,将其后的位置为 $0$ 。

复杂度要求应该是 $O(nq \log n)$ 的,这就要求单次 $O(n \log n)$ 的查询复杂度,需要对上面进行优化。

不难发现此时不为 $1$ 的位是可以预处理出来的:对每一位必然存在多个可行区间,超过可行区间即不能再放 $1$ 。利用珂朵莉树维护这个区间,这里的珂朵莉树复杂度是严格 $O(q)$ 的。

那么开始模拟进位的过程,需要一个堆来维护每一位 $1$ 的可行区间。

  • 维护出上一位的 $1$ 位;

  • 查询当前位哪些必须从 $0$ 置 $1$ ,找到最高的那一位 $m$ ;将这些位置 $0$ ,且将他们从堆中删除;

  • 往前找没有置 $1$ 且可以置 $1$ 的位,将其置 $1$ ,将其可行区间加入堆;否则无解;

  • 继续下一位。

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <set>
#include <queue>
#include <unordered_map>
#include <vector>

#define MAXN 1010

using namespace std;

typedef set<pair<int, int>>::iterator it;
typedef set<int>::iterator jt;
typedef long long lint;

const int mod = 1e9 + 7;
unordered_map<int, set<pair<int, int>>> column;
set<int> row[MAXN], bits;

int n, m, q;

struct heap {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> p, q;

void push(pair<int, int> x) {
p.push(x);
}

void pop(pair<int, int> x) {
q.push(x);
}

void clear() {
while (!q.empty())
q.pop();
while (!p.empty())
p.pop();
}

bool empty() {
return q.size() == p.size();
}

pair<int, int> top() {
while (!q.empty() && p.top() == q.top()) {
q.pop();
p.pop();
}
return p.top();
}
}candinates;

int read() {
char c = getchar();
int x = 0;
while (!isdigit(c))
c = getchar();
while (isdigit(c)) {
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return x;
}

void unavailable(int r, int c) {
row[r].erase(c);
it i = column[c].lower_bound(make_pair(r, 0));
if (i == column[c].end() || i -> first != r)
--i;
int u = i -> first, v = i -> second;
column[c].erase(i);
if (u != r)
column[c].insert(make_pair(u, r - 1));
if (v != r)
column[c].insert(make_pair(r + 1, v));
}

void available(int r, int c) {
row[r].insert(c);
it i = column[c].lower_bound(make_pair(r, 0));
int u = r, v = r;
if (i != column[c].begin()) {
it j = i;
--j;
while (j -> second == u - 1) {
u = j -> first;
if (j == column[c].begin()) {
column[c].erase(j);
break;
}
column[c].erase(j--);
}
}
it j = i;
while (j != column[c].end() && j -> first == v + 1) {
v = j -> second;
column[c].erase(j++);
}
column[c].insert(make_pair(u, v));
}

lint power(lint a, int b) {
lint res = 1;
while (b) {
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}

int get(int r, int c) {
it i = column[c].lower_bound(make_pair(r, 0));
if (i == column[c].end() || i -> first != r)
--i;
return i -> second;
}

lint solve() {
bits.clear();
candinates.clear();
lint sum = 0, ans = 0;
for (int i = 1; i <= n; ++i) {
int maxi = 0;
while (!candinates.empty() && candinates.top().first < i) {
maxi = max(maxi, candinates.top().second);
candinates.pop(candinates.top());
}
bool isfail = false;
while (true) {
jt j = row[i].upper_bound(maxi);
if (j == row[i].end()) {
isfail = true;
break;
}
while(!bits.empty() && *bits.begin() < *j) {
int cur = *bits.begin();
sum = (sum - power(2, cur - 1) + mod) % mod;
bits.erase(cur);
int pos = get(i - 1, cur);
if (pos != i - 1)
candinates.pop(make_pair(pos, cur));
}
if (bits.empty() || *bits.begin() != *j) {
int cur = *j;
sum = (sum + power(2, cur - 1)) % mod;
bits.insert(cur);
int pos = get(i, cur);
candinates.push(make_pair(pos, cur));
break;
}
else
maxi = *j;
}
if (isfail)
return -1;
ans = (ans + sum) % mod;
}
return ans;
}

int main() {
n = read();
m = read();
q = read();
while (q--) {
int opt = read();
if (opt == 1) {
int r = read(), c = read();
c = m - c + 1;
if (row[r].count(c))
unavailable(r, c);
else
available(r, c);
}
else
printf("%lld\n", solve());
}
}