1. https://hihocoder.com/contest/offers24/problem/4
bzoj弹飞绵羊 跟这道题目一模一样。hihocode的题目数据比较水，暴力也可以过。
分块，块内修改+查询。
学习的别人的代码。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e5 + 10; 7 8 int n, m, k; 9 int a[maxn]; 10 int be[maxn], b[maxn], c[maxn]; 11 void up(int i) { 12 if(i + a[i] > n || (i + a[i]) / k != i / k) { 13 b[i] = 1; 14 c[i] = i + a[i]; 15 } else { 16 b[i] = b[i + a[i] ] + 1; 17 c[i] = c[i + a[i] ]; 18 } 19 } 20 int ask(int i) { 21 int r = 0; 22 while(i <= n) { 23 r += b[i]; 24 i = c[i]; 25 } 26 return r; 27 } 28 29 void solve() { 30 scanf("%d", &n); 31 for (int i = 1; i <= n; i++) { 32 scanf("%d", &a[i]); 33 } 34 k = sqrt(n + 0.5); 35 for (int i = n; i >= 1; i--) { 36 up(i); 37 } 38 scanf("%d", &m); 39 int x, y, v; 40 while(m--) { 41 scanf("%d%d", &x, &y); 42 //cout << x << " " << y << endl; 43 if(x == 1) { 44 printf("%d ", ask(y)); 45 } else { 46 scanf("%d", &v); 47 a[y] = v; 48 for (int i = y; i >= y / k * k; i--) { 49 up(i); 50 } 51 } 52 } 53 } 54 55 int main() { 56 // freopen("test.in", "r", stdin); 57 //freopen("test.out", "w", stdout); 58 solve(); 59 return 0; 60 }
2. https://hihocoder.com/problemset/problem/1553?sid=1172120
区间统计，区间计数，主要是没有线段树区间加和的性质，无法维护，利用分块计算计数，然后用计数分布稀疏的特征进行k次幂的计算，比较难。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 typedef long long ll; 4 using namespace std; 5 typedef pair<int, int> pii; 6 const int maxn = 1e5 + 10; 7 const int mod = 1e9 + 7; 8 ll ppow(ll x, ll y) { 9 if(x == 0) return 0; 10 if(x == 1 || y == 0) return 1; 11 ll r = 1; 12 while(y > 0) { 13 if(y & 1) 14 r = (r * x) % mod; 15 y >>= 1; 16 x = (x * x) % mod; 17 } 18 return r; 19 } 20 ll tk[maxn][105]; 21 int n, m, s; 22 int a[maxn]; 23 int be[maxn]; 24 ll res[maxn]; 25 //map<int, int> ma; 26 //map<int, int> mc; 27 int ma[maxn], mc[maxn]; 28 struct node { 29 int x, y, k, id; 30 bool operator<(const node&t) const{ 31 if(be[x] == be[t.x]) { 32 return y < t.y; 33 } 34 return x < t.x; 35 } 36 }; 37 node q[maxn]; 38 ll cur; 39 set<int> se; 40 void add(int x) { 41 mc[ma[x] ]--; 42 ++ma[x]; 43 mc[ma[x] ]++; 44 if(ma[x] == s) { 45 se.insert(x); 46 } 47 } 48 void del(int x) { 49 mc[ma[x] ]--; 50 if(ma[x] == s) { 51 se.erase(x); 52 } 53 --ma[x]; 54 mc[ma[x] ]++; 55 } 56 ll f(int k) { 57 ll r = 0; 58 for (int i = 1; i < s; i++) { 59 r = (r + mc[i] * tk[i][k] % mod) % mod; 60 } 61 for (int x : se) { 62 r = (r + tk[ma[x] ][k]) % mod; 63 } 64 /* 65 for (int i = 1; i <= s; i++) { 66 r = (r + mc[i] * ppow(i, k) % mod) % mod; 67 } 68 for (auto i = ma.upper_bound(s); i != ma.end(); i++) { 69 r = (r + ppow()) 70 }*/ 71 return r; 72 } 73 void init() { 74 for (int i = 0; i <= 100000; i++) { 75 tk[i][0] = 1; 76 for (int j = 1; j <=100; j++) { 77 tk[i][j] = (tk[i][j - 1] * i) % mod; 78 } 79 } 80 } 81 void solve() { 82 scanf("%d%d", &n, &m); 83 //ma.clear(); 84 //mc.clear(); 85 memset(ma, 0, sizeof ma); 86 memset(mc, 0, sizeof mc); 87 se.clear(); 88 cur = 0; 89 s = sqrt(n + 0.5); 90 for (int i = 1; i <= n; i++) { 91 scanf("%d", &a[i]); 92 be[i] = i / s; 93 } 94 int x, y, v; 95 for (int i = 1; i <= m; i++) { 96 scanf("%d%d%d", &x, &y, &v); 97 q[i] = {x, y, v, i}; 98 } 99 sort(q + 1, q + m + 1); 100 for (int i = 1, l = 1, r = 0; i <= m; i++) { 101 //cout << "asd" << endl; 102 while(r < q[i].y) { 103 r++; 104 add(a[r]); 105 } 106 while(l > q[i].x) { 107 l--; 108 add(a[l]); 109 } 110 while(r > q[i].y) { 111 del(a[r]); 112 r--; 113 } 114 while(l < q[i].x) { 115 del(a[l]); 116 l++; 117 } 118 //cout << i << endl; 119 res[q[i].id ] = f(q[i].k); 120 // cout << res[q[i].id ] << endl; 121 } 122 for (int i = 1; i <= m; i++) 123 printf("%lld ", res[i]); 124 } 125 126 int main() { 127 //freopen("test.in", "r", stdin); 128 //freopen("test.out", "w", stdout); 129 init(); 130 int _; 131 scanf("%d", &_); 132 while(_--) 133 solve(); 134 return 0; 135 }
上面的2题算是对分块思想的介绍，主要是知道(l,r),可以很快的计算(l,r+1),(l,r-1),(l+1,r),(l-1,r),然后就可以利用分块的性质。
暂时就这么多吧，有时间做这类题目训练一下。