第一次 r a n k 1 rank1 rank1 有点激动 q w q qwq qwq
T1 query签到题，求区间等于 x x x 的数的个数。考虑树状数组，对于一个区间 [ L , R ] [L, R] [L,R] 考虑算出小于等于 L − 1 L - 1 L−1 中等于 x x x 的数的个数记为 a a a，和小于等于 R R R 中的等于 x x x 的数的个数记为 b b b 然后答案就是 a n s = b − a ans = b - a ans=b−a。然后我们又发现等于 x x x 的数的个数等于小于等于 x x x 的数的个数减去小于等于 x − 1 x - 1 x−1 的数的个数。然后就跑两遍一维数点就过了。
#includeT2 paintusing namespace std; #define in read() #define MAXN 200200 inline int read(){ int x = 0; char c = getchar(); while(c < '0' or c > '9') c = getchar(); while('0' <= c and c <= '9'){ x = x * 10 + c - '0'; c = getchar(); } return x; } int a[MAXN] = { 0 }; int n = 0; int q = 0; int c[MAXN * 4] = { 0 }; struct Tq{ int l, r, x; int ans, idx; }qs[MAXN]; bool comp1(Tq a, Tq b) { return a.l < b.l; } bool comp2(Tq a, Tq b) { return a.r < b.r; } bool comp3(Tq a, Tq b) { return a.idx < b.idx; } inline int lowbit(int x) { return x & -x; } void add(int x){ for(; x <= n; x += lowbit(x)) c[x]++; } int query(int x){ int ans = 0; for(; x; x -= lowbit(x)) ans += c[x]; return ans; } int main(){ freopen("query.in", "r", stdin); freopen("query.out", "w", stdout); n = in; for(int i = 1; i <= n; i++) a[i] = in; q = in; for(int i = 1; i <= q; i++) qs[i].l = in, qs[i].r =in, qs[i].x = in, qs[i].idx = i; int j = 1; sort(qs + 1, qs + q + 1, comp1); for(int i = 1; i <= n; i++){ add(a[i]); while(qs[j].l < i + 1 and j <= q) j++; while(qs[j].l == i + 1 and j <= q){ int a = query(qs[j].x) - query(qs[j].x - 1); qs[j].ans -= a; j++; } } memset(c, 0, sizeof(c)); j = 1; sort(qs + 1, qs + q + 1, comp2); for(int i = 1; i <= n; i++){ add(a[i]); while(qs[j].r < i and j <= q) j++; while(qs[j].r == i and j <= q){ int a = query(qs[j].x) - query(qs[j].x - 1); qs[j].ans += a; j++; } } sort(qs + 1, qs + q + 1, comp3); for(int i = 1; i <= q; i++) cout << qs[i].ans << 'n'; return 0; }
考场上的玄学做法竟然没有 T L E TLE TLE，（虽然有一个点是卡着 1 s 1s 1s 过的）。显然可以 O ( n m ) O(nm) O(nm) 预处理出每一个色块的边界，然后枚举所有色块，统计这个色块被哪些颜色覆盖过了。这些覆盖了这个色块的颜色显然就不是最先放下去的颜色。所以我们开一个桶存储一下，然后最后统计一遍就是答案了。
注意这个做法在正常地图只有一个颜色的时候是错的，所以要特判一下是否整张地图都只有一个颜色，如果是直接输出 k − 1 k - 1 k−1 （就是因为这里少了 10 p t s 10 pts 10pts）。
#includeusing namespace std; #define in read() #define MAXN 100100 #define INFI 1 << 30 inline int read(){ int x = 0; char c = getchar(); while(c < '0' or c > '9') c = getchar(); while('0' <= c and c <= '9'){ x = x * 10 + c - '0'; c = getchar(); } return x; } int n = 0; int m = 0; int k = 0; struct Tnode{ int sx, sy; int tx, ty; int ts, tt; }tag[MAXN]; int fa[MAXN] = { 0 }; int main(){ freopen("paint.in", "r", stdin); freopen("paint.out", "w", stdout); n = in; m = in; k = in; int cnt = 0; if(n == 1 and m == 1) { cout << k - 1 << 'n'; return 0; } // 事后知道只有一个颜色的样例就只有一个点，所以直接这样写了 qwq for(int i = 1; i <= k; i++) fa[i] = i; int c[n + 10][m + 10]; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) c[i][j] = in; for(int i = 1; i <= k; i++) tag[i].sx = tag[i].sy = INFI, tag[i].tx = tag[i].ty = -INFI; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){ tag[c[i][j]].sx = min(tag[c[i][j]].sx, i); tag[c[i][j]].sy = min(tag[c[i][j]].sy, j); tag[c[i][j]].tx = max(tag[c[i][j]].tx, i); tag[c[i][j]].ty = max(tag[c[i][j]].ty, j); } for(int x = 1; x <= k; x++){ if(tag[x].sx == INFI) continue; for(int i = tag[x].sx; i <= tag[x].tx; i++) for(int j = tag[x].sy; j <= tag[x].ty; j++) if(c[i][j] != x and fa[c[i][j]] == c[i][j]) cnt++, fa[c[i][j]] = 0; } cout << k - cnt << 'n'; return 0; }
我们考虑优化这个做法，如果
n
>
m
n > m
n>m 我们就交换
n
n
n 和
m
m
m 这样可以保证
n
<
m
n < m
n 一个不确定的数组，每次约束条件是区间模
p
p
p 和，让你判断是否与前面的矛盾。容易想到做一个前缀和，但是数组不确定所以我们假设已经做了一个前缀和记为
s
s
s。那么每次的约束条件就可以写成：
s
r
−
s
l
−
1
≡
k
(
m
o
d
p
)
s_r - s_{l - 1} equiv k pmod p
sr−sl−1≡k(modp) 然后移一下项就可以得到：
s
r
≡
s
l
−
1
+
k
(
m
o
d
p
)
s_r equiv s_{l - 1} +k pmod p
sr≡sl−1+k(modp) 于是题目就转化成了有
m
m
m 个像这样：
s
j
≡
s
i
+
k
(
m
o
d
p
)
s_j equiv s_i + k pmod p
sj≡si+k(modp) 的约束条件，判断每一个条件是否与前面所有的条件矛盾。我们发现当给出的
(
s
j
,
s
i
)
(s_j, s_i)
(sj,si) 都两两不同的时候是绝对不会有矛盾的，所以只需要考虑有相同的时候是否矛盾。这就可以想到用带权并查集来维护信息。 具体的，对于一个式子：
s
i
≡
s
j
+
k
1
(
m
o
d
p
)
s_i equiv s_j + k_1 pmod p
si≡sj+k1(modp) 我们连一条由
j
j
j 指向
i
i
i 的边，其边权为
k
1
k_1
k1。根据我们上面的表述，当且仅当这个并查集里成环的时候我们才与要判断是否矛盾。并查集如果现在长这样： 也就是说有两个约束条件：
{
s
i
≡
s
j
+
k
1
(
m
o
d
p
)
s
i
≡
s
n
+
k
2
(
m
o
d
p
)
begin{cases} s_i equiv s_j + k_1 pmod p \ s_i equiv s_n +k_2 pmod p end{cases}
{si≡sj+k1(modp)si≡sn+k2(modp) 经过一些变换我们能得到：
s
j
+
k
1
≡
s
n
+
k
2
(
m
o
d
p
)
→
s
j
≡
s
n
+
(
k
2
−
k
1
)
(
m
o
d
p
)
s_j + k_1 equiv s_n +k_2 pmod p rightarrow s_j equiv s_n + (k_2 - k_1)pmod p
sj+k1≡sn+k2(modp)→sj≡sn+(k2−k1)(modp) 这个时候如果有一个新的约束条件：
s
j
≡
s
n
+
k
′
s_j equiv s_n + k'
sj≡sn+k′ 加进来，也就是把并查集变成这样： 我们就只需要判断
k
′
k'
k′ 是否等于
k
2
−
k
1
k_2 - k_1
k2−k1 就可以了，不用真的把
k
′
k'
k′ 这条边加进去。 然后就结束了。 考虑线性
d
p
dp
dp，设
f
i
f_i
fi 表示引爆第
i
i
i 个炸弹且炸弹
i
i
i 左边的所有炸弹都炸的最小能量。
g
i
g_i
gi 表示引爆第
i
i
i 个炸弹且炸弹
i
i
i 右边的所有炸弹都炸的最小能量。那么答案就是：
a
n
s
=
min
i
=
1
n
{
max
(
f
i
,
g
i
)
}
ans = min_{i = 1}^nleft{max( f_i, g_i ) right}
ans=i=1minn{max(fi,gi)} 现在我们考虑如何计算
f
i
f_i
fi（
g
i
g_i
gi 同理）。显然有：
f
i
=
min
j
=
1
i
−
1
{
max
(
3
f
j
2
,
a
i
−
a
j
)
}
f_i = min_{j = 1}^{i - 1} { max( frac{3f_j}{2}, a_i - a_j ) }
fi=j=1mini−1{max(23fj,ai−aj)} 意思就是枚举
j
j
j 找到能引爆
j
j
j 的能量（也就是
a
i
−
a
j
a_i - a_j
ai−aj） 和能引爆
j
j
j 左边的所有的最小值（也就是
3
f
j
2
frac{3f_j}{2}
23fj）的能量最大值，然后再找出其中的最小值就是
f
i
f_i
fi。同理我们有：
g
i
=
min
j
=
i
+
1
n
{
max
(
3
f
j
2
,
a
j
−
a
i
)
}
g_i = min_{j = i + 1}^n { max ( frac{3f_j}{2}, a_j - a_i ) }
gi=j=i+1minn{max(23fj,aj−ai)} 这两个式子都是
O
(
n
2
)
O(n^2)
O(n2) 的，所以暴力计算可以得到
60
p
t
s
60 pts
60pts。 考虑如何优化，我们发现对于每一次的
a
i
−
a
j
a_i - a_j
ai−aj 都是单调递减的，画出来就是一条从左上画到右下的斜线，而
3
f
j
2
frac{3f_j}{2}
23fj 是单调递增的，就是左下到右上的线。所以我们发现这俩的
max
max
max 的最小值肯定在这两条线的交点的两边最近的地方取到，而且对于每一次的查询
f
j
f_j
fj 这条线不会变，每次就是
a
j
−
a
i
a_j - a_i
aj−ai 这条线像下平移，所以我们只需要
O
(
n
)
O(n)
O(n) 每次维护出这两条线每一次的交点然后就能
O
(
n
)
O(n)
O(n) 求出这个式子了。// std 代码
#include
T3 seq
#include
T4 bomb
