线段树 HDU 4217 Data Structure? 单点更新 区间查询

链接：http://acm.hdu.edu.cn/showproblem.php?pid=4217

题意：就是让你输入一个N代表有1`n几个数，然后输入Q代表几次询问，每次询问输入一个K ,代表吧第K大的数删除。最后计算删除的数的大小~

代码

#include <stdio.h>
#include <string.h>
#define maxn 262145*4+5//一般开到最大的四倍大小就无压力~
__int64 count,sub;
struct node
{
    __int64 sum,count;
}tr[maxn];
void pushup(__int64 rt)
{
    tr[rt].sum = tr[rt<<1|1].sum + tr[rt<<1].sum;//对父节点的更新
}
void build(__int64 l,__int64 r,__int64 rt)
{
    if(l == r)
    {
        tr[rt].count = ++count;//这个为叶子节点，为叶子节点赋值
        tr[rt].sum = 1;
        return;
    }
    __int64 m;
    m = (l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pushup(rt);//更新节点
    return;
}
void delet(__int64 k,__int64 l,__int64 r,__int64 rt)
{
    if(l == r)
    {
        sub += tr[rt].count;//找到这个值，然后删除。
        tr[rt].sum = 0;
        return ;
    }

    __int64 m = (l+r)>>1;

    if(k > tr[rt<<1].sum)
    {
        k -= tr[rt<<1].sum;//如果大于做孩子的sum就把K值减小~
        delet(k,m+1,r,rt<<1|1);
    }
    else
    delet(k,l,m,rt<<1);
    pushup(rt);//删除后对节点的更新
    return;
}
int main()
{
    __int64 t,n,q,i,j,cas,k;
    scanf("%I64d",&t);
    cas = 0;
    while(t--)
    {
        count = sub = 0;
        scanf("%I64d %I64d",&n,&q);
        build(1,n,1);
        while(q--)
        {
            scanf("%I64d",&k);
            delet(k,1,n,1);
        }
        printf("Case %I64d: %I64d\n",++cas,sub);
    }
}