数列分块入门
入门 1-区间加法-单点查询
ll n,a[maxn],lazy[maxn]; int main() { n = read; for(int i=1; i<=n; i++) a[i] = read; int blk = sqrt(n); for(int ii=1; ii<=n; ii++) { int op = read,l = read,r = read,c = read; if( op == 0) { for(int i=l; i<min(r+1,(l/blk+1)*blk); i++) { a[i] += c; } for(int i=l/blk+1; i<r/blk; i++) { lazy[i] += c; } if(l / blk != r / blk) { for(int i=r/blk*blk; i<=r; i++) a[i] += c; } } else { printf("%lld\n",a[r] + lazy[r/blk]); } } return 0; } /** 4 1 2 2 3 0 1 3 1 1 0 1 0 0 1 2 2 1 0 2 0 2 5 **/
入门 2-区间加法-区间查询
const int maxn = 1e5 + 7; ll n, a[maxn]; vector<ll> vet[maxn]; ll blk, lazy[maxn], b[maxn]; void reget(int id) { vet[id].clear(); for (int i = (id - 1) * blk + 1; i <= min(n, id * blk); i++) { vet[id].push_back(a[i]); } sort(vet[id].begin(), vet[id].end()); } void update(ll l, ll r, ll c) { for (int i = l; i <= min(b[l]*blk, r); i++) a[i] += c; reget(b[l]); if (b[l] != b[r]) { for (int i = (b[r] - 1) * blk + 1; i <= r; i++) a[i] += c; reget(b[r]); } for (int i = b[l] + 1; i <= b[r] - 1; i++) { lazy[i] += c; } } ll query(ll l, ll r, ll val) { ll ret = 0; for (int i = l; i <= min(b[l]*blk, r); i++) { if (a[i] + lazy[b[l]] < val) ++ ret; } if (b[l] != b[r]) { for (int i = (b[r] - 1) * blk + 1; i <= r; i++) { if (a[i] + lazy[b[r]] < val) ++ ret; } } for (int i = b[l] + 1; i <= b[r] - 1; i++) { int get = val - lazy[i]; // ret += upper_bound(vet[i].begin(),vet[i].end(),get) - lower_bound(vet[i].begin(),vet[i].end(),get); ret += lower_bound(vet[i].begin(), vet[i].end(), get) - vet[i].begin(); } return ret; } int main() { n = read; for (int i = 1; i <= n; i++) a[i] = read; blk = sqrt(n); for (int i = 1; i <= n; i++) { b[i] = (i - 1) / blk + 1; vet[b[i]].push_back(a[i]); } for (int i = 1; i <= b[n]; i++) sort(vet[i].begin(), vet[i].end()); for (int i = 1; i <= n; i++) { int op = read, l = read, r = read, c = read; if (op == 0) update(l, r, c); else printf("%lld\n", query(l, r, c * c)); } return 0; } /** 4 1 2 2 3 0 1 3 1 1 1 3 2 1 1 4 1 1 2 3 2 3 0 2 **/
入门 3-区间加法-单点查询
const int maxn = 1e5 + 7; ll n, a[maxn]; vector<ll> vet[maxn]; ll blk, lazy[maxn], b[maxn]; void reget(int id) { vet[id].clear(); for (int i = (id - 1) * blk + 1; i <= min(n, id * blk); i++) { vet[id].push_back(a[i]); } sort(vet[id].begin(), vet[id].end()); } void update(ll l, ll r, ll c) { for (int i = l; i <= min(b[l]*blk, r); i++) a[i] += c; reget(b[l]); if (b[l] != b[r]) { for (int i = (b[r] - 1) * blk + 1; i <= r; i++) a[i] += c; reget(b[r]); } for (int i = b[l] + 1; i <= b[r] - 1; i++) { lazy[i] += c; } } ll query(ll l, ll r, ll val) { ll ret = -1; for (int i = l; i <= min(b[l]*blk, r); i++) { if (a[i] + lazy[b[l]] < val) ret = max(ret, a[i] + lazy[b[l]]); } if (b[l] != b[r]) { for (int i = (b[r] - 1) * blk + 1; i <= r; i++) { if (a[i] + lazy[b[r]] < val) ret = max(ret, a[i] + lazy[b[r]]); } } for (int i = b[l] + 1; i <= b[r] - 1; i++) { ll get = val - lazy[i]; vector<ll>::iterator l = lower_bound(vet[i].begin(), vet[i].end(), get); if (l == vet[i].begin()) continue; l --; ret = max(ret, *l + lazy[i]); } return ret; } int main() { n = read; for (int i = 1; i <= n; i++) a[i] = read; blk = sqrt(n); for (int i = 1; i <= n; i++) { b[i] = (i - 1) / blk + 1; vet[b[i]].push_back(a[i]); } for (int i = 1; i <= b[n]; i++) sort(vet[i].begin(), vet[i].end()); for (int i = 1; i <= n; i++) { int op = read, l = read, r = read, c = read; if (op == 0) update(l, r, c); else printf("%lld\n", query(l, r, c)); // debug(i); } return 0; } /** 4 1 2 2 3 0 1 3 1 1 1 4 4 0 1 2 2 1 1 2 4 3 -1 **/
入门 4-区间加法-区间查询
ll n,a[maxn]; ll blk,lazy[maxn],b[maxn],sum[maxn]; void update(ll l,ll r,ll c) { for(int i=l; i<=min(b[l]*blk,r); i++) a[i] += c,sum[b[l]] += c; if(b[l] != b[r]) { for(int i=(b[r] - 1) * blk+1; i<=r; i++) a[i] += c,sum[b[r]] += c; } for(int i=b[l]+1; i<=b[r] - 1; i++) { lazy[i] += c; } } ll query(ll l,ll r,ll val) { ll ret = 0; for(int i=l; i<=min(b[l]*blk,r); i++) { ret += a[i] + lazy[b[l]]; ret %= (val + 1); } if(b[l] != b[r]) { for(int i=(b[r]-1)*blk+1; i<=r; i++) { ret += a[i] + lazy[b[r]]; ret %= (val + 1); } } for(int i=b[l]+1; i<=b[r]-1; i++) { ll add = lazy[i] * blk % (val + 1); ret += (sum[i] + add) % (val + 1); ret %= (val + 1); } return ret; } int main() { n = read; for(int i=1; i<=n; i++) a[i] = read; blk = sqrt(n); for(int i=1; i<=n; i++) { b[i] = (i - 1) / blk + 1; sum[b[i]] += a[i]; } for(int i=1; i<=n; i++) { int op = read,l = read,r = read,c = read; if(op == 0) update(l,r,c); else printf("%lld\n",query(l,r,c)); } return 0; } /** 4 1 2 2 3 0 1 3 1 1 1 4 4 0 1 2 2 1 1 2 4 1 4 **/
入门 5-区间开方-区间查询
ll n,a[maxn]; ll blk,lazy[maxn],b[maxn],sum[maxn]; bool vis[maxn]; bool check(int id) { if(vis[id]) return true; for(int i=(id-1)*blk+1; i<=min(n,blk*id); i++) { if(a[i] > 1) return false; } return vis[id] = 1; } void update(ll l,ll r) { if(!check(b[l])) { for(int i=l; i<=min(b[l]*blk,r); i++) { sum[b[l]] -= a[i]; a[i] = sqrt(a[i]); sum[b[l]] += a[i]; } } if(b[l] != b[r] && !check(b[r])) { for(int i=(b[r]-1)*blk+1; i<=r; i++) { sum[b[r]] -= a[i]; a[i] = sqrt(a[i]); sum[b[r]] += a[i]; } } for(int i=b[l]+1; i<=b[r]-1; i++) { if(!check(i)) { sum[i] = 0; for(int j=(i-1)*blk+1; j<=i*blk; j++) { a[j] = sqrt(a[j]); sum[i] += a[j]; } } } } ll query(ll l,ll r) { ll ret = 0; for(int i=l; i<=min(b[l]*blk,r); i++) { ret += a[i]; } if(b[l] != b[r]) { for(int i=(b[r]-1)*blk+1; i<=r; i++) { ret += a[i]; } } for(int i=b[l]+1; i<=b[r]-1; i++) { ret += sum[i]; } return ret; } int main() { n = read; for(int i=1; i<=n; i++) a[i] = read; blk = sqrt(n); for(int i=1; i<=n; i++) { b[i] = (i - 1) / blk + 1; sum[b[i]] += a[i]; } for(int i=1; i<=n; i++) { int op = read,l = read,r = read,c = read; if(op == 0) update(l,r); else printf("%lld\n",query(l,r)); } return 0; } /** 4 1 2 2 3 0 1 3 1 1 1 4 4 0 1 2 2 1 1 2 4 6 2 **/
