题意
题目链接 https://www.luogu.org/problemnew/show/P4198
Sol
别问我为什么发两遍 就是为了骗访问量
这个题的线段树做法,, 妙的很
首先一个显然的结论: 位置 \(i\) 能被看到当且仅当 \(\frac{H_k}{k} <\frac{H_i}{i}, k < i\)
考虑直接维护区间 \([l, r]\) 的可以被看到的点.
因为只有单点修改, 因此只需考虑如何合并两个区间即可
维护区间内 \(\frac{H_i}{i}\) 的最大值, 设其为 \(mx\)
首先左孩子的答案可以直接加上, 考虑左孩子对右孩子的贡献, 如果 \(mx_{ls}> mx_{rs}\), 那么右孩子的答案为 0.
否则考虑右孩子的左孩子的贡献, 如果 \(mx_{rs_{ls}}> mx_{ls}\), 直接加上右孩子的右孩子在右孩子的左孩子的影响下的贡献 (差分一下), 递归右孩子的左孩子. 否则左孩子的贡献为 0, 递归右孩子
其实写起来还是挺好写的, 复杂度 \(O(nlog^2n)\)
- #include<bits/stdc++.h>
- using namespace std;
- const int MAXN = 1e6 + 10;
- inline int read() {
- char c = getchar(); int x = 0, f = 1;
- while(c <'0' || c> '9') {if(c == '-') f = -1; c = getchar();}
- while(c>= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
- return x * f;
- }
- int N, M, a[MAXN];
- int sum[MAXN], ls[MAXN], rs[MAXN], ll[MAXN], rr[MAXN], tot, root;
- double mx[MAXN];
- int find(double lim, int k) {
- if(ll[k] == rr[k]) return mx[k]> lim;
- int mid = ll[k] + rr[k]>> 1;
- if(mx[ls[k]]> lim) return sum[k] - sum[ls[k]] + find(lim, ls[k]);
- else return find(lim, rs[k]);
- }
- void update(int k) {
- sum[k] = sum[ls[k]];
- mx[k] = max(mx[ls[k]], mx[rs[k]]);
- if(mx[ls[k]]> mx[rs[k]]) return ;
- sum[k] += find(mx[ls[k]], rs[k]);
- }
- void Modify(int &k, int l, int r, int p, double v) {
- if(!k) k = ++tot, ll[k] = l, rr[k] = r;
- if(l == r) {sum[k] = 1; mx[k] = v; return ;}
- int mid = l + r>> 1;
- if(p <= mid) Modify(ls[k], l, mid, p, v);
- else Modify(rs[k], mid + 1, r, p, v);
- update(k);
- }
- signed main() {
- N = read(); M = read();
- for(int i = 1; i <= M; i++) {
- int x = read(), y = read();
- Modify(root, 1, N, x, (double) y / x);
- printf("%d\n", sum[root]);
- }
- return 0;
- }
- /*
- 3 4
- 2 4
- 3 6
- 1 1000000000
- 1 1
- */
来源: http://www.bubuko.com/infodetail-2946944.html