【题解】整体二分泛做

说是泛做其实就是多做了三道题?

博文内容的水分日渐增多.jpeg

$1$ LG1527 [国家集训队]矩阵乘法

给你一个 $N\times N$ 的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第 $K$ 小数。

把BIT换成二维的就做完了。

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
struct query{
int op, x, y, l, r, z ;
}q[MAXM], lq[MAXM], rq[MAXM] ;

int N, M, base[MAXN][MAXN] ;
int ans[MAXQ], _bit[MAXN][MAXN], cnt ;

il void upd(const int &p, const int &q, int x){
for (rg int i = p ; i <= N ; i += low(i))
for (rg int j = q ; j <= N ; j += low(j))
_bit[i][j] += x ;
}
il int ask(const int &p, const int &q){
int ret = 0 ;
if (!p || !q) return ret ;
for (rg int i = p ; i ; i -= low(i))
for (rg int j = q ; j ; j -= low(j))
ret += _bit[i][j] ;
return ret ;
}
void solve(int vl, int vr, int l, int r){
if (l > r) return ;
if (vl == vr){
for (int i = l ; i <= r ; ++ i)
if (q[i].op > 0) ans[q[i].op] = vl ;
return void() ;
}
rg int vmid = (vl + vr) >> 1, bl = 0, br = 0 ;
for (rg int i = l ; i <= r ; ++ i){
if (!q[i].op){
if (q[i].z <= vmid)
upd(q[i].x, q[i].y, 1), lq[++ bl] = q[i] ;
else rq[++ br] = q[i] ;
}
else {
int res = ask(q[i].l, q[i].r) ;
res -= ask(q[i].x - 1, q[i].r) ;
res -= ask(q[i].l, q[i].y - 1) ;
res += ask(q[i].x - 1, q[i].y - 1) ;
//cout << res << endl ;
if (res >= q[i].z) lq[++ bl] = q[i] ;
else q[i].z -= res, rq[++ br] = q[i] ;
}
}
for (rg int i = l ; i <= r ; ++ i)
if (!q[i].op && q[i].z <= vmid)
upd(q[i].x, q[i].y, -1) ;
for (rg int i = 1 ; i <= bl ; ++ i) q[l + i - 1] = lq[i] ;
for (rg int i = 1 ; i <= br ; ++ i) q[l + bl + i - 1] = rq[i] ;
solve(vl, vmid, l, l + bl - 1), solve(vmid + 1, vr, l + bl, r) ;
}

int main(){
cin >> N >> M ;
int n, x, y, l, r, k ;
for (int i = 1 ; i <= N ; ++ i)
for (int j = 1 ; j <= N ; ++ j)
q[++ cnt].op = 0, q[cnt].x = i,
q[cnt].y = j, scanf("%d", &q[cnt].z) ;
for (rg int i = 1 ; i <= M ; ++ i){
++ cnt, scanf("%d%d", &q[cnt].x, &q[cnt].y) ;
scanf("%d%d%d", &q[cnt].l, &q[cnt].r, &q[cnt].z), q[cnt].op = i ;
}/*
for (int i = 1 ; i <= cnt ; ++ i)
cout << q[i].x << " " << q[i].y << " " << q[i].l << " " << q[i].r << " " << q[i].z << endl ;*/
// cout << cnt << endl ;
solve(0, Inf, 1, cnt) ;
for (rg int i = 1 ; i <= M ; ++ i) printf("%d\n", ans[i]) ;
return 0 ;
}

$2$ LG4175 [CTSC2008]网络管理

给定一棵树,每次或者修改一个点的点权,或者查询两点之间的第 $k$ 大点权。

这东西是真的丧心病狂嗷233

发现写个树剖就变成傻题了。最终 $\log ^3$ 能过 $10^5$ 可能是医学奇迹叭。

贴个代码记录一下此时美好心情(毕竟写的很长.jpg

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
#define il inline
#define rg register
#define MAXN 500010

using namespace std ;

const int Inf = 100000001 ;

bool o[MAXN] ;
struct query{
int op, x, y, z ;
}q[MAXN], lq[MAXN], rq[MAXN] ;
int N, M, base[MAXN], ans[MAXN], cnt ;

namespace Mary{
struct Edge{
int to, next ;
}E[MAXN] ; int head[MAXN], cnt ;
int Id[MAXN], dfn[MAXN], top[MAXN], tot ;
int dep[MAXN], sz[MAXN], faa[MAXN], son[MAXN] ;
#define to(k) E[k].to
#define next(k) E[k].next
il void add(const int &u, const int &v){
to(++ cnt) = v, next(cnt) = head[u], head[u] = cnt ;
to(++ cnt) = u, next(cnt) = head[v], head[v] = cnt ;
}
void dfs(int u, int fa){
faa[u] = fa ;
sz[u] = 1, dep[u] = dep[fa] + 1 ;
for (int k = head[u] ; k ; k = next(k)){
if (to(k) == fa) continue ;
dfs(to(k), u), sz[u] += sz[to(k)] ;
if (!son[u] || sz[son[u]] < sz[to(k)]) son[u] = to(k) ;
}
}
void dfs(int u, int fa, int _top){
top[u] = _top, dfn[u] = ++ tot ;
if (son[u]) dfs(son[u], u, _top) ;
for (int k = head[u] ; k ; k = next(k))
if (to(k) != fa && to(k) != son[u]) dfs(to(k), u, to(k)) ;
}
int s[MAXN << 2] ;
void update(int rt, int l, int r, int p, int uv){
rg int mid = (l + r) >> 1 ;
if (l == r) return s[rt] += uv, void() ;
if (p <= mid) update(rt << 1, l, mid, p, uv) ;
else update(rt << 1 | 1, mid + 1, r, p, uv) ;
s[rt] = s[rt << 1] + s[rt << 1 | 1] ;
}
int query(int rt, int l, int r, int ql, int qr){
if (l >= ql && r <= qr) return s[rt] ;
rg int mid = (l + r) >> 1 ; rg int res = 0 ;
if (ql <= mid) res += query(rt << 1, l, mid, ql, qr) ;
if (qr > mid) res += query(rt << 1 | 1, mid + 1, r, ql, qr) ;
return res ;
}
int Query(int u, int v){
rg int ret = 0 ;
while (top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u, v) ;
ret += query(1, 1, N, dfn[top[u]], dfn[u]), u = faa[top[u]] ;
}
if (dfn[u] > dfn[v]) swap(u, v) ;
ret += query(1, 1, N, dfn[u], dfn[v]) ; return ret ;
}
}
void solve(int vl, int vr, int l, int r){
using namespace Mary ;
if (l > r) return ;
if (vl == vr){
for (int i = l ; i <= r ; ++ i)
if (q[i].op > 0) ans[q[i].op] = vr ;
return void() ;
}
rg int vmid = (vl + vr) >> 1, bl = 0, br = 0 ;
for (rg int i = l ; i <= r ; ++ i){
if (q[i].op == -1){
if (q[i].y > vmid)
update(1, 1, N, dfn[q[i].x], 1), rq[++ br] = q[i] ;
else lq[++ bl] = q[i] ;
}
else if (q[i].op == -2){
if (q[i].y > vmid)
update(1, 1, N, dfn[q[i].x], -1), rq[++ br] = q[i] ;
else lq[++ bl] = q[i] ;
}
else {
rg int res = 0 ;
res = Query(q[i].x, q[i].y) ;
if (res >= q[i].z) rq[++ br] = q[i] ;
else q[i].z -= res, lq[++ bl] = q[i] ;
}
}
for (rg int i = l ; i <= r ; ++ i)
if (q[i].op == -1 && q[i].y > vmid)
update(1, 1, N, dfn[q[i].x], -1) ;
else if (q[i].op == -2 && q[i].y > vmid)
update(1, 1, N, dfn[q[i].x], 1) ;
for (rg int i = 1 ; i <= bl ; ++ i) q[l + i - 1] = lq[i] ;
for (rg int i = 1 ; i <= br ; ++ i) q[l + bl + i - 1] = rq[i] ;
solve(vl, vmid, l, l + bl - 1), solve(vmid + 1, vr, l + bl, r) ;
}
int main(){
int l, r, k, u, v ;
ios::sync_with_stdio(0) ;
cin.tie(0), cout.tie(0), cin >> N >> M ;
for (rg int i = 1 ; i <= N ; ++ i) cin >> base[i] ;
for (rg int i = 1 ; i < N ; ++ i) cin >> u >> v, Mary :: add(u, v) ;
// cout << 23333 << endl ;
Mary :: dfs(1, 0) ;
Mary :: dfs(1, 0, 1), cnt = 0 ;
// cout << 23333 << endl ;
for (rg int i = 1 ; i <= N ; ++ i)
q[++ cnt].y = base[i],
q[cnt].x = i, q[cnt].op = -1 ;
for (rg int i = 1 ; i <= M ; ++ i){
cin >> k ;
if (k)
cin >> l >> r,
q[++ cnt].op = i, o[i] = 1,
q[cnt].x = l, q[cnt].y = r, q[cnt].z = k ;
else {
cin >> l >> r ;
q[++ cnt].y = base[l],
q[cnt].x = l, q[cnt].op = -2 ;
q[++ cnt].y = (base[l] = r),
q[cnt].x = l, q[cnt].op = -1 ;
}
}
// cout << 23333 << endl ;
solve(0, Inf, 1, cnt) ;
// cout << 23333 << endl ;
for (int i = 1 ; i <= M ; ++ i)
if (!o[i]) continue ;
else if (!ans[i])
cout << "invalid request!" << '\n' ;
else cout << ans[i] << '\n' ;
// cout << 23333 << endl ;
return 0 ;
}

$3$ [POI2011] Meteors

给定一个环,每个节点有一个所属国家,$k$ 次事件,每次对 $[l,r]$ 区间上的每个点点权加上一个值,求每个国家最早多少次操作之后所有点的点权和能达到一个值。

据蒋神说有 $1\log$ 的写法,然而并不想去学,等抽个空补上吧(

还是整体二分,二分时间。怎么说呢,这道题比之前做的题要灵活一点。考虑二分时间本质上就是在二分操作,所以只需要执行 $[vl,vmid]$ 内的操作就可以了。发现这样需要分治的是国家,查询的话拿一个vector+BIT差分维护一下即可。

感觉…就是还欠火候。明明每一部分都了解得一清二楚,明明每一部分都知道该怎么写,但是却串接不起来…wtcl

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
const int N = 300010 ;
const int Inf = 191981000 ;

vector <int> _be[N] ;
struct met{
int l, r, v, id ;
}q[N] ; int t[N], lt[N], rt[N] ;
int n, m, k, s[N], b[N], _bit[N << 1], ans[N] ;

void upd(int p, int x){
for ( ; p <= 2 * m ; p += low(p)) _bit[p] += x ;
}
int ask(int p){
int ret = 0 ; for ( ; p ; p -= low(p)) ret += _bit[p] ; return ret ;
}
int query(int p){
int ret = 0 ;
for (int i = 0 ; i < _be[p].size() ; ++ i){
ret += ask(_be[p][i]) + ask(_be[p][i] + m) ;
if (ret >= s[p]) break ;
}
return ret ;
}
void solve(int vl, int vr, int l, int r){
if (l > r) return ;
if (vl == vr){
for (int i = l ; i <= r ; ++ i)
ans[t[i]] = vl ; return void() ;
}
int vmid = (vr + vl) >> 1, fl = 0, fr = 0 ;
for (int i = vl ; i <= vmid ; ++ i)
upd(q[i].l, q[i].v), upd(q[i].r + 1, -q[i].v) ;
for (int i = l ; i <= r ; ++ i){
int res = query(t[i]) ;
if (res >= s[t[i]]) lt[++ fl] = t[i] ;
else s[t[i]] -= res, rt[++ fr] = t[i] ;
}
for (int i = vl ; i <= vmid ; ++ i)
upd(q[i].l, -q[i].v), upd(q[i].r + 1, q[i].v) ;
for (int i = 1 ; i <= fl ; ++ i) t[i + l - 1] = lt[i] ;
for (int i = 1 ; i <= fr ; ++ i) t[i + l + fl - 1] = rt[i] ;
solve(vl, vmid, l, l + fl - 1) ; solve(vmid + 1, vr, l + fl, r) ;
}
signed main(){
cin >> n >> m ;
for (int i = 1 ; i <= m ; ++ i)
scanf("%lld", &b[i]), _be[b[i]].pb(i) ;
for (int i = 1 ; i <= n ; ++ i) t[i] = i ;
for (int i = 1 ; i <= n ; ++ i) scanf("%lld", &s[i]) ;
cin >> k ;
for (int i = 1 ; i <= k ; ++ i)
scanf("%lld%lld%lld", &q[i].l, &q[i].r, &q[i].v),
q[i].r += (q[i].l > q[i].r) ? m : 0, q[i].id = i ;
q[++ k].l = 1, q[k].r = 2 * m, q[k].id = k, q[k].v = Inf ;
solve(1, k, 1, n) ;
for (int i = 1 ; i <= n ; ++ i)
if (ans[i] == k) puts("NIE") ; else printf("%lld\n", ans[i]) ;
return 0 ;
}