首页 > 代码库 > PKU-3468 simple problem with integer 线段树 LL坑点(欢迎讨论)

PKU-3468 simple problem with integer 线段树 LL坑点(欢迎讨论)

2024-09-05 21:42:08   218人阅读

You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.InputThe first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.OutputYou need to answer all Q commands in order. One answer in a line.Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15

Hint

The sums may exceed the range of 32-bit integers.

 

——————————————————————正义的分割线————————————————————————————

    嘛，仍然是到线段树题目，但是这道题目一个不同的点是需要对段进行增删操作，这个和之前count color的替换不大一样，具体哪里不一样么，就是这样一来查询的时候需要进行pushdown操作，因为在程序路过一个节点的时候，它可能只是要这个节点的部分信息而已，这时候就变成了底层信息需要从底层节点获取，但是增删信息存在上层节点上，而且多层的结构也使携带信息成为了一个增加代码复杂度降低可读性的东西，所以既然增加一个pushdown又能过的前提下我们当然没有必要设计一个一路携带信息下来的访问程序。

  不过这里有一个值得疑问的东西，我之前由于一开始的设计习惯增加了lazy标签来标注是否有增量，然后增量存在lazyn这个数据里面，判断是否需要pushdown用的是lazy标签，但是这在后来证明是错的，判断用lazyn标签就对了。

  我们来列举一下lazy和lazyn的关系：

  若lazy为0，那么lazyn必为0，两者的判断无影响

  若lazy为1，那么lazyn会是一个int，但是我在里面特判了一下，如果lazyn为0，那么lazy也为0，所以lazy和lazyn应该是等价的……好吧我不得不承认这其中应该存在一个非常严重的逻辑漏洞，但是确实是没有找到一组错误样例来证明的。

p.s:如果评论里有人能给出错误样例我会很感激QAQ

————————————————————————————————————————————————————————

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<climits>
#include<map>
#include<stack>
#define file_in freopen("input.txt","r",stdin)
#define MAX 100000
#define maxn 5005
using namespace std;
#define LL long long
#define FF(x,y) for(int i=x;i<y;i++)
struct node
{
    LL lef;
    LL rig;
    LL mid;
    LL data;
    LL lazyn;
    LL lazy;
}tree[3 * MAX];
vector<LL>sto;
LL createtree(LL left, LL right, LL id)
{
    tree[id].lef = left;
    tree[id].rig = right;
    tree[id].lazy = 0;
    tree[id].lazyn = 0;
    if (left == right)
    {
        tree[id].data = http://www.mamicode.com/sto[left];
        return tree[id].data;
    }
    LL mid = (left + right) >> 1;
    tree[id].mid = mid;
    tree[id].data = http://www.mamicode.com/createtree(left, mid, id * 2) + createtree(mid + 1, right, id * 2 + 1);
    return tree[id].data;
}
void pushdown(LL id)
{
    if (tree[id].lazyn)
    {
        tree[2 * id].data += (tree[2 * id].rig - tree[2 * id].lef + 1)*tree[id].lazyn;
        tree[2 * id + 1].data += (tree[2 * id + 1].rig - tree[2 * id + 1].lef + 1)*tree[id].lazyn;
        tree[2 * id].lazyn += tree[id].lazyn;
        tree[2 * id + 1].lazyn += tree[id].lazyn;
        tree[id].lazy = 0;
        tree[id].lazyn = 0;
    }
}
void update(LL left, LL right, LL value, LL id)
{
    if (tree[id].lef >= left&&tree[id].rig <= right)
    {
        tree[id].data += (tree[id].rig - tree[id].lef + 1)*value;
        tree[id].lazy = 1;
        tree[id].lazyn += value;
        if (tree[id].lazyn == 0)tree[id].lazy = 0;
        //cout << tree[id].lef << " " << tree[id].rig << " " << tree[id].data << "|";
        return;
    }
    pushdown(id);
    if (left > tree[id].mid)
    {
        update(left, right, value, 2 * id + 1);
    }
    else if (tree[id].mid >= right)
    {
        update(left, right, value, 2 * id);
    }
    else
    {
        update(left, right, value, 2 * id);
        update(left, right, value, 2 * id + 1);
    }
    tree[id].data = http://www.mamicode.com/tree[id * 2].data + tree[id * 2 + 1].data;

}
LL query(LL lef, LL rig, LL id)
{
    if (tree[id].lef >= lef&&tree[id].rig <= rig)
    {
        //cout << tree[id].lef << " " << tree[id].rig << " " << tree[id].data << "|";
        return tree[id].data;
    }
    pushdown(id);
    if (lef > tree[id].mid)
    {
        return query(lef, rig, 2 * id + 1);
    }
    else if (tree[id].mid >= rig)
    {
        return query(lef, rig, 2 * id);
    }
    else
    {
        return query(lef, rig, 2 * id + 1) + query(lef, rig, 2 * id);
    }
}

int main()
{
    LL num, op;
    while (scanf("%lld %lld", &num, &op) != EOF)
    {
        sto.resize(num + 1);
        FF(1, num + 1)
        {
            scanf("%lld", &sto[i]);
        }
        createtree(1, num, 1);
        FF(0, op)
        {
            char T;
            getchar();
            scanf("%c", &T);
            if (T == ‘Q‘)
            {
                LL a, b;
                scanf("%lld %lld", &a, &b);
                printf("%lld\n", query(a, b, 1));
            }
            else
            {
                LL a, b, v;
                scanf("%lld %lld %lld", &a, &b, &v);
                /*    for (int i = a; i <= b; i++)
                {
                sto[i] += v;
                }
                for (int i = 1; i <= num; i++)
                printf("%lld ", sto[i]);
                puts("");*/
                update(a, b, v, 1);
                //puts("");
            }
        }
    }


}
/*10 5
1 2 3 4 5 6 7 8 9 10
Q 2 4
C 3 6 3
Q 2 4
C 3 6 -3
Q 2 4
*/

PKU-3468 simple problem with integer 线段树 LL坑点(欢迎讨论)


联系
我们