（咕咕咕了好久qwq.）
分块1
给出一个长为n的数列，以及n个操作，操作涉及区间加法，单点查值。
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{
int sum = 0,p = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
p = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
(sum *= 10) += ch - '0';
ch = getchar();
}
return sum * p;
}
const int maxn = 50005;
int n,blo;
int v[maxn],block[maxn],atag[maxn];
void add(int a,int b,int c)
{
for(int i = a;i <= min(block[a] * blo,b);i++)
v[i] += c;
if(block[a] != block[b])
for(int i = (block[b] - 1)* blo + 1;i <= b;i++)
v[i] += c;
for(int i = block[a] + 1;i <= block[b] - 1;i++)
atag[i] += c;
}
int main()
{
n = read();
blo = sqrt(n);
for(int i = 1;i <= n;i++)
v[i] = read();
for(int i = 1;i <= n;i++)
block[i] = (i - 1)/blo + 1;
for(int i = 1;i <= n;i++)
{
int opt = read(),a = read(),b = read(),c = read();
if(opt == 0)
add(a,b,c);
if(opt == 1)
printf("%d
",v[b] + atag[block[b]]);
}
return 0;
}
分块2
给出一个长为n的数列，以及n个操作，操作涉及区间加法，询问区间内小于某个值x的元素个数。
//区间加法，询问区间内小于某个值的元素个数 #include<cstdio> #include<algorithm> #include<cmath> #include<vector> #include<iostream> using namespace std; inline int read()//快读 { int sum = 0,p = 1; char ch = getchar(); while(ch < '0'|| ch > '9') { if(ch == '-') p = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (sum *= 10) += ch - '0'; ch = getchar(); } return sum * p; } const int maxn = 50005; int n,blo; int v[maxn],block[maxn],atag[maxn]; vector<int>ve[505]; void reset(int x) { ve[x].clear(); for(int i = (x - 1) *blo + 1;i <= min(x * blo , n);i++) ve[x].push_back(v[i]); sort(ve[x].begin(),ve[x].end()); } void add(int a,int b,int c) { for(int i = a;i <= min(block[a] *blo,b);i++) v[i] += c; reset(block[a]); if(block[a] != block[b]) { for(int i = (block[b] - 1)* blo + 1;i <= b;i++) v[i] += c; reset(block[b]); } for(int i = block[a] + 1;i <= block[b] - 1;i++) atag[i] += c; } int query(int a,int b,int c) { int ans = 0; for(int i = a;i <= min(block[a] * blo , b);i++) if(v[i] + atag[block[i]]< c) ans++; if(block[a] != block[b]) for(int i = (block[b] - 1) * blo + 1;i <= b;i++) if(v[i] +atag[block[i]] < c) ans++; for(int i = block[a] + 1;i <= block[b] - 1;i++) { int x = c - atag[i]; ans += lower_bound(ve[i].begin(),ve[i].end(),x) - ve[i].begin(); } return ans; } int main() { n = read(); blo = sqrt(n); for(int i = 1;i <= n;i++) v[i] = read(); for(int i = 1;i <= n;i++) { block[i] = (i - 1) / blo + 1; ve[block[i]].push_back(v[i]); } for(int i = 1;i <= block[n];i++) sort(ve[i].begin(),ve[i].end()); for(int i = 1;i <= n;i++) { int opt = read(),a = read(),b = read(),c = read(); if(opt == 0) add(a,b,c); if(opt == 1) printf("%d ",query(a,b,c * c)); } return 0; }
分块3
给出一个长为n 的数列，以及n 个操作，操作涉及区间加法，询问区间内小于某个值x 的前驱（比其小的最大元素）。
//区间加法，询问区间内小于某个值x的前驱（比其小的最大前驱）
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
inline int read()//快读
{
int sum = 0,p = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
p = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
(sum *= 10) += ch - '0';
ch = getchar();
}
return sum * p;
}
const int maxn = 100005;
int n,blo;
int v[maxn],block[maxn],atag[maxn];
set<int>st[105];
void add(int a,int b,int c)
{
for(int i = a;i <= min(block[a] * blo , b);i++)
{
st[block[a]].erase(v[i]);
v[i] += c;
st[block[a]].insert(v[i]);
}
if(block[a] != block[b])
for(int i = (block[b] - 1) * blo + 1;i <= b;i++)
{
st[block[b]].erase(v[i]);
v[i] += c;
st[block[b]].insert(v[i]);
}
for(int i = block[a] + 1;i <= block[b] - 1;i++)
atag[i] += c;
}
int query(int a,int b,int c)
{
int ans = -1;
for(int i = a;i <= min(block[a] * blo , b);i++)
{
int cnt = v[i] + atag[block[a]];
if(cnt < c)
ans = max(ans,cnt);
}
if(block[a] != block[b])
for(int i = (block[b] - 1) * blo + 1;i <= b;i++)
{
int cnt = v[i] + atag[block[b]];
if(cnt < c)
ans = max(ans,cnt);
}
for(int i = block[a] + 1;i <= block[b] - 1;i++)
{
int cnt = c - atag[i];
set<int>::iterator it = st[i].lower_bound(cnt);
if(it == st[i].begin())
continue;
--it;
ans = max(ans,*it + atag[i]);
}
return ans;
}
int main()
{
n = read();
blo = 1000;
for(int i = 1;i <= n;i++)
v[i] = read();
for(int i = 1;i <= n;i++)
{
block[i] = (i - 1)/blo + 1;
st[block[i]].insert(v[i]);
}
for(int i = 1;i <= n;i++)
{
int opt = read(),a = read(),b = read(),c = read();
if(opt == 0)
add(a,b,c);
if(opt == 1)
printf("%d
",query(a,b,c));
}
return 0;
}
分块4
给出一个长为n 的数列，以及n 个操作，操作涉及区间加法，区间求和。
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
inline ll read()
{
int sum = 0,p = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
p = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
(sum *= 10) += ch - '0';
ch = getchar();
}
return sum * p;
}
const int maxn = 50005;
int n,blo;
ll v[maxn];
ll block[maxn],atag[maxn],sum[maxn];
void add(ll a,ll b,ll c)
{
for(int i = a;i <= min(block[a] * blo,b);i++)
{
v[i] += c;
sum[block[a]] += c;
}
if(block[a] != block[b])
for(int i = (block[b] - 1) * blo + 1;i <= b;i++)
{
v[i] += c;
sum[block[b]] += c;
}
for(int i = block[a] + 1;i <= block[b] - 1;i++)
atag[i] += c;
}
void query(ll a,ll b,ll c)
{
ll ans = 0;
for(int i = a;i <= min(block[a] * blo,b);i++)
ans = (ans + v[i] % c + atag[block[a]] % c)%c;
if(block[a] != block[b])
for(int i = (block[b] - 1) * blo + 1;i <= b;i++)
ans = (ans + v[i] % c + atag[block[b]] % c)%c;
for(int i = block[a] + 1;i <= block[b] - 1;i++)
ans = (ans + sum[i] % c + atag[i] * blo % c)%c;
printf("%lld
",ans);
}
int main()
{
n = read();
blo = sqrt(n);
for(int i = 1;i <= n;i++)
v[i] = read();
for(int i = 1;i <= n;i++)
{
block[i] = (i - 1) / blo + 1;
sum[block[i]] += v[i];
}
for(int i = 1;i <= n;i++)
{
ll opt = read(),a = read(),b = read(),c = read();
if(opt == 0)
add(a,b,c);
if(opt == 1)
query(a,b,c+1);
}
return 0;
}
分块5
给出一个长为n 的数列 ，以及n 个操作，操作涉及区间开方，区间求和。
//区间开方，区间求和
#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
inline int read()
{
int sum = 0,p = 1;
char ch = getchar();
while(ch < '0' | ch > '9')
{
if(ch == '-')
p = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
(sum *= 10) += ch - '0';
ch = getchar();
}
return sum * p;
}
const int maxn = 50005;
ll n,blo;
ll block[maxn],v[maxn],sum[maxn];
bool flag[maxn];
void ssqrt(ll x)
{
if(flag[x])
return;
flag[x] = true;
sum[x] = 0;
for(int i = (x - 1) * blo+ 1;i <= x * blo;i++)
{
v[i] = sqrt(v[i]);
sum[x] += v[i];
if(v[i] > 1)
flag[x] = false;
}
}
void add(ll a,ll b,ll c)
{
for(int i = a;i <= min(block[a] * blo,b);i++)
{
sum[block[a]] -= v[i];
v[i] = sqrt(v[i]);
sum[block[a]] += v[i];
}
if(block[a] != block[b])
for(int i = (block[b] - 1)* blo + 1;i <= b;i++)
{
sum[block[b]] -= v[i];
v[i] = sqrt(v[i]);
sum[block[b]] += v[i];
}
for(int i = block[a] + 1;i <= block[b] - 1;i++)
ssqrt(i);
}
void query(ll a,ll b)
{
ll ans = 0;
for(int i = a;i <= min(block[a] * blo,b);i++)
ans += v[i];
if(block[a] != block[b])
for(int i = (block[b] - 1)* blo + 1;i <= b;i++)
ans += v[i];
for(int i = block[a] + 1;i <= block[b] - 1;i++)
ans += sum[i];
printf("%lld
",ans);
}
int main()
{
n = read();
blo = sqrt(n);
for(int i = 1;i <= n;i++)
v[i] = read();
for(int i = 1;i <= n;i++)
{
block[i] = (i - 1) / blo + 1;
sum[block[i]] += v[i];
}
for(int i = 1;i <= n;i++)
{
ll opt = read(),a = read(),b = read(),c = read();
if(opt == 0)
add(a,b,c);
else
query(a,b);
}
return 0;
}
分块6
给出一个长为n的数列，以及n个操作，操作涉及单点插入，单点询问，数据随机生成。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#define ll long long
using namespace std;
inline int read()
{
int sum = 0,p = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
p = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
(sum *= 10) += ch - '0';
ch = getchar();
}
return sum * p;
}
int n,m,blo;
int v[100005];
vector<int>block[1005];
int st[200005],top;
pair<int,int> query(int o)
{
int x = 1;
while(o > block[x].size())
{
o -= block[x].size();
x++;
}
return make_pair(x,o - 1);
}
void rebuild()
{
top = 0;
for(int i = 1;i <= m;i++)
{
for(vector<int>::iterator j = block[i].begin();j != block[i].end();j++)
st[++top] = *j;
block[i].clear();
}
int blo2 = sqrt(top);
for(int i = 1;i <= top;i++)
block[(i - 1) / blo2 + 1].push_back(st[i]);
m = (top - 1)/blo2 + 1;
}
void insert(int a,int b)
{
pair<int,int>t = query(a);
block[t.first].insert(block[t.first].begin() + t.second,b);
if(block[t.first].size() > 20 * blo)
rebuild();
}
int main()
{
n = read(),blo = sqrt(n);
for(int i = 1;i <= n;i++)
v[i] = read();
for(int i = 1;i <= n;i++)
block[(i - 1)/blo + 1].push_back(v[i]);
m = (n - 1)/blo + 1;
for(int i = 1;i <= n;i++)
{
int opt = read(),a = read(),b = read(),c = read();
if(opt == 0)
insert(a,b);
if(opt == 1)
{
pair<int,int>t = query(b);
printf("%d
",block[t.first][t.second]);
}
}
return 0;
}
分块7
给出一个长为n 的数列，以及n个操作，操作涉及区间乘法，区间加法，单点询问。
//区间乘法+区间加法+单点查询
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{
int sum = 0,p = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
p = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
(sum *= 10) += ch - '0';
ch = getchar();
}
return sum * p;
}
int n,blo,mod = 10007;
int v[100005],block[100005],atag[1005],mtag[1005];
void reset(int o)
{
for(int i = (o - 1)* blo + 1;i <= min(n,o * blo);i++)
v[i] = (v[i] * mtag[o] + atag[o])%mod;
atag[o] = 0;
mtag[o] = 1;
}
void solve(int opt,int a,int b,int c)
{
reset(block[a]);
for(int i = a;i <= min(block[a] * blo,b);i++)
{
if(opt == 0)
v[i] += c;
else
v[i] *= c;
v[i] %= mod;
}
if(block[a] != block[b])
{
reset(block[b]);
for(int i = (block[b] - 1) * blo + 1;i <= b;i++)
{
if(opt == 0)
v[i] += c;
else
v[i] *= c;
v[i] %= mod;
}
}
for(int i = block[a] + 1;i <= block[b] - 1;i++)
{
if(opt == 0)
atag[i] = (atag[i] + c)% mod;
else
{
atag[i] = (atag[i] * c)%mod;
mtag[i] = (mtag[i] * c)%mod;
}
}
}
int main()
{
n = read();
blo = sqrt(n);
for(int i = 1;i <= n;i++)
v[i] = read();
for(int i = 1;i <= n;i++)
block[i] = (i - 1)/blo + 1;
for(int i = 1;i <= block[n];i++)
mtag[i] = 1;
for(int i = 1;i <= n;i++)
{
int opt = read(),a = read(),b = read(),c = read();
if(opt == 2)
printf("%d
",(v[b] *mtag[block[b]] +atag[block[b]]) % mod);
else
solve(opt,a,b,c);
}
return 0;
}
分块8
给出一个长为n的数列，以及n个操作，操作涉及区间询问等于一个数c的元素，并将这个区间的所有元素改为c。
//区间询问等于一个数c的元素，并将这个区间的所有元素改为c
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
int sum = 0,p = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
p = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
(sum *= 10) += ch - '0';
ch = getchar();
}
return sum * p;
}
int n,blo;
int v[100005],block[100005],atag[1005];
void reset(int o)
{
if(atag[o] == -1)
return;
for(int i = (o - 1) * blo + 1;i <= o * blo;i++)
v[i] = atag[o];
atag[o] = -1;
}
void query(int l,int r,int c)
{
int ans = 0;
reset(block[l]);
for(int i = l;i <= min(blo * block[l],r);i++)
if(v[i] != c)
v[i] = c;
else
ans++;
if(block[l] != block[r])
{
reset(block[r]);
for(int i = blo * (block[r] - 1) + 1;i <= r;i++)
if(v[i] != c)
v[i] = c;
else
ans++;
}
for(int i = block[l] + 1;i <= block[r] - 1;i++)
{
if(atag[i] != -1)
if(atag[i] != c)
atag[i] = c;
else
ans += blo;
else
{
for(int j = blo * (i - 1) + 1;j <= blo * i;j++)
if(v[j] != c)
v[j] = c;
else
ans++;
atag[i] = c;
}
}
printf("%d
",ans);
}
int main()
{
n = read();
blo = sqrt(n);
memset(atag,-1,sizeof(atag));
for(int i = 1;i <= n;i++)
v[i] = read();
for(int i = 1;i <= n;i++)
block[i] = (i - 1) / blo + 1;
for(int i = 1;i <= n;i++)
{
int l = read(),r = read(),c = read();
query(l,r,c);
}
return 0;
}
分块9
给出一个长为n的数列，以及n个操作，操作涉及询问区间的最小众数。
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#include<cstring>
#define ll long long
using namespace std;
inline int read()
{
int sum = 0,p = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-')
p = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
(sum *= 10) += ch - '0';
ch = getchar();
}
return sum * p;
}
const int maxn = 100005,maxm = 100005;
int n,blo = 100,id;
int v[maxn],block[maxn],val[maxm],cnt[maxn];
int f[1010][1010];
map<int,int>mp;
vector<int>ve[maxn];
void pre(int x)
{
memset(cnt,0,sizeof(cnt));
int mx = 0,ans = 0;
for(int i = (x - 1) * blo + 1;i <= n;i++)
{
int t = block[i];
cnt[v[i]]++;
if(cnt[v[i]] > mx || (cnt[v[i]] == mx && val[v[i]] < val[ans]))
{
mx = cnt[v[i]];
ans = v[i];
}
f[x][t] = ans;
}
}
int ask(int a,int b,int x)
{
return upper_bound(ve[x].begin(),ve[x].end(),b) - lower_bound(ve[x].begin(),ve[x].end(),a);
}
int query(int a,int b)
{
int ans = f[block[a] + 1][block[b] - 1];
int mx = ask(a,b,ans);
for(int i = a;i <= min(blo * block[a],b);i++)
{
int t = ask(a,b,v[i]);
if(t > mx || (t == mx && val[v[i]] < val[ans]))
{
ans = v[i];
mx = t;
}
}
if(block[a] != block[b])
{
for(int i = (block[b] - 1) * blo + 1;i <= b;i++)
{
int t = ask(a,b,v[i]);
if(t > mx || (t == mx && val[v[i]] < val[ans]))
{
ans = v[i];
mx = t;
}
}
}
return ans;
}
int main()
{
n = read();
for(int i = 1;i <= n;i++)
{
v[i] = read();
if(!mp[v[i]])
{
mp[v[i]] = ++id;
val[id] = v[i];
}
v[i] = mp[v[i]];
ve[v[i]].push_back(i);
}
for(int i = 1;i <= n;i++)
block[i] = (i - 1)/blo + 1;
for(int i = 1;i <= block[n];i++)
pre(i);
for(int i = 1;i <= n;i++)
{
int l = read(),r = read();
if(l > r)
swap(l,r);
int t = query(l,r);
printf("%d
",val[t]);
}
return 0;
}