【链接】
http://acm.hdu.edu.cn/showproblem.php?pid=5152
【题意】
给你一个长度为n的序列，有m个操作，3种操作：
1. 给你l,r，输出l-r的和。
2. 修改操作，x，把a[x]->修改为x^a[x]
3. 加操作。l,r,x，l-r区间加x
输出结果对2333333取模。
【思路】
重点在于第二个操作。
A^x = A ^ (x%Phi(C) + Phi(C)) (mod C) (x >= Phi(C))
然后，值得注意是，这道题的Phi(c)，是一层套一层的。
最后，题目给出2333333（不是质数），所以Phi(c)，最多只有18层。
【代码】
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
const int MOD = 2333333;
int mo[19] = { 2333333 , 2196720 , 580608 , 165888 , 55296 , 18432 , 6144 , 2048 , 1024 , 512 , 256 , 128 , 64 , 32 , 16 , 8 , 4 , 2 , 1 };ll sum[maxn << 2];
ll len[maxn << 2];
ll add[maxn << 2];
ll a[maxn];
vector<ll> v[maxn];
int n, m;int qpow(ll a, ll b, ll mod) {ll ret = 1;a %= MOD;while (b) {if (b & 1) ret = ret * a % mod;a = a * a % mod;b >>= 1;}return ret;
}void pushdown(int n) {if (add[n]) {add[n<<1] += add[n];add[n<<1|1] += add[n];sum[n<<1] = (sum[n<<1] + add[n] * len[n<<1] % MOD) % MOD;sum[n<<1|1] = (sum[n<<1|1] + add[n] * len[n<<1|1] % MOD) % MOD;add[n] = 0;}
}void pushup(int n) {sum[n] = (sum[n<<1] + sum[n<<1|1]) % MOD;
}void build(int l, int r, int n) {add[n] = 0;len[n] = r - l + 1;if (l == r) {sum[n] = a[l] % MOD;return;}int mid = (l + r) >> 1;build(l, mid, n<<1);build(mid + 1, r, n<<1|1);pushup(n);
}void pushupdate(int L, int R, int l, int r, int n, ll v) {if (L <= l && r <= R) {add[n] += v;sum[n] = (sum[n] + len[n] * v) % MOD;return;}pushdown(n);int mid = (l + r) >> 1;if (L <= mid) pushupdate(L, R, l, mid, n<<1, v);if (mid < R) pushupdate(L, R, mid + 1, r, n<<1|1, v);pushup(n);
}ll cal(int i, int t) {if (t == 19) return 0;ll tmp;int ch = v[i].size() - 1 - t;if (t + 1 == v[i].size()) tmp = v[i][ch];else tmp = qpow(2, cal(i, t + 1), mo[t]) + v[i][ch];if (tmp >= mo[t]) tmp = tmp % mo[t] + mo[t];return tmp;
}void modify(int x, int l, int r, int n) {if (l == r) {v[x][v[x].size() - 1] += add[n];add[n] = 0;v[x].push_back(0);sum[n] = cal(x, 0) % MOD;return;}pushdown(n);int mid = (l + r) >> 1;if (x <= mid) modify(x, l, mid, n<<1);else modify(x, mid + 1, r, n<<1|1);pushup(n);
}ll query(int L, int R, int l, int r, int n) {if (L <= l && r <= R) return sum[n];pushdown(n);int mid = (l + r) >> 1;ll ret = 0;if (L <= mid) ret = (ret + query(L, R, l, mid, n<<1)) % MOD;if (mid < R) ret = (ret + query(L, R, mid + 1, r, n<<1|1)) % MOD;return ret;
}void init() {for (int i = 0; i <= n; ++i)v[i].clear();
}int main() {while (~scanf("%d%d", &n, &m) ) {init();for (int i = 1; i <= n; ++i) {scanf("%lld", &a[i]);v[i].push_back(a[i]);}build(1, n, 1);int op, u, v;ll w;for (int i = 0; i<m; ++i) {scanf("%d", &op);if (op == 1) {scanf("%d%d", &u, &v);printf("%lld\n", query(u, v, 1, n, 1));}else if (op == 2) {scanf("%d", &u);modify(u, 1, n, 1);}else{scanf("%d%d%lld", &u, &v, &w);pushupdate(u, v, 1, n, 1, w);}}}
}