传送门 https://www.luogu.org/problemnew/show/P4198
蒟蒻渣渣禹看到这个题时十分不想写线段树emmmm
于是乎。。。。分块！！！
分块。思路就是：如果一个楼房能被看见，当且仅当它的房顶到(0,0)连线的斜率 比前面的都大。我们暴力维护每个块内斜率的最长上升序列，然后查询的时候二分找到块内第一个能看到的，那么它之后的所有最长上升序列里的元素就都能被看到，再去搜下一个块就好了。
下面我来讲下具体过程，我们要求的个数，就是斜率最长上升子序列，大家思考一下。。。显然成立。
我们设a，b以及他们的高度为h[a],h[b],如果a不会被b挡住，那么我们可以推出这样一个式子：h[a]/a >= h[b]/b，交叉相乘之后可得：h[a]b >= h[b]a。
对于原点的话我们只要判断h[a]是否大于0就行了。
修改：然后我们暴力更新块内元素信息，每次清零，重新维护块内最长上升序列长度。
查询：我们设last为上一个满足条件的块的末尾节点，那么从第一块开始到最后一块，在块内进行二分查找出与last相比刚满足条件的点，那么，从这个点一直到末尾均为合法序列，那么ans=这段序列的长度qwq，然后更新last为本块的末尾。
我们在暴力搞定每个块的递增数列，把这些斜率从小到大塞到一个栈里边（时间复杂度O(n/b)，b为块的大小）。
然后查找时从头开始，在每个块对应的栈中二分查找第一个斜率比前一个大的位置，这个位置和栈里面后边的位置都能被看到（时间复杂度O(blog(n/b))）。
总时间复杂度为O(n(n/b + blog(n/b)))≈O(n(n/b + blogn))。
这样一来b=√(n/logn)/2有奇效。想知道为什么么？
通过我巨水无比的计算，以及一次次试错试出的，不然会tle，除非你开o2，强烈建议用快读。
不用o2优化代码如下qwq
#include#include #include #include #define N 100005#define LL long longusing namespace std;;int n,m,b,h[N],p[N];struct stack { int s[N],top;}t[330];bool check(LL a,LL b) { if(!b) return h[a] > 0; return (LL)(h[a] * b) > (LL)(h[b] * a);}inline int read(){ int w=0; char ch; while(ch<'0'||ch>'9') { ch=getchar(); } while(ch>='0'&&ch<='9') { w=(w<<3)+(w<<1)+ch-'0'; ch=getchar(); } return w;}int main() { n=read(); m=read(); b = sqrt(n * log(n) / 2); for(register int i = 1;i <= n;i++) p[i] = (i - 1) / b + 1; while(m--) { int x,ans = 0; x=read(); h[x]=read(); register int l = (p[x] - 1) * b + 1,r = min(n,p[x] * b); t[p[x]].top = 0; for(register int i = l;i <= r;i++) if(check(i,t[p[x]].s[t[p[x]].top])) t[p[x]].s[++t[p[x]].top] = i; for(register int i = 1,last = 0;i <= p[n];i++) { register int q = 0; l = 1,r = t[i].top; while(l <= r) { register int mid = (l + r) >> 1; if(check(t[i].s[mid],last)){ q = mid; r = mid - 1; } else l = mid + 1; } if(q){ last = t[i].s[t[i].top]; ans += t[i].top - q + 1; } } printf("%d\n",ans); }}