数列分块入门1
第一题是y总的板子，但是y总的分块就讲了这个基础题目，我觉得还是太浅了，后来讲的就是链表分块，但是后来我去洛谷交了一个数据大一点点的题目，发现会卡常，还算不建议用y总的板子了
代码：
#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 1e5 + 10, M = 350, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
int n;
vector<T> tr;
BIT1(int n) : n(n), tr(n + 1) {}
void add(int x, T v)
{
for (; x <= n; x += x & -x)
tr[x] += v;
}
T sum(int x)
{
T r = 0;
for (; x; x -= x & -x)
r += tr[x];
return r;
}
T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
int n, m;
vector<vector<T>> t1, t2, t3, t4;
BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
void init(int n_, int m_)
{
n = n_;
m = m_;
t1.assign(n + 1, vector<T>(m + 1, T{}));
t2.assign(n + 1, vector<T>(m + 1, T{}));
t3.assign(n + 1, vector<T>(m + 1, T{}));
t4.assign(n + 1, vector<T>(m + 1, T{}));
}
void _add(int x, int y, const T &v)
{
for (int i = x; i <= n; i += i & -i)
for (int j = y; j <= m; j += j & -j)
{
t1[i][j] += v;
t2[i][j] += v * x;
t3[i][j] += v * y;
t4[i][j] += v * x * y;
}
}
void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
{
_add(x1, y1, v);
_add(x1, y2 + 1, -v);
_add(x2 + 1, y1, -v);
_add(x2 + 1, y2 + 1, v);
}
T prefixSum(int x, int y)
{
T r{};
for (int i = x; i > 0; i -= i & -i)
for (int j = y; j > 0; j -= j & -j)
r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
return r;
}
T rangeSum(int x1, int y1, int x2, int y2)
{
if (x1 > x2 || y1 > y2)
return T{};
return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
}
};
struct Random
{
mt19937_64 rng;
Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
template <typename T>
void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
ll res = 1 % p;
a %= p;
while (b)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
/*
*/
ll n, m, len;
ll a[N], add[M], sum[M];
ll get(ll i)
{
return i / len;
}
void change(ll l, ll r, ll d)
{
if (get(l) == get(r))
{
rep(i, l, r) a[i] += d, sum[get(i)] += d;
}
else
{
ll i = l, j = r;
while (get(i) == get(l))
a[i] += d, sum[get(i)] += d, i++;
while (get(j) == get(r))
a[j] += d, sum[get(j)] += d, j--;
rep(k, get(i), get(j))
{
sum[k] += len * d;
add[k] += d;
}
}
}
ll query(ll l, ll r)
{
ll ret = 0;
if (get(l) == get(r))
{
rep(i, l, r) ret += a[i] + add[get(i)];
}
else
{
ll i = l, j = r;
while (get(i) == get(l))
ret += a[i] + add[get(i)], i++;
while (get(j) == get(r))
ret += a[j] + add[get(j)], j--;
rep(k, get(i), get(j))
{
ret += sum[k];
}
}
return ret;
}
void solve()
{
cin >> n ;
m=n;
rep(i, 1, n) cin >> a[i];
len = sqrt(n);
rep(i, 1, n)
{
sum[get(i)] += a[i];
}
while (m--)
{
string op;
cin >> op;
if (op == "0")
{
ll l, r, d;
cin >> l >> r >> d;
change(l, r, d);
}
else
{
ll l, r,d;
cin >> l >> r>>d;
ll ans = query(r, r);
cout << ans << endl;
}
}
}
int main()
{
IOS;
int _ = 1;
// cin>>_;//如果是多组数据
while (_--)
{
solve();
}
return 0;
}下面的是暂时不卡常的代码:
#include <bits/stdc++.h>
using namespace std;
//CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p<<1
#define rc p<<1|1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x)&(-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps=1e-5;
const int N = 3e5 + 10,M=550,K=26;
const ll MOD = 1e9 + 7,Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template<typename T> bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template<typename T> void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template<typename T> struct BIT1 { int n; vector<T> tr; BIT1(int n) : n(n), tr(n+1) {} void add(int x, T v) { for(;x<=n;x+=x&-x) tr[x]+=v; } T sum(int x) { T r=0; for(;x;x-=x&-x) r+=tr[x]; return r; } T range(int l, int r) { return sum(r)-sum(l-1); } };
template<typename T> struct BIT2 { int n,m; vector<vector<T>> t1,t2,t3,t4; BIT2(int n_=0,int m_=0) { init(n_,m_); } void init(int n_,int m_) { n=n_; m=m_; t1.assign(n+1,vector<T>(m+1,T{})); t2.assign(n+1,vector<T>(m+1,T{})); t3.assign(n+1,vector<T>(m+1,T{})); t4.assign(n+1,vector<T>(m+1,T{})); } void _add(int x,int y,const T& v) { for(int i=x;i<=n;i+=i&-i) for(int j=y;j<=m;j+=j&-j) { t1[i][j]+=v; t2[i][j]+=v*x; t3[i][j]+=v*y; t4[i][j]+=v*x*y; } } void rangeAdd(int x1,int y1,int x2,int y2,const T& v) { _add(x1,y1,v); _add(x1,y2+1,-v); _add(x2+1,y1,-v); _add(x2+1,y2+1,v); } T prefixSum(int x,int y) { T r{}; for(int i=x;i>0;i-=i&-i) for(int j=y;j>0;j-=j&-j) r+=t1[i][j]*(x+1)*(y+1)-t2[i][j]*(y+1)-t3[i][j]*(x+1)+t4[i][j]; return r; } T rangeSum(int x1,int y1,int x2,int y2) { if(x1>x2||y1>y2) return T{}; return prefixSum(x2,y2)-prefixSum(x1-1,y2)-prefixSum(x2,y1-1)+prefixSum(x1-1,y1-1); } };
struct Random { mt19937_64 rng; Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {} ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); } ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); } double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); } bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); } template<typename T> void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); } };
ll qmi(ll a, ll b, ll p) { ll res = 1 % p; a %= p; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; }
/*
*/
ll n, len;
ll a[N], add[M]; // 移除了不必要的sum数组
ll get(ll i) {
return (i - 1) / len; // 通常块编号从0开始，或者用(i-1)/len +1从1开始，这里根据你的习惯调整。注意与后续操作匹配。
}
void change(ll l, ll r, ll d) {
int bl = get(l), br = get(r);
if (bl == br) {
// 情况1：l和r在同一个块内，暴力修改
for (ll i = l; i <= r; i++) {
a[i] += d;
}
} else {
// 情况2：跨块
// 处理左侧不完整块
for (ll i = l; i <= (bl + 1) * len; i++) { // 假设块编号从0开始，bl是l所在的块
a[i] += d;
}
// 处理右侧不完整块
for (ll i = br * len + 1; i <= r; i++) { // br是r所在的块
a[i] += d;
}
// 处理中间的完整块
for (int k = bl + 1; k < br; k++) {
add[k] += d;
}
}
}
void solve() {
cin >> n;
len = sqrt(n); // 块的大小
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int m = n;
while (m--) {
int opt;
ll l, r, c;
cin >> opt >> l >> r >> c;
if (opt == 0) {
change(l, r, c);
} else {
// 单点查询：直接输出 a[r] + 其所在块的add标记
cout << a[r] + add[get(r)] << endl;
}
}
}
int main() {
IOS;
int _ = 1;
while (_--) {
solve();
}
return 0;
}数列分块入门2
代码：
#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 1e5 + 10, M = 350, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
int n;
vector<T> tr;
BIT1(int n) : n(n), tr(n + 1) {}
void add(int x, T v)
{
for (; x <= n; x += x & -x)
tr[x] += v;
}
T sum(int x)
{
T r = 0;
for (; x; x -= x & -x)
r += tr[x];
return r;
}
T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
int n, m;
vector<vector<T>> t1, t2, t3, t4;
BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
void init(int n_, int m_)
{
n = n_;
m = m_;
t1.assign(n + 1, vector<T>(m + 1, T{}));
t2.assign(n + 1, vector<T>(m + 1, T{}));
t3.assign(n + 1, vector<T>(m + 1, T{}));
t4.assign(n + 1, vector<T>(m + 1, T{}));
}
void _add(int x, int y, const T &v)
{
for (int i = x; i <= n; i += i & -i)
for (int j = y; j <= m; j += j & -j)
{
t1[i][j] += v;
t2[i][j] += v * x;
t3[i][j] += v * y;
t4[i][j] += v * x * y;
}
}
void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
{
_add(x1, y1, v);
_add(x1, y2 + 1, -v);
_add(x2 + 1, y1, -v);
_add(x2 + 1, y2 + 1, v);
}
T prefixSum(int x, int y)
{
T r{};
for (int i = x; i > 0; i -= i & -i)
for (int j = y; j > 0; j -= j & -j)
r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
return r;
}
T rangeSum(int x1, int y1, int x2, int y2)
{
if (x1 > x2 || y1 > y2)
return T{};
return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
}
};
struct Random
{
mt19937_64 rng;
Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
template <typename T>
void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
ll res = 1 % p;
a %= p;
while (b)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
/*
*/
ll n, len;
ll a[N], add[M];
vll sorted[M];
ll get(ll i)
{
return (i - 1) / len + 1;
}
void build(ll block)
{
ll st = (block - 1) * len + 1;
ll ed = min((block)*len, n);
sorted[block].clear();
rep(i, st, ed)
{
sorted[block].push_back(a[i]);
}
sort(all(sorted[block]));
}
void change(ll l, ll r, ll d)
{
ll bl = get(l), br = get(r);
if (bl == br)
{
rep(i, l, r) a[i] += d;
build(bl);
}
else
{
rep(i, l, (bl)*len) a[i] += d;
build(bl);
rep(i, (br - 1) * len + 1, r) a[i] += d;
build(br);
rep(i, bl + 1, br - 1) add[i] += d;
}
}
ll query_less(ll l, ll r, ll c)
{
ll x = c * c;
ll bl = get(l), br = get(r);
ll ans = 0;
if (bl == br)
{
rep(i, l, r)
{
if (a[i] + add[bl] < x)
ans++;
}
}
else
{
rep(i, l, bl * len)
{
if (a[i] + add[bl] < x)
ans++;
}
rep(i, (br - 1) * len + 1, r)
{
if (a[i] + add[br] < x)
ans++;
}
rep(i, bl + 1, br - 1)
{
ll d = x - add[i];
ll pos = lower_bound(all(sorted[i]), d) - sorted[i].begin();
ans += pos;
}
}
return ans;
}
void solve()
{
cin >> n;
len = sqrt(n);
ll t = get(n);
rep(i, 1, n) cin >> a[i];
rep(i, 1, t)
{
add[i] = 0;
build(i);
}
rep(i, 1, n)
{
ll op, l, r, d;
cin >> op >> l >> r >> d;
if (op == 0)
{
change(l, r, d);
}
else
{
ll ans = query_less(l, r, d);
cout << ans << endl;
}
}
}
int main()
{
IOS;
int _ = 1;
// cin>>_;//如果是多组数据
while (_--)
{
solve();
}
return 0;
}数列分块入门3
#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 2e5 + 10, M = 550, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
int n;
vector<T> tr;
BIT1(int n) : n(n), tr(n + 1) {}
void add(int x, T v)
{
for (; x <= n; x += x & -x)
tr[x] += v;
}
T sum(int x)
{
T r = 0;
for (; x; x -= x & -x)
r += tr[x];
return r;
}
T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
int n, m;
vector<vector<T>> t1, t2, t3, t4;
BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
void init(int n_, int m_)
{
n = n_;
m = m_;
t1.assign(n + 1, vector<T>(m + 1, T{}));
t2.assign(n + 1, vector<T>(m + 1, T{}));
t3.assign(n + 1, vector<T>(m + 1, T{}));
t4.assign(n + 1, vector<T>(m + 1, T{}));
}
void _add(int x, int y, const T &v)
{
for (int i = x; i <= n; i += i & -i)
for (int j = y; j <= m; j += j & -j)
{
t1[i][j] += v;
t2[i][j] += v * x;
t3[i][j] += v * y;
t4[i][j] += v * x * y;
}
}
void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
{
_add(x1, y1, v);
_add(x1, y2 + 1, -v);
_add(x2 + 1, y1, -v);
_add(x2 + 1, y2 + 1, v);
}
T prefixSum(int x, int y)
{
T r{};
for (int i = x; i > 0; i -= i & -i)
for (int j = y; j > 0; j -= j & -j)
r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
return r;
}
T rangeSum(int x1, int y1, int x2, int y2)
{
if (x1 > x2 || y1 > y2)
return T{};
return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
}
};
struct Random
{
mt19937_64 rng;
Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
template <typename T>
void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
ll res = 1 % p;
a %= p;
while (b)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
/*
*/
ll n, len;
ll a[N], add[M];
vll tmp[M];
ll get(ll i)
{
return (i - 1) / len + 1;
}
void build(ll block)
{
ll st = (block - 1) * len + 1;
ll ed = min(block * len, n);
tmp[block].clear();
rep(i, st, ed)
{
tmp[block].push_back(a[i]);
}
sort(all(tmp[block]));
}
void change(ll l, ll r, ll d)
{
ll bl = get(l), br = get(r);
if (bl == br)
{
rep(i, l, r) a[i] += d;
build(bl);
}
else
{
rep(i, l, min(bl * len, n)) a[i] += d;
build(bl);
rep(i, (br - 1) * len + 1, r) a[i] += d;
build(br);
rep(i, bl + 1, br - 1) add[i] += d;
}
}
ll query(ll l, ll r, ll c)
{
ll bl = get(l), br = get(r);
ll ans = -INF;
if (bl == br)
{
rep(i, l, r)
{
if (a[i] + add[bl] < c)
cmax(ans, a[i] + add[bl]);
}
if (ans == -INF)
return -1;
return ans;
}
else
{
rep(i, l, min(bl * len, n))
{
if (a[i] + add[bl] < c)
cmax(ans, a[i] + add[bl]);
}
rep(i, (br - 1) * len + 1, r)
{
if (a[i] + add[br] < c)
cmax(ans, a[i] + add[br]);
}
rep(i, bl + 1, br - 1)
{
ll d = c - add[i];
ll num = lower_bound(all(tmp[i]), d) - tmp[i].begin();
auto it = lower_bound(all(tmp[i]), d);
if (it != tmp[i].begin())
{
it--;
ll now = *it + add[i];
if (now < c)
{
cmax(ans, now);
}
}
}
if (ans == -INF)
return -1;
return ans;
}
}
void solve()
{
cin >> n;
len = sqrt(n);
ll cnt = get(n);
rep(i, 1, n) cin >> a[i];
rep(i, 1, cnt)
{
add[i] = 0;
build(i);
}
rep(i, 1, n)
{
ll op, l, r, c;
cin >> op >> l >> r >> c;
if (op == 0)
{
change(l, r, c);
}
else
{
ll ans = query(l, r, c);
cout << ans << endl;
}
}
}
int main()
{
IOS;
int _ = 1;
// cin>>_;//如果是多组数据
while (_--)
{
solve();
}
return 0;
}数列分块入门4
P13979 数列分块入门 4
题目背景
洛谷的数列分块入门系列的测试数据范围和原题有不同。
题目描述
给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间加法，区间求和。
输入格式
第一行输入一个数字 $n$。
第二行输入 $n$ 个数字，第 $i$ 个数字为 $a_i$，以空格隔开。
接下来输入 $n$ 行询问，每行输入四个数字 $\mathrm{opt}$、$l$、$r$、$c$，以空格隔开。
若 $\mathrm{opt} = 0$，表示将位于 $[l, r]$ 的之间的数字都加 $c$。
若 $\mathrm{opt} = 1$，表示询问位于 $[l, r]$ 的所有数字的和 $\bmod (c+1)$。你需要输出非负的余数值。
输出格式
对于每次询问，输出一行一个数字表示答案。
输入输出样例 #1
输入 #1
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4
输出 #1
1
4
说明/提示
子任务
子任务 1（40 分）：$1 \leq n \leq 50000, -2^{31} \leq a_i,c \leq 2^{31}-1$。
子任务 2（60 分）：$1 \leq n \leq 300000, -2^{31} \leq a_i,c \leq 2^{31}-1$。
对于所有测试数据，满足 $1 \leq n \leq 300000, -2^{31} \leq a_i,c \leq 2^{31}-1$。$1 \leq l \leq r \leq n$。$\mathrm{opt} \in {0,1}, 1 \leq l \leq r\leq n$。每次操作后的 $a_i$ 满足 $-2^{31} \leq a_i \leq 2^{31}-1$。特别地，数据保证当 $\mathrm{opt}=1$ 时，$c\geq 0$。
先吐槽一下vjudge的评测系统，太水了，我很多边界和细节都没有注意，给我一次过了，现在果断换上洛谷的题面和评测，第一次在Vjudge上写还真以为会了呢，结果一大堆细节没有处理好，真是会让人产生学会了的幻觉啊！！！
代码：
#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 3e5 + 10, M = 550, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
int n;
vector<T> tr;
BIT1(int n) : n(n), tr(n + 1) {}
void add(int x, T v)
{
for (; x <= n; x += x & -x)
tr[x] += v;
}
T sum(int x)
{
T r = 0;
for (; x; x -= x & -x)
r += tr[x];
return r;
}
T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
int n, m;
vector<vector<T>> t1, t2, t3, t4;
BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
void init(int n_, int m_)
{
n = n_;
m = m_;
t1.assign(n + 1, vector<T>(m + 1, T{}));
t2.assign(n + 1, vector<T>(m + 1, T{}));
t3.assign(n + 1, vector<T>(m + 1, T{}));
t4.assign(n + 1, vector<T>(m + 1, T{}));
}
void _add(int x, int y, const T &v)
{
for (int i = x; i <= n; i += i & -i)
for (int j = y; j <= m; j += j & -j)
{
t1[i][j] += v;
t2[i][j] += v * x;
t3[i][j] += v * y;
t4[i][j] += v * x * y;
}
}
void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
{
_add(x1, y1, v);
_add(x1, y2 + 1, -v);
_add(x2 + 1, y1, -v);
_add(x2 + 1, y2 + 1, v);
}
T prefixSum(int x, int y)
{
T r{};
for (int i = x; i > 0; i -= i & -i)
for (int j = y; j > 0; j -= j & -j)
r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
return r;
}
T rangeSum(int x1, int y1, int x2, int y2)
{
if (x1 > x2 || y1 > y2)
return T{};
return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
}
};
struct Random
{
mt19937_64 rng;
Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
template <typename T>
void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
ll res = 1 % p;
a %= p;
while (b)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
/*
*/
ll n, len;
ll a[N], add[M], sum[M];
ll get(ll i)
{
return (i - 1) / len + 1;
}
void modify(ll l, ll r, ll d)
{
ll bl = get(l), br = get(r);
if (bl == br)
{
rep(i, l, r)
{
a[i] += d;
sum[bl] += d;
}
}
else
{
for (ll i = l; i <= min(bl * len, n); i++)
{
a[i] += d;
sum[bl] += d;
}
for (ll i = (br - 1) * len + 1; i <= r; i++)
{
a[i] += d;
sum[br] += d;
}
for (ll i = bl + 1; i < br; i++)
{
add[i] += d;
}
}
}
ll query(ll l, ll r, ll c)
{
ll m = c + 1;
ll tot = 0;
ll bl = get(l), br = get(r);
if (bl == br)
{
rep(i, l, r)
{
tot = (tot + a[i] + add[bl]);
}
}
else
{
for (ll i = l; i <= min(bl * len, n); i++)
{
tot = (tot + a[i] + add[bl]);
}
for (ll i = (br - 1) * len + 1; i <= r; i++)
{
tot = (tot + a[i] + add[br]);
}
for (ll i = bl + 1; i < br; i++)
{
ll st = (i - 1) * len + 1;
ll ed = min(i * len, n);
ll far = ed - st + 1;
tot += sum[i] + add[i] * far;
}
}
return mod(tot, m);
}
void solve()
{
cin >> n;
len = sqrt(n);
// mem(add, 0);
// mem(sum, 0);
rep(i, 1, n)
{
cin >> a[i];
sum[get(i)] += a[i];
}
rep(i, 1, n)
{
ll op, l, r, c;
cin >> op >> l >> r >> c;
if (op == 0)
{
modify(l, r, c);
}
else
{
ll ans = query(l, r, c);
cout << ans << endl;
}
}
}
int main()
{
IOS;
int _ = 1;
// cin>>_;//如果是多组数据
while (_--)
{
solve();
}
return 0;
}数列分块入门 5
P13980 数列分块入门 5
题目背景
洛谷的数列分块入门系列的测试数据范围和原题有不同。
题目描述
给出一个长为 $n$ 的数列 $a_1 \ldots a_n$，以及 $n$ 个操作，操作涉及区间开方，区间求和。
输入格式
第一行输入一个数字 $n$。
第二行输入 $n$ 个数字，第 $i$ 个数字为 $a_i$，以空格隔开。
接下来输入 $n$ 行询问，每行输入三个数字 $\mathrm{opt}, l, r$，以空格隔开。
若 $\mathrm{opt} = 0$，表示将位于 $[l, r]$ 的之间的数字都开方。对于区间中每个 $a_i(l\le i\le r),: a_i \leftarrow \left\lfloor \sqrt{a_i}\right\rfloor$
若 $\mathrm{opt} = 1$，表示询问位于 $[l, r]$ 的所有数字的和。
输出格式
对于每次询问，输出一行一个数字表示答案。
输入输出样例 #1
输入 #1
4
1 2 2 3
0 1 3
1 1 4
0 1 2
1 1 2
输出 #1
6
2
说明/提示
子任务
子任务 1（40 分）：$1 \leq n \leq 50000, 0 \leq a_i,\mathrm{ans} \leq 2^{31}-1$。
子任务 2（60 分）：$1 \leq n \leq 300000, 0 \leq a_i \leq 2^{31}-1$，$0\leq \mathrm{ans}\leq 2^{63}-1$。
对于所有测试数据，满足 $1 \leq n \leq 300000, 0 \leq a_i \leq 2^{31}-1$，$0\leq \mathrm{ans} \leq 2^{63}-1$。$1 \leq l \leq r \leq n$。$\mathrm{opt} \in {0,1}, 1 \leq l \leq r\leq n$。每次操作后的 $a_i$ 满足 $0 \leq a_i \leq 2^{31}-1$。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10, M = 550;
ll n, len;
ll a[N], sum[M]; // sum记录每个块的和
bool flag[M]; // flag标记块是否全为0或1（开方后不再变化）
ll get(ll i) {
return (i - 1) / len + 1;
}
void build(ll block) {
ll st = (block - 1) * len + 1;
ll ed = min(block * len, n);
sum[block] = 0;
flag[block] = true;
for (ll i = st; i <= ed; i++) {
sum[block] += a[i];
if (a[i] > 1) {
flag[block] = false;
}
}
}
void sqrt_range(ll l, ll r) {
ll bl = get(l), br = get(r);
if (bl == br) {
if (flag[bl]) return;
for (ll i = l; i <= r; i++) {
ll old = a[i];
a[i] = (ll)sqrt(a[i]);
sum[bl] += (a[i] - old);
}
flag[bl] = true;
ll st = (bl - 1) * len + 1;
ll ed = min(bl * len, n);
for (ll i = st; i <= ed; i++) {
if (a[i] > 1) {
flag[bl] = false;
break;
}
}
} else {
if (!flag[bl]) {
for (ll i = l; i <= bl * len; i++) {
ll old = a[i];
a[i] = (ll)sqrt(a[i]);
sum[bl] += (a[i] - old);
}
flag[bl] = true;
ll st = (bl - 1) * len + 1;
ll ed = bl * len;
for (ll i = st; i <= ed; i++) {
if (a[i] > 1) {
flag[bl] = false;
break;
}
}
}
if (!flag[br]) {
for (ll i = (br - 1) * len + 1; i <= r; i++) {
ll old = a[i];
a[i] = (ll)sqrt(a[i]);
sum[br] += (a[i] - old);
}
flag[br] = true;
ll st = (br - 1) * len + 1;
ll ed = min(br * len, n);
for (ll i = st; i <= ed; i++) {
if (a[i] > 1) {
flag[br] = false;
break;
}
}
}
for (ll i = bl + 1; i <= br - 1; i++) {
if (flag[i]) continue;
flag[i] = true;
ll st = (i - 1) * len + 1;
ll ed = min(i * len, n);
for (ll j = st; j <= ed; j++) {
ll old = a[j];
a[j] = (ll)sqrt(a[j]);
sum[i] += (a[j] - old);
if (a[j] > 1) {
flag[i] = false;
}
}
}
}
}
ll query_sum(ll l, ll r) {
ll bl = get(l), br = get(r);
ll tot = 0;
if (bl == br) {
for (ll i = l; i <= r; i++) {
tot += a[i];
}
} else {
for (ll i = l; i <= bl * len; i++) {
tot += a[i];
}
for (ll i = (br - 1) * len + 1; i <= r; i++) {
tot += a[i];
}
for (ll i = bl + 1; i <= br - 1; i++) {
tot += sum[i];
}
}
return tot;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
len = sqrt(n);
ll blocks = get(n);
for (ll i = 1; i <= n; i++) {
cin >> a[i];
}
for (ll i = 1; i <= blocks; i++) {
build(i);
}
for (ll i = 1; i <= n; i++) {
ll op, l, r;
cin >> op >> l >> r ;
if (op == 0) {
sqrt_range(l, r);
} else {
ll result = query_sum(l, r);
cout << result << endl;
}
}
return 0;
}