AOJ 902.最讨厌的“2”

276


题目



点击显/隐题目

有一个长度为n的数组a。现有m组操作。
操作1:将区间[l,r]内的所有数字都整除2。
操作2:输出区间[l,r]内所有数字的和。


第一行输入两个整数n,m(1<=n<=200000,1<=m<=200000)
第二行n个整数,表示数组a (0<=a[i]<=10^9)
接下来m行,每行三个整数op,l,r
——若op=1,表示操作1,将[l,r]内所有数字整除2
——若op=2,表示操作2,输出[l,r]内所有数字的和


对于所有的操作2,输出结果。


5 5
3 4 9 2 7
2 3 4
1 4 5
2 1 5
1 3 4
2 3 5


11
20
7




题解


线段树问题,需要注意的是,虽然查询次数多的情况下通常会使用lazy标记
但是这道题除以2的操作使用lazy标记很难实现
另外可以发现一个数即使达到输入范围的最大值 10^9 ,其也能在仅仅30次操作后变成 0

那么就可以想到,如果我们查询到一个节点的值已经是0,就没有必要往下查,直接返回 0 即可,更新同理
这样其实查询的复杂度远远少于 O(log(n))

另外由于数比较大,需要使用long long记录和


代码


点击显/隐代码
#include <cmath>
#include <cstdio>
#include <ctime>
const int maxn = 2e5 + 5;

typedef long long LL;

int n, m;
LL a[maxn];

LL read_int() {
    char c;
    LL ans = 0;
    while (c = getchar(), !(c >= '0' && c <= '9'))
        ;
    while (c >= '0' && c <= '9') {
        ans *= 10;
        ans += (int)c - '0';
        c = getchar();
    }
    return ans;
}
long long add(long long a, long long b) { return a + b; }

class ST {
    struct Tree {
        int l, r;
        LL n;
    };

    Tree T[maxn * 8];

  public:
    inline static int getLastRowBeginPosition(int n) {
        int ans = 1 << ((int)(log(n) / log(2)));
        if (ans < n)
            ans <<= 1;
        return ans;
    }
    LL BuildTree(int a, int b, LL (*compare)(LL, LL), LL *num, int pos = 1) {
        // printf("build(%d,%d,%d)\n", a, b, pos);

        T[pos].l = a;
        T[pos].r = b;

        if (a == b) {
            if (a > n)
                return T[pos].n = 0;
            else
                return T[pos].n = num[a];
        }

        int mid = (a + b) >> 1;
        int leftchild = pos << 1;
        int rightchild = (pos << 1) + 1;

        return T[pos].n =
                   compare(BuildTree(a, mid, compare, num, leftchild),
                           BuildTree(mid + 1, b, compare, num, rightchild));
    }

    LL query(int a, int b, LL (*compare)(LL, LL), LL *num, int pos = 1) {
        // printf("query(%d,%d,%d)\n", a, b, pos);

        if (a == b)
            return T[getLastRowBeginPosition(n) - 1 + a].n;

        if (T[pos].n == 0)
            return 0;

        int &l = T[pos].l;
        int &r = T[pos].r;

        if (a == l && b == r)
            return T[pos].n;

        int mid = (l + r) >> 1;
        int leftchild = pos << 1;
        int rightchild = (pos << 1) + 1;

        if (b <= mid)
            return query(a, b, compare, num, leftchild);
        if (a > mid)
            return query(a, b, compare, num, rightchild);
        return compare(query(a, mid, compare, num, leftchild),
                                  query(mid + 1, b, compare, num, rightchild));
    }

    LL update(int a, int b, LL (*compare)(LL, LL), LL *num, int pos = 1) {
        // printf("     update(%d,%d,%d)\n", a, b, pos);

        int &l = T[pos].l;
        int &r = T[pos].r;

        if (l == r)
            return T[pos].n >>= 1;

        if (T[pos].n == 0)
            return 0;

        int mid = (l + r) >> 1;
        int leftchild = pos << 1;
        int rightchild = (pos << 1) + 1;

        if (b <= mid) {
            T[pos].n =
                compare(update(a, b, compare, num, leftchild), T[rightchild].n);
        } else if (a > mid) {
            T[pos].n =
                compare(T[leftchild].n, update(a, b, compare, num, rightchild));
        } else {
            T[pos].n = compare(update(a, mid, compare, num, leftchild),
                               update(mid + 1, b, compare, num, rightchild));
        }
        return T[pos].n;
    }

    void printTree() {
        for (int i = 1; i < getLastRowBeginPosition(n) << 1; ++i) {
            if ((i > 0) && (i & (i - 1)) == 0)
                printf("\n");
            printf("[%d (%d,%d) %I64d] ", i, T[i].l, T[i].r, T[i].n);
        }
        printf("\n");
    }
};

ST tree;

int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    //int START = clock();
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= n; ++i) {
            scanf("%I64d", &a[i]);
            // printf("%d\n",i);
        }
        // printf("read finish\n");
        tree.BuildTree(1, ST::getLastRowBeginPosition(n), add, a);
        // tree.printTree();
        for (int i = 1; i <= m; ++i) {
            int c, l, r;
            scanf("%d%d%d", &c, &l, &r);
            if (c == 1)
                tree.update(l, r, add, a);
            else
                printf("%I64d\n", tree.query(l, r, add, a));
            // tree.printTree();
        }
    }
    //printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论