HDU 4027 Can you answer these queries?（线段树单点更新+询问+神坑）

谁践踏了优雅 2022-06-12 03:17 118阅读 0赞

A lot of battleships of evil are arranged in a line before the battle. Our commander decides to use our secret weapon to eliminate the battleships. Each of the battleships can be marked a value of endurance. For every attack of our secret weapon, it could decrease the endurance of a consecutive part of battleships by make their endurance to the square root of it original value of endurance. During the series of attack of our secret weapon, the commander wants to evaluate the effect of the weapon, so he asks you for help.  
You are asked to answer the queries that the sum of the endurance of a consecutive part of the battleship line.  
  
Notice that the square root operation should be rounded down to integer.

Input

The input contains several test cases, terminated by EOF.  
For each test case, the first line contains a single integer N, denoting there are N battleships of evil in a line. (1 <= N <= 100000)  
The second line contains N integers Ei, indicating the endurance value of each battleship from the beginning of the line to the end. You can assume that the sum of all endurance value is less than 2 63.  
The next line contains an integer M, denoting the number of actions and queries. (1 <= M <= 100000)  
For the following M lines, each line contains three integers T, X and Y. The T=0 denoting the action of the secret weapon, which will decrease the endurance value of the battleships between the X-th and Y-th battleship, inclusive. The T=1 denoting the query of the commander which ask for the sum of the endurance value of the battleship between X-th and Y-th, inclusive.

Output

For each test case, print the case number at the first line. Then print one line for each query. And remember follow a blank line after each test case.

Sample Input

10
    1 2 3 4 5 6 7 8 9 10
    5
    0 1 10
    1 1 10
    1 1 5
    0 5 8
    1 4 8

Sample Output

Case #1:
    19
    7
    6

题解：

这题难度不大，坑点特多，不过也学到了很多，让我感到疑问的是，我用同样的代码，把里面父子节点的\*号和+号改成了位运算。。结果用的时间居然更！多！了，测试了2组，平均都比加号乘号多了100-200ms，这和学长说的位运算会更快得出了相反的结论（也可能是测试数据过少），学到的是在建树的时候赋值会快上一倍，以前都是用数组保存好再建的，费时间又废内存，还有这题就是我看了几篇博客都是用打tag的方法确定区间是否全部为1的以节省时间。。后来不记得在哪看到的用的方法很巧妙，用询问区间来确定要不要更新，如果被询问的区间x，y值为y-x+1，就不更新，虽然好像更慢一些但是操作起来简单。。记笔记

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    struct node
    {
        int l,r;
        long long sum;//给的范围要求用long long
    };
    node t[400005];
    void Build(int l,int r,int num)
    {
        t[num].l=l;
        t[num].r=r;
        if(l==r)
        {
            scanf("%lld",&t[num].sum);//要直接在里面建树，不能用数组保存后建，会超时
            return;
        }
        int mid=(l+r)/2;
        Build(l,mid,num*2);
        Build(mid+1,r,num*2+1);
        t[num].sum=t[num*2].sum+t[num*2+1].sum;//更新一波数据
    }
    void update(int l,int r,int num)//日常更新
    {
        if(t[num].l==t[num].r)
        {
            t[num].sum=sqrt(t[num].sum);
            return;
        }
        int mid=(t[num].l+t[num].r)/2;
        if(r<=mid)
            update(l,r,num*2);
        else if(l>mid)
            update(l,r,num*2+1);
        else
        {
            update(l,mid,num*2);
            update(mid+1,r,num*2+1);
        }
        t[num].sum=t[num*2].sum+t[num*2+1].sum;//相当于pushup向上更新
    }
    long long query(int l,int r,int num)//询问
    {
        if(l==t[num].l&&r==t[num].r)//与平常不同，由于是单点更新，区间左右端点相同就是访问区间的单点
        {
            return t[num].sum;
        }
        int mid=(t[num].l+t[num].r)/2;
        if(r<=mid)
            return query(l,r,num*2);
        else if(l>mid)
            return query(l,r,num*2+1);
        else
            return query(l,mid,num*2)+query(mid+1,r,num*2+1);
    }
    int main()
    {
        int i,j,n,m,x,y,d,k,ans=1;
        while(scanf("%d",&n)!=EOF&&n)
        {
            Build(1,n,1);
            scanf("%d",&m);
            printf("Case #%d:\n",ans);
            ans++;
            for(i=0;i<m;i++)
            {
                scanf("%d%d%d",&d,&x,&y);
                if(x>y)//神坑，去掉会错。。故意的
                    swap(x,y);
                if(d==0)
                {
                    if(query(x,y,1)!=y-x+1)//精华，如果区间全是1，就不用更新了，去掉tle
                        update(x,y,1);
                }
                else
                {
                    printf("%lld\n",query(x,y,1));
                }
            }
            printf("\n");
        }
        return 0;
    }

然后这是我自己想的第二种做法，比前一种还快200ms-300ms，就是区间打tag的方法，如果是1就tag为0，不是1就tag为1，如果区间tag和为0就不用找或者修改了，这里就不打备注了，都差不多

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    const int N=1e5+5;
    struct node
    {
        int l,r;
        int tag;
        long long sum;
    }t[N*4];
    void Build(int l,int r,int num)
    {
        t[num].l=l;
        t[num].r=r;
        if(l==r)
        {
            scanf("%lld",&t[num].sum);
            if(t[num].sum!=1)
                t[num].tag=1;
            else
                t[num].tag=0;
            return;
        }
        int mid=(l+r)/2;
        Build(l,mid,num*2);
        Build(mid+1,r,num*2+1);
        t[num].tag=t[num*2].tag+t[num*2+1].tag;
        t[num].sum=t[num*2].sum+t[num*2+1].sum;
    }
    long long query(int l,int r,int num)
    {
        if(t[num].tag==0)
        {
            return r-l+1;
        }
        if(l==t[num].l&&r==t[num].r)
        {
            return t[num].sum;
        }
        int mid=(t[num].l+t[num].r)/2;
        if(r<=mid)
            return query(l,r,num*2);
        else if(l>mid)
            return query(l,r,num*2+1);
        else
            return query(l,mid,num*2)+query(mid+1,r,num*2+1);
    }
    void update(int l,int r,int num)
    {
        if(t[num].tag==0)
            return;
        if(t[num].l==t[num].r)
        {
            t[num].sum=sqrt(t[num].sum);
            if(t[num].sum==1)
                t[num].tag=0;
            return;
        }
        int mid=(t[num].l+t[num].r)/2;
        if(r<=mid)
            update(l,r,num*2);
        else if(l>mid)
            update(l,r,num*2+1);
        else
        {
            update(l,mid,num*2);
            update(mid+1,r,num*2+1);
        }
        t[num].tag=t[num*2].tag+t[num*2+1].tag;
        t[num].sum=t[num*2].sum+t[num*2+1].sum;
    }
    int main()
    {
        int n,i,j,k,x,y,q,ans=1;
        while(scanf("%d",&n)!=EOF)
        {
            Build(1,n,1);
            scanf("%d",&k);
            printf("Case #%d:\n",ans);
            ans++;
            for(i=0;i<k;i++)
            {
                scanf("%d%d%d",&q,&x,&y);
                if(x>y)
                    swap(x,y);
                if(q==0)
                    update(x,y,1);
                else
                    printf("%lld\n",query(x,y,1));
            }
            printf("\n");
        }
        return 0;
    }