hdu

题目链接：点击打开链接

思路：简单的线段树模板，理解了好久。创建+更新+查询。更新只涉及到区间更新次数（+1）即可。查询可以递归查询，累加包含查询结点的树结点（即离散化的区间[l,r]）的次数即可。简单的说就是，查询结点所在的区间更新次数的总和。

eg：离散化到树结点，若共有4个结点，更新区间[1,3]则更新到区间[1,2]+[3,3].

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

struct Node{
    int l,r;
    int sum;        //sum表示整个区间 [l,r] 被维护的次数。一定是整个区间，且被离散化到各个树结点的子区间
}node[400005];

void build(int id,int l,int r){
    node[id].l = l;
    node[id].r = r;
    node[id].sum = 0;
    if(l == r)
        return ;

    int mid = (l+r) >> 1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
}

void update(int id,int l,int r){
    if(node[id].l == l && node[id].r == r){
        node[id].sum++;
        return ;
    }

    int mid = node[id].l+node[id].r >> 1;
    if(r <= mid)   update(id*2,l,r);
    else if(l > mid)
        update(id*2+1,l,r);
    else{
        update(id*2,l,mid);
        update(id*2+1,mid+1,r);
    }
}

int ans;
void query(int id,int temp){
    ans += node[id].sum;

    if(node[id].l == node[id].r && node[id].l == temp)
        return ;

    int mid = (node[id].l + node[id].r) >> 1;
    if(temp <= mid) query(2*id,temp);
    else
        query(2*id+1,temp);
}
int main()
{
    int n;
    while(cin>>n,n != 0){
        int l,r;
        build(1,1,n);
        for(int i = 1;i <= n;i ++){
            scanf("%d%d",&l,&r);
            update(1,l,r);
        }
        for(int i = 1;i <= 15;i ++)
            cout<<node[i].l<<"  "<<node[i].r<<"  "<<node[i].sum<<endl;
        for(int i = 1;i <= n;i ++){
            if(i != 1)  cout<<" ";
            ans = 0;
            query(1,i);
            cout<<ans;
        }
        cout<<endl;
    }
    return 0;
}