about 4 years ago

线段树神题
有分块做法【时间复杂度貌似过不了……】和正常做法
1、分块
http://www.cnblogs.com/wmrv587/p/3843681.html orz
首先明确问题,对于每栋楼房的斜率K=H/X,问题就是问有多少个楼房的K比前面所有楼房的K都要大。

这题树套树当然可以,但是挺麻烦的,本渣觉得最简单就是分块……

将N个楼房分成T块,不断维护每个块内楼房的可视序列,如一个块内楼房的高度分别为(3 1 4 2 6 7)那么这个块内楼房的可视序列就是(3 4 6 7)(注意不同的块内是不干扰的,如第一个块可视序列为(3 4 6),第二块的序列可以是(5 7 8))

对于每个修改,我们只需对每个块内的楼房暴力维护可视序列就行了,O(N/T)

对于每个询问,我们只需一个块一个块看,不断维护到目前为止的可视序列中K的最大值kmax(不在可视序列内的楼房的K值一定不大),那么对于查询每个块的时候,可以二分可视序列找到第一个大于kmax的位置,若没有则这个块的所有楼房都不可见,如果存在,那么这个位置后的此块中的可视序列楼房都能看见,那么就更新答案和kmax,不断往后做

注意:毕竟时间比较紧,所以常数还是尽可能写小点,二分和max函数还是自己写好些,不然会爆RP……
2、正常一点的……
个人感觉有一点点类似于划分树的线段树……因为不要求原数列所以数组被规整成了sum。在每次修改的时候不断向后维护区间-->维护sum
hzc神犇的题解:http://blog.csdn.net/huzecong/article/details/9214307
设第i栋房子的高度为a_i。如果一栋房子可以被看到,即其斜率a_i/i比其前面所有的房子的斜率都要大。那么现在问题变成了,每次修改一个数字,问此时有多少数字比之前的数字都要大。

一种比较显然的O(Nlog^2N)做法是用线段树套平衡树……但是写起来挺蛋疼。事实上我们可以只用线段树完成这个任务。

一个显而易见的结论是,这种数字的值是单调递增的。我们修改一个数只会对这个数后面的数造成影响。考虑线段树划分出来的若干线段。这里有两种情况:

1、某个线段中的最大值小于等于修改的数,那么这个线段的贡献为0,无需处理

2、否则我们将这个线段分成两个并单独考虑,如果左侧的最大值大于修改的数,那么是不影响右侧的贡献的,只需递归处理左侧;否则就变成了第一种情况

那么我们就可以用线段树来解决这个问题了……复杂度好像是O(Nlog^2N)?但是常数巨小无比,而且非常好写……

代码中因为每一个节点对应的sum维护的信息都是不一样的,所以a[now].sum与a[now*2].sum+a[now*2+1].sum并不是完全等同的
calc那里需要注意……好好想想

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100001
using namespace std;
int n,m;
struct node
{
    double v;int sum;
}a[maxn*4];
inline int readln()
{
    char c=getchar();int bj=1,result=0;
    while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
    if (c=='-') c=getchar(),bj=-1;
    while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
    return bj*result;
}
inline int calc(int now,int left,int right,double value)
{
    if (left==right) return  a[now].v>value;
    int mid=(left+right)>>1;
    if (a[now*2].v<=value) return calc(now*2+1,mid+1,right,value);
    else return  a[now].sum-a[now*2].sum+calc(now*2,left,mid,value);
}
inline void change(int now,int left,int right,int pos,double value)
{
    if(left==right)
    {
        a[now].v=value;a[now].sum=1;
        return;
    } 
    int mid=(left+right)>>1;
    if (pos<=mid) change(now*2,left,mid,pos,value);
    else change(now*2+1,mid+1,right,pos,value);
    a[now].v=max(a[now*2].v,a[now*2+1].v); 
    a[now].sum=a[now*2].sum+calc(now*2+1,mid+1,right,a[now*2].v);
}
int main()
{
    n=readln();m=readln();
    for (int x,y,o=1;o<=m;o++)
    {
        x=readln();y=readln();
        change(1,1,n,x,y/(double)x);
        printf("%d\n",a[1].sum);
    }
}
← 【bzoj1007】【平几?】水平可见直线 【bzoj1020】【神剪枝】【二分】【几何新技能】安全的航线 →
 
comments powered by Disqus