题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=5152

题目大意

首先给你一个长度为N的序列,序列为A1,A2,A3,...AN,然后有M个操作,每个操作为以下三种操作的其中一个: 

1. 输出操作。给你l,r,输出∑i(l, r)Ai的值。 

2. 修改操作。给你x,把Ax修改为2^Ax。

3. 加法操作。给你l,r,x,给Ai(l <= i <= r)加上x。

由于输出操作的结果可能很大,输出结果对2333333取模。

题解

操作一、三为区间线断树的查询和更新操作。

对于操作二,利用公式

当x >= Phi(C),A^x = A ^ (x%Phi(C) + Phi(C)) (mod C) 

对于2333333这个模数来说,求18次欧拉函数后就变成了1,所以只需要保存19层。

知识点

在数论,对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目。F(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)...(1-1/pn),其中p1 p2...pn为x的所有质因数,x是不为0的整数。F(1)=1(唯一和1互质的数(小于等于1)就是1本身)。

代码

/*************************************************************************
    > File Name: 1003.cpp
    > Author: Haipz
    > Blog: haipz.com 
    > Created Time: 日 12/28 17:22:26 2014
 ************************************************************************/

#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

const int MOD = 2333333;
const int N = 50000 + 5;

struct Operation {
    int type;
    int l, r, x;
} f[N + 5];

int a[N], mod[20];
int idx;

vector<long long> V[N];

struct Node {
    int sum;
    long long mark;
};

struct Tree {
    Node node[N*4];
    
    void init() {
        memset(node, 0, sizeof(node));
    }

    void pushup(int i) {
        int ls = i*2, rs = i*2 + 1;
        node[i].sum = node[ls].sum + node[rs].sum;
        node[i].sum %= MOD;
        return;
    }

    void pushdown(int i, int tl, int tr) {
        int ls = i*2, rs = i*2 + 1, mid = (tl + tr)/2;
        if (node[i].mark) {
            node[ls].mark += node[i].mark;
            node[ls].sum += node[i].mark*(mid - tl) % MOD;
            node[ls].sum %= MOD;

            node[rs].mark += node[i].mark;
            node[rs].sum += node[i].mark*(tr - mid) % MOD;
            node[rs].sum %= MOD;

            node[i].mark = 0;
        }
        return;
    }

    void update(int i, int tl, int tr, int l, int r, int val) {
        if (l <= tl && tr <= r) {
            node[i].mark += val;
            node[i].sum += 1LL*val*(tr - tl) % MOD;
            node[i].sum %= MOD;
            return;
        }
        pushdown(i, tl, tr);

        int ls = i*2, rs = i*2 + 1, mid = (tl + tr)/2;
        if (l < mid) update(ls, tl, mid, l, r, val);
        if (r > mid) update(rs, mid, tr, l, r, val);

        pushup(i);
        return;
    }

    int query(int i, int tl, int tr, int l, int r) {
        if (l <= tl && tr <= r) {
            idx = i;
            return node[i].sum;
        }
        pushdown(i, tl, tr);

        int ls = i*2, rs = i*2 + 1, mid = (tl + tr)/2, ans = 0;
        if (l < mid) ans += query(ls, tl, mid, l, r), ans %= MOD;
        if (r > mid) ans += query(rs, mid, tr, l, r), ans %= MOD;

        pushup(i);
        return ans;
    }
} tree;

int euler(int n) {
    int ans = 1;
    for (int i = 2; i*i <= n; ++i)
        if (n % i == 0) {
            n /= i;
            ans *= i - 1;
            while (n % i == 0) {
                n /= i;
                ans *= i;
            }
        }
    if (n > 1) ans *= n - 1;
    return ans;
}

int apbmodc(int a, int b, int c) {
    int ans = 1 % c;
    while (b) {
        if (b & 1) ans = 1LL*ans*a % c;
        a = 1LL*a*a % c;
        b /= 2;
    }
    return ans;
}

int main() {
    mod[0] = MOD;
    for (int i = 1; i < 20; ++i) mod[i] = euler(mod[i - 1]);

    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {

        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        for (int i = 1; i <= m; ++i) {
            scanf("%d", &f[i].type);
            if (f[i].type == 1) scanf("%d%d", &f[i].l, &f[i].r);

            if (f[i].type == 2) scanf("%d", &f[i].x);

            if (f[i].type == 3) scanf("%d%d%d", &f[i].l, &f[i].r, &f[i].x);
        }

        for (int i = 1; i <= n; ++i) V[i].clear();
        for (int i = 1; i <= n; ++i) V[i].push_back(0);

        tree.init();
        for (int i = 1; i <= n; ++i) tree.update(1, 1, n + 1, i, i + 1, a[i]);
        for (int i = 1; i <= m; ++i) {
            if (f[i].type == 1) printf("%d\n", tree.query(1, 1, n + 1, f[i].l, f[i].r + 1));
            
            if (f[i].type == 2) {
                int a = tree.query(1, 1, n + 1, f[i].x, f[i].x + 1);
                int size = V[f[i].x].size();
                V[f[i].x][size - 1] += tree.node[idx].mark;
                V[f[i].x].push_back(0);
                ++size;
                tree.update(1, 1, n + 1, f[i].x, f[i].x + 1, -a);
                long long b;
                if (size < 19) {
                    b = V[f[i].x][0];
                    bool flag = false;
                    if (b >= mod[size - 1]) {
                        flag = true;
                        b = b % mod[size - 1] + mod[size - 1];
                    }
                    for (int j = 1; j < size; ++j)
                        if (flag) b = (apbmodc(2, b, mod[size - j - 1]) + V[f[i].x][j]) % mod[size - j - 1] + mod[size - j - 1];
                        else {
                            if (b >= 30 || (1<<b) >= mod[size - j - 1]) {
                                flag = true;
                                b = (apbmodc(2, b, mod[size - j - 1]) + V[f[i].x][j]) % mod[size - j - 1] + mod[size - j - 1];
                            } else {
                                b = (1<<b) + V[f[i].x][j];
                                if (b >= mod[size - j - 1]) b = b % mod[size - j - 1] + mod[size - j - 1];
                            }
                        }
                } else {
                    b = 1;
                    for (int j = 18; j; --j)
                        b = (apbmodc(2, b, mod[j]) + V[f[i].x][size - j]) % mod[j] + mod[j];
                }

                tree.update(1, 1, n + 1, f[i].x, f[i].x + 1, b % MOD);
                tree.node[idx].mark = 0;
            }

            if (f[i].type == 3) tree.update(1, 1, n + 1, f[i].l, f[i].r + 1, f[i].x);
        }
    }
    return 0;
}
转载保留版权:http://haipz.com/blog/i/6352 - 海胖博客