HDU4027

本以为对线段树还是比较熟悉的,但是这题改变了我的想法。

顺着wk的题解做了这题。

拿到手就知道线段树,写完T,这时候我想起来蓝桥杯的线段树也是这样的吧,只不过那题对区间的操作是log,真可笑,当时还以为是cin写跪了,就这题看来,估计也那题没过几组数据,二等奖也在情理之中。

每次都更新到最底下会超时,每个数sqrt几次之后就会成为1,这时再开方是没有意义的,可以剪枝,如果区间长度等于区间和,说明区间没有必要更新,可以直接return。

此外还有好几个WA点

#include<cstdio>
#include<cstring>
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
#define MAXN 100005
struct node
{
    int l,r,mid;
    __int64 sum,len;//32位会WA
}tree[MAXN<<2];
void build(int l,int r,int now)
{
    tree[now].l=l;
    tree[now].r=r;
    tree[now].sum=0;
    tree[now].len=r+1-l;
    if(l==r)
    {
        scanf("%I64d",&tree[now].sum);
        return ;
    }
    tree[now].mid=(l+r)>>1;
    build(l,tree[now].mid,now<<1);
    build(tree[now].mid+1,r,now<<1|1);
    tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;//弱爆了,刚开始这里都忘记写了
}
void update(int l,int r,int now)
{
    if(tree[now].l==l && tree[now].r==r)
    {
        if(tree[now].len==tree[now].sum)
        return ;
    }
    if(tree[now].l==tree[now].r)
    {
        tree[now].sum=(__int64)sqrt(1.0*tree[now].sum);//不知道为什么,这里直接开方不行,可能是64位的原因吧
        return;
    }
    if(l>tree[now].mid)
    update(l,r,now<<1|1);
    else
    {
        if(r<=tree[now].mid)
        update(l,r,now<<1);
        else
        {
            update(l,tree[now].mid,now<<1);
            update(tree[now].mid+1,r,now<<1|1);
        }
    }
    tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
}
__int64 query(int l,int r,int now)//64君哦
{
    if(l==tree[now].l && r==tree[now].r)
    return tree[now].sum;
    if(l>tree[now].mid)
    return query(l,r,now<<1|1);
    else
    {
        if(r<=tree[now].mid)
        return query(l,r,now<<1);
        else
        return query(l,tree[now].mid,now<<1)+query(tree[now].mid+1,r,now<<1|1);
    }
}
int main()
{
    int n,m,te=0;
    while(~scanf("%d",&n))
    {
        te++;
        build(1,n,1);
        scanf("%d",&m);
        printf("Case #%d:\n",te);
        while(m--)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            int l=min(b,c);//区间左右大小不一定
            int r=max(b,c);
            if(a==0)
                update(l,r,1);
            else
            {
                printf("%I64d\n",query(l,r,1));
            }
        }
        cout<<endl;//还有这里最后还PE一发
    }
    return 0;
}

真是作死!64君,加油!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • codeforces 438D

    在某位不知名的大大推荐下做了这题,和我上一篇的线段树很像,于是怒拍,思想基本相同,记录区间最大值,当最大值小于取模时可以剪枝。 今后再遇到此类问题算是能解决了 ...

    triplebee
  • Leetcode 218. The Skyline Problem 线段树

    A city's skyline is the outer contour of the silhouette formed by all the build...

    triplebee
  • 主席树POJ2104

    求区间第k大数是多少 用我惯用的线段树写法似乎不适合写主席树,看别人的代码好半天才看懂 用root表示每一个前缀树的根,思想大致是由第i-1个树构成的树建第i个...

    triplebee
  • codeforces 438D

    在某位不知名的大大推荐下做了这题,和我上一篇的线段树很像,于是怒拍,思想基本相同,记录区间最大值,当最大值小于取模时可以剪枝。 今后再遇到此类问题算是能解决了 ...

    triplebee
  • Leetcode 218. The Skyline Problem 线段树

    A city's skyline is the outer contour of the silhouette formed by all the build...

    triplebee
  • 主席树POJ2104

    求区间第k大数是多少 用我惯用的线段树写法似乎不适合写主席树,看别人的代码好半天才看懂 用root表示每一个前缀树的根,思想大致是由第i-1个树构成的树建第i个...

    triplebee
  • Leetcode 77 Combinations

    Given two integers n and k, return all possible combinations of k numbers out o...

    triplebee
  • ACM校赛网络赛部分题解

    这次网络赛我共出了三题,现给出题解 自动售货机 由于测试样例很多,每次都计算会超时,所以要打表,递推方程为dp[i][j]=dp[i-1][j]+dp[i-1]...

    triplebee
  • 洛谷P3835 【模板】可持久化平衡树

    题目背景 本题为题目 普通平衡树 的可持久化加强版。 数据已经经过强化 题目描述 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作(对...

    attack
  • BZOJ3998: [TJOI2015]弦论(后缀自动机)

    第二行为两个整数T和K,T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。

    attack

扫码关注云+社区

领取腾讯云代金券