CF311D Interval Cubing

题意：

给出长度为
询问区间
将
对于第一个操作输出一行一个整数。
题解：

打表发现循环节是48，可以维护48个线段树，记录偏移量。
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1e5 + 10;
 5 typedef long long ll;
 6 const ll mod = 95542721;
 7 inline ll read()
 8 {
 9     char ch = getchar();ll x = 0, f = 1;
10     while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
11     while(ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) - '0' + ch; ch = getchar();}
12     return x * f;
13 }
14 ll n, m;
15 ll sum[N << 2][49];
16 int lazy[N << 2];
17 int tr[N << 2];
18 
19 
20 void build(int rt, int l, int r)
21 {
22     if(l == r)
23     {
24         scanf("%lld", &sum[rt][0]);
25         for (int i = 1; i <= 47; i ++)
26             sum[rt][i] = sum[rt][i - 1] * sum[rt][i - 1] % mod * sum[rt][i - 1] % mod;
27         return ;
28     }
29     int mid = l + r >> 1;
30     build(rt << 1, l, mid);
31     build(rt << 1 | 1, mid + 1, r);
32     for (int i = 0; i <= 47; i ++)
33         sum[rt][i] = sum[rt << 1][i] + sum[rt << 1 | 1][i];
34 }
35 
36 void pushdown(int rt)
37 {
38     if(lazy[rt])
39     {
40         lazy[rt << 1] = (lazy[rt << 1] + lazy[rt]) % 48;
41         lazy[rt << 1 | 1] = (lazy[rt] + lazy[rt << 1 | 1]) % 48;
42         tr[rt << 1] = (tr[rt << 1] + lazy[rt]) % 48;
43         tr[rt << 1 | 1] = (tr[rt << 1 | 1] + lazy[rt]) % 48;
44         lazy[rt] = 0;
45     }
46 }
47 
48 
49 void update(int rt, int L, int R, int l, int r)
50 {
51     if(L <= l && R >= r)
52     {
53         lazy[rt] = (lazy[rt] + 1) % 48;
54         tr[rt] = (tr[rt] + 1) % 48;
55         return ;
56     }
57     pushdown(rt);
58     int mid = l + r >> 1;
59     if(L <= mid) update(rt << 1, L, R, l, mid);
60     if(R > mid) update(rt << 1 | 1, L, R, mid + 1, r);
61     for (int i = 0; i <= 47; i ++)
62         sum[rt][i] = sum[rt << 1][(i + tr[rt << 1])%48] + sum[rt << 1 | 1][(i + tr[rt << 1 | 1]) % 48];
63     tr[rt] = 0;
64 }
65 
66 ll query(int rt, int L, int R, int l, int r)
67 {
68     if(L <= l && R >= r)
69     {
70         return sum[rt][tr[rt]];
71     }
72     int mid = l + r >> 1;
73     pushdown(rt);
74     ll ans = 0;
75     if(L <= mid) ans = (ans + query(rt << 1, L, R, l, mid)) % mod;
76     if(R > mid) ans = (ans + query(rt << 1 | 1, L, R, mid + 1, r)) % mod;
77     return ans;
78 }
79 
80 int main()
81 {
82        n = read();
83        build(1, 1, n);
84        m = read();
85        while(m --)
86        {
87            int op = read(), l = read(), r = read();
88            if(op == 1)
89            {
90                printf("%lld
", query(1, l, r, 1, n));
91            }
92            else
93            {
94                update(1, l, r, 1, n);
95            }
96        }
97 }
View Code