HDU 4831 Scenic Popularity （段树）

Scenic Popularity

Problem Description

　　临近节日，度度熊们近期计划到室外游玩公园。公园内部包含了非常多的旅游景点区和歇息区，因为旅游景点非常热门，导致景点区和歇息区都聚集了非常多人。所以度度熊在旅游之前想通过百度地图查看一下公园内各个地方的热门程度。
　　假设全部景点区和歇息区都是X轴直线上的一系列顶点，所相应的坐标X_i 保证唯一。每一个景点区有个初始的热度值，而一个歇息区(坐标为X_i)的热度值等于离它距离近期的景点区X_j的热度值（距离定义为|X_i-X_j|）。假设此歇息区与两个景点区的距离一样。则歇息区的热度值选择两个景点区中的热度值最大值。假设两个热度值都一样，则任意选择当中一个。
　　度度熊在出门之前会常常去查看百度地图，每次查看前会有某些景点区的热度值已发生改变，从而也会导致周围的歇息区的热度值发生改变，然后度度熊想知道当前热度值<=R_k的顶点(包含景点区和歇息区)有多少个

Input

　　输入数据的第一行是測试Case的个数(T<=100）。
　　每一个Case的第一行是N(0<N<=10000)，表示景点区和歇息区的总数。
　　接着会有N行数据，每一列首先是顶点的X坐标Xi (0< X_i <=1e8)，第二列是一个整数H_i(0=<H_i <=100000)，假设H_i 不为0。则表示当前顶点为风景区且初始的热度值为H_i，否则表示当前顶点为歇息区。这N行数据会依照坐标Xi递增的方式依次给出。

　　接着的一行数据是操作的次数K(K<=100)，最后会有K行数据，每一行的第一列要么是’U’或者’Q’，’U’表示当前操作为更改热度操作。’Q’表示当前操作为查询操作。假设是更改操作，接着会有两列数据，各自是热度值要改变的风景区的下标L_k(0<=L_k<N)以及改变后的热度值V_k(0< V_k<=100000)；假设是查询操作，第二列是要查询的热度范围R_k(0< R_k<=100000)

Output

　　对于第k组測试数据，第一行输出Case #k:。接下来对每次查询操作(即Q操作)会输出一个整数，表示满足条件的顶点数有多少个

Sample Input

Sample Output

Case #1:
4
2

Source

2014年百度之星程序设计大赛 - 初赛（第二轮）

题目大意：

T组測试数据，每组首先一个n表示旅游区和歇息区共同拥有 n个。

接下来是n行介绍，每行两个数字，第一个表示位置。第二个表示热度，假设热度为0表示歇息区。否则为景区。歇息区的热度与近期景区的热度同样，假设（左边和右边）两个景区距离同样。歇息区的热度取热度高的。

经接着m，表示m组询问，Q x 。表示热度小于等于x的有多少个。

U 表示改变某个景区的热度。

解题思路：

对于Q操作的询问，非常明显是维护的一个前缀和，因此想到用线段树维。可是U操作非常复杂。要维护差量计算。

解题代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int maxn=110000;
int pos[maxn],value[maxn],lson[maxn],rson[maxn],n;

struct node{
    int l,r,sum;
}a[maxn*4];

void build(int l,int r,int k){
    a[k].l=l;
    a[k].r=r;
    a[k].sum=0;
    if(l<r){
        int mid=(l+r)/2;
        build(l,mid,2*k);
        build(mid+1,r,2*k+1);
    }
}

void insert(int l,int r,int k,int c){
    //if(k==1) cout<<"insert:"<<l<<" "<<r<<" "<<c<<" "<<endl;
    if(l<=a[k].l && a[k].r<=r){
        a[k].sum+=c;
    }else{
        int mid=(a[k].l+a[k].r)/2;
        if(r<=mid) insert(l,r,2*k,c);
        else if(l>=mid+1) insert(l,r,2*k+1,c);
        else{
            insert(l,mid,2*k,c);
            insert(mid+1,r,2*k+1,c);
        }
        a[k].sum=a[2*k].sum+a[2*k+1].sum;
    }
}

int query(int l,int r,int k){
    if(l<=a[k].l && a[k].r<=r){
        return a[k].sum;
    }else{
        int mid=(a[k].l+a[k].r)/2;
        if(r<=mid) return query(l,r,2*k);
        else if(l>=mid+1) return query(l,r,2*k+1);
        else return query(l,mid,2*k)+query(mid+1,r,2*k+1);
    }
}

void findlson(int k){
    if(k<=0) lson[k]=-1;
    else{
        if(value[k-1]==0) lson[k]=lson[k-1];
        else lson[k]=k-1;
    }
}

void findrson(int k){
    if(k>=n-1) rson[k]=-1;
    else{
        if(value[k+1]==0) rson[k]=rson[k+1];
        else rson[k]=k+1;
    }
}

void input(){
    build(0,110000,1);
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&pos[i],&value[i]);
        lson[i]=-1;
        rson[i]=-1;
    }
    for(int i=0;i<n;i++){
        if(value[i]==0) findlson(i);
    }
    for(int i=n-1;i>=0;i--){
        if(value[i]==0) findrson(i);
    }
    for(int i=0;i<n;i++){
        if(value[i]==0){
            if( lson[i]==-1 && rson[i]==-1 ) insert(0,0,1,1);
            if( lson[i]!=-1 && rson[i]==-1 ) insert(value[lson[i]],value[lson[i]],1,1);
            if( lson[i]==-1 && rson[i]!=-1 ) insert(value[rson[i]],value[rson[i]],1,1);
            if( lson[i]!=-1 && rson[i]!=-1 ){
                int l0=lson[i],r0=rson[i];
                if(pos[i]-pos[l0] <pos[r0]-pos[i] ) insert(value[l0],value[l0],1,1);
                else if(pos[i]-pos[l0] > pos[r0]-pos[i] ) insert(value[r0],value[r0],1,1);
                else{
                    insert(max(value[r0],value[l0]),max(value[r0],value[l0]),1,1);
                }
            }
        }else{
            insert(value[i],value[i],1,1);
        }
    }
}


void solve(){
    int m;
    scanf("%d",&m);
    while(m-- >0){
        char ch;
        cin>>ch;
        if(ch=='Q'){
            int c;
            scanf("%d",&c);
            cout<<query(0,c,1)<<endl;
        }else{
            int k,c;
            scanf("%d%d",&k,&c);
            insert(c,c,1,1);
            insert(value[k],value[k],1,-1);
            if(value[k]!=c){
                for(int i=k-1;i>=0;i--){
                    if(value[i]!=0) continue;
                    if(rson[i]!=k) break;
                    if(lson[i]==-1){
                        insert(c,c,1,1);
                        insert(value[k],value[k],1,-1);
                    }else{
                        int l0=lson[i],r0=rson[i];
                        if(pos[i]-pos[l0] > pos[r0]-pos[i] ){
                            insert(c,c,1,1);
                            insert(value[k],value[k],1,-1);
                        }
                        if(pos[i]-pos[l0] == pos[r0]-pos[i] ){
                            insert( max(value[r0],value[l0]) , max(value[r0],value[l0]) ,1,-1);
                            insert( max(c,value[l0]) , max(c,value[l0]) ,1,1);
                        }
                    }
                }
                for(int i=k+1;i<n;i++){
                    if(value[i]!=0) continue;
                    if(lson[i]!=k) break;
                    if(rson[i]==-1){
                        insert(c,c,1,1);
                        insert(value[k],value[k],1,-1);
                    }else{
                        int l0=lson[i],r0=rson[i];
                        if(pos[i]-pos[l0] < pos[r0]-pos[i] ){
                            insert(c,c,1,1);
                            insert(value[k],value[k],1,-1);
                        }
                        if(pos[i]-pos[l0] == pos[r0]-pos[i] ){
                            insert( max(value[r0],value[l0]) , max(value[r0],value[l0]) ,1,-1);
                            insert( max(c,value[r0]) , max(c,value[r0]) ,1,1);
                        }
                    }
                }
            }
            value[k]=c;
        }
    }
}

int main(){
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        input();
        printf("Case #%d:
",i);
        solve();
    }
    return 0;
}