当前位置: 首页 > 工具软件 > Status HUD > 使用案例 >

hud 4288

洪高刚
2023-12-01

题目大意:有以下三种操作:add x添加一个数x并且保证之前没有这个数,del x删除一个数x并且保证之前有这个数,输出所有数中下标对5取摸为3的数的和;(所有的数按照从小到大的顺序排序);

分析:(刚开始做这道题确实没什么思路,虽然知道是用线段树做,但是就是想不出节点的权值应该怎么设定,想了一天,最后还是看了题解(鄙视一下自己。。。):

http://blog.csdn.net/qingniaofy/article/details/7985933)其实也很简单,每个节点只需要记录两个东西,一个是自己这一段中间数的数量,之后结构体中有个sum[5]数组,用于记录这个节点所表示线段中间下标对5取摸的5种情况的数字的和(语文表达能力感觉还是有点问题,不过。。。你懂得),分析到这里,就只剩下两个问题了:

一、PushUp函数,也就是跟新的时候回溯部分怎么写?

二、由于我们先输入在建树在输出(这样做的原因就是输出完了之后可以排一遍序,以此来保证建树的时候一定是从小到大);

具体这两个问题的解答见代码:

/*Problem : 4288 ( Coder )     Judge Status : Accepted
RunId : 11551798    Language : G++    Author : Burglar
Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta*/
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<iostream>
#define MAXN 100005
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
int n;
int number[MAXN];//记录输入中出现的数字,方便排序;
struct Input//输入
{
    char dos[4];
    int nub;
}input[MAXN];
struct Tree//线段树
{
    long long sum[5];
    int num;//节点的数量;
}tree[MAXN << 2];
void PushUp(int rt)//用于更新时的回溯;
{
    for(int i = 0; i < 5; i++)
    {
        tree[rt].sum[i] = tree[rt << 1].sum[i] + tree[rt << 1 | 1].sum[((i - tree[rt << 1].num) % 5 + 5) % 5];//难点就在于想右节点sum与跟检点sum的对应关系,其中加上一个5就是为了防止数组下标出现负数;
    }
}
void BuildTree(int l, int r, int rt)//建树
{
    memset(tree[rt].sum,0,sizeof(tree[rt].sum));
    tree[rt].num = 0;
    if(l == r) return;
    int m = (r + l) >> 1;
    BuildTree(lson);
    BuildTree(rson);
}
void Update(int value, int pos, int k, int l, int r, int rt)//更新,pos表示这个数字应放置的位置;
{
    tree[rt].num += k;
    if(l == r)
    {
        if(k == 1) tree[rt].sum[1] = value;
        else
            tree[rt].sum[1] = 0;
        return;
    }
    int m = (l + r) >> 1;
    if(pos <= m)
        Update(value, pos, k, lson);
    else
        Update(value, pos, k, rson);
    PushUp(rt);
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        int num_number = 1;
        memset(number, 0, sizeof(number));
        for(int i = 1; i <= n; i++)
        {
            scanf("%s",input[i].dos);
            if(!strcmp(input[i].dos,"sum")) continue;
            else
            {
                scanf("%d",&input[i].nub);
                number[num_number++] = input[i].nub;
            }
        }
        sort(number + 1, number + num_number);//通过排序之后方便下面的lower_bound函数,他的实现是利用二分搜索,必须要排序;
        num_number = unique(number + 1, number + num_number) - (number + 1);//祛除序列中重复的数(应为number数组中是不区分删除和添加的要认为区分开),unique的返回值是一个指针;此时num_number变量表示的是序列中没有重复的数字的个数;
        BuildTree(1, num_number, 1);//应为在添加的时候保证之前是没有这个数的,所以根据没有重复数字的个数建树;
        for(int i = 1; i <= n; i++)
        {
            if(!strcmp(input[i].dos,"sum"))//询问操作;
            {
                printf("%I64d\n",tree[1].sum[3]);
            }
            else
            {
                int pos = lower_bound(number + 1, number + num_number + 1, input[i].nub)-number;//找出数字的位置
                if(!strcmp(input[i].dos,"add"))
                {
                    Update(input[i].nub, pos, 1, 1, num_number, 1);//添加操作;
                }
                else
                {
                    Update(input[i].nub, pos, -1, 1, num_number, 1);//删除操作;
                }
            }
        }
    }
    return 0;
}


 类似资料:

相关阅读

相关文章

相关问答