突刺贯穿的第二分块()-其他
突刺贯穿的第二分块()
[CF896E] Welcome home, Chtholly
给定一个长为 \(n\) 的序列 \(a_1\sim a_n\)，\(m\) 次操作，分两种：
，将 \(a_l\sim a_r\) 中 \(\gt x\) 的数减去 \(x\)。
，询问此时 \(a_l\sim a_r\) 有多少数等于 \(x\)。
\(1\le n,m,a_i,x\le 10^5\)。
给定一个长为 \(n\) 的序列 \(a_1\sim a_n\)，\(m\) 次操作，分两种：
- 1 l r x，将 \(a_l\sim a_r\) 中 \(\gt x\) 的数减去 \(x\)。
- 2 l r x，询问此时 \(a_l\sim a_r\) 有多少数等于 \(x\)。
\(1\le n,m,a_i,x\le 10^5\)。
lxl 的分块科技，很奇妙。
考虑根据这个特殊的值域搞点什么东西。
分块以后可以直接在每个块内开 \(10^5\) 个桶存这个块里的数。这样询问操作就可以解决了。
考虑修改操作，散块重构，对于整块，两种暴力：
- 给 \(\le x\) 的数加上 \(x\)，然后给整个块打上一个整体减 \(x\) 的 tag。
- 枚举 \(\gt x\) 的桶 \(i\)，将桶 \(i\) 和 \(i-x\) 合并。
单次操作 \(\mathcal O(V)\)，这是坏的。考虑平衡思想，将两者结合。记录整块最大值 \(\rm maxv\)，分类：
- \(\mathrm{maxv}\le 2x\)，采用暴力 2.
- \(\mathrm{maxv}\gt 2x\)，采用暴力 1.
相当于用 \(\mathcal O(Dx)\) 的代价使得 \(\rm maxv\) 减小了 \(x\)。总复杂度 \(\mathcal O(Dn\sqrt n)\)，这是好的。
考虑用一个 \(\mathcal O(1)\) 复杂度的数据结构维护桶的合并。使用并查集，因为每条边至多被遍历一遍，单次复杂度均摊 \(\mathcal O(1)\)。
强化版卡空间，可以离线，对于每个块单独计算对所有询问的贡献。
#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
const int S = 400;
int read() {
int s = 0;
char c = getchar();
for(;c < '0'||c > '9';c = getchar());
for(;c >= '0'&&c <= '9';c = getchar())
s = (s << 1) + (s << 3) + (c ^ '0');
return s;
}
void print(int x) {
if(x > 9)
print(x / 10);
putchar(x % 10 + '0');
return ;
}
int pre[maxn],val[maxn];
int find(int x) {
return x == pre[x] ? x : pre[x] = find(pre[x]);
}
struct node {
int rt,sz;
node() {
rt = sz = 0;
}
} d[S + 5][maxn];
int max(const int& x,const int& y) {
return x > y ? x : y;
}
int min(const int& x,const int& y) {
return x < y ? x : y;
}
int n,m,a[maxn],t,maxv[S],L[S],R[S],pos[maxn],tag[S];
void pushdown(int p) {
for(int i = L[p];i <= R[p];++ i)
a[i] = val[find(i)],d[p][a[i]].rt = d[p][a[i]].sz = 0,a[i] -= tag[p];
tag[p] = 0;
for(int i = L[p];i <= R[p];++ i)
pre[i] = 0;
return ;
}
void Maintain(int p) {
maxv[p] = 0;
for(int i = L[p];i <= R[p];++ i) {
maxv[p] = max(maxv[p] , a[i]);
++ d[p][a[i]].sz;
if(!d[p][a[i]].rt)
d[p][a[i]].rt = pre[i] = i,val[i] = a[i];
else
pre[i] = d[p][a[i]].rt;
}
return ;
}
void Merge(int p,int x,int y) {
if(d[p][y].rt)
pre[d[p][x].rt] = d[p][y].rt;
else
d[p][y].rt = d[p][x].rt,val[d[p][x].rt] = y;
d[p][y].sz += d[p][x].sz;
d[p][x].sz = d[p][x].rt = 0;
return ;
}
void gettag(int p,int x) {
if(maxv[p] - tag[p] < (x << 1)) {
for(int i = maxv[p];i > x + tag[p];-- i)
if(d[p][i].rt)
Merge(p , i , i - x);
maxv[p] = min(maxv[p] , x + tag[p]);
}
else {
for(int i = tag[p] + 1;i <= x + tag[p];++ i)
if(d[p][i].rt)
Merge(p , i , i + x);
tag[p] += x;
}
return ;
}
void modify(int l,int r,int x) {
int p = pos[l],q = pos[r];
if(p == q) {
pushdown(p);
for(int i = l;i <= r;++ i)
if(a[i] > x)
a[i] -= x;
Maintain(p);
}
else {
pushdown(p);
pushdown(q);
for(int i = l;i <= R[p];++ i)
if(a[i] > x)
a[i] -= x;
for(int i = L[q];i <= r;++ i)
if(a[i] > x)
a[i] -= x;
Maintain(p);
Maintain(q);
for(int i = p + 1;i < q;++ i)
gettag(i , x);
}
return ;
}
int query(int l,int r,int x) {
int ans = 0,p = pos[l],q = pos[r];
if(p == q) {
for(int i = l;i <= r;++ i)
if(val[find(i)] - tag[p] == x)
++ ans;
}
else {
for(int i = l;i <= R[p];++ i)
if(val[find(i)] - tag[p] == x)
++ ans;
for(int i = L[q];i <= r;++ i)
if(val[find(i)] - tag[q] == x)
++ ans;
for(int i = p + 1;i < q;++ i)
if(x + tag[i] <= 100000)
ans += d[i][x + tag[i]].sz;
}
return ans;
}
int main() {
n = read();
m = read();
for(int i = 1;i <= n;++ i)
a[i] = read(),pos[i] = (i - 1) / S + 1;
for(int i = 1;i <= n;++ i) {
if(!L[pos[i]])
L[pos[i]] = i;
R[pos[i]] = i;
}
for(int i = 1;i <= pos[n];++ i)
Maintain(i);
while(m --) {
int op = read(),l = read(),r = read(),x = read();
if(op == 1)
modify(l , r , x);
else
print(query(l , r , x)),putchar('\n');
}
return 0;
}
————————
[CF896E] Welcome home, Chtholly
给定一个长为 \(n\) 的序列 \(a_1\sim a_n\)，\(m\) 次操作，分两种：
，将 \(a_l\sim a_r\) 中 \(\gt x\) 的数减去 \(x\)。
，询问此时 \(a_l\sim a_r\) 有多少数等于 \(x\)。
\(1\le n,m,a_i,x\le 10^5\)。
给定一个长为 \(n\) 的序列 \(a_1\sim a_n\)，\(m\) 次操作，分两种：
- 1 l r x，将 \(a_l\sim a_r\) 中 \(\gt x\) 的数减去 \(x\)。
- 2 l r x，询问此时 \(a_l\sim a_r\) 有多少数等于 \(x\)。
\(1\le n,m,a_i,x\le 10^5\)。
lxl 的分块科技，很奇妙。
考虑根据这个特殊的值域搞点什么东西。
分块以后可以直接在每个块内开 \(10^5\) 个桶存这个块里的数。这样询问操作就可以解决了。
考虑修改操作，散块重构，对于整块，两种暴力：
- 给 \(\le x\) 的数加上 \(x\)，然后给整个块打上一个整体减 \(x\) 的 tag。
- 枚举 \(\gt x\) 的桶 \(i\)，将桶 \(i\) 和 \(i-x\) 合并。
单次操作 \(\mathcal O(V)\)，这是坏的。考虑平衡思想，将两者结合。记录整块最大值 \(\rm maxv\)，分类：
- \(\mathrm{maxv}\le 2x\)，采用暴力 2.
- \(\mathrm{maxv}\gt 2x\)，采用暴力 1.
相当于用 \(\mathcal O(Dx)\) 的代价使得 \(\rm maxv\) 减小了 \(x\)。总复杂度 \(\mathcal O(Dn\sqrt n)\)，这是好的。
考虑用一个 \(\mathcal O(1)\) 复杂度的数据结构维护桶的合并。使用并查集，因为每条边至多被遍历一遍，单次复杂度均摊 \(\mathcal O(1)\)。
强化版卡空间，可以离线，对于每个块单独计算对所有询问的贡献。
#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
const int S = 400;
int read() {
int s = 0;
char c = getchar();
for(;c < '0'||c > '9';c = getchar());
for(;c >= '0'&&c <= '9';c = getchar())
s = (s << 1) + (s << 3) + (c ^ '0');
return s;
}
void print(int x) {
if(x > 9)
print(x / 10);
putchar(x % 10 + '0');
return ;
}
int pre[maxn],val[maxn];
int find(int x) {
return x == pre[x] ? x : pre[x] = find(pre[x]);
}
struct node {
int rt,sz;
node() {
rt = sz = 0;
}
} d[S + 5][maxn];
int max(const int& x,const int& y) {
return x > y ? x : y;
}
int min(const int& x,const int& y) {
return x < y ? x : y;
}
int n,m,a[maxn],t,maxv[S],L[S],R[S],pos[maxn],tag[S];
void pushdown(int p) {
for(int i = L[p];i <= R[p];++ i)
a[i] = val[find(i)],d[p][a[i]].rt = d[p][a[i]].sz = 0,a[i] -= tag[p];
tag[p] = 0;
for(int i = L[p];i <= R[p];++ i)
pre[i] = 0;
return ;
}
void Maintain(int p) {
maxv[p] = 0;
for(int i = L[p];i <= R[p];++ i) {
maxv[p] = max(maxv[p] , a[i]);
++ d[p][a[i]].sz;
if(!d[p][a[i]].rt)
d[p][a[i]].rt = pre[i] = i,val[i] = a[i];
else
pre[i] = d[p][a[i]].rt;
}
return ;
}
void Merge(int p,int x,int y) {
if(d[p][y].rt)
pre[d[p][x].rt] = d[p][y].rt;
else
d[p][y].rt = d[p][x].rt,val[d[p][x].rt] = y;
d[p][y].sz += d[p][x].sz;
d[p][x].sz = d[p][x].rt = 0;
return ;
}
void gettag(int p,int x) {
if(maxv[p] - tag[p] < (x << 1)) {
for(int i = maxv[p];i > x + tag[p];-- i)
if(d[p][i].rt)
Merge(p , i , i - x);
maxv[p] = min(maxv[p] , x + tag[p]);
}
else {
for(int i = tag[p] + 1;i <= x + tag[p];++ i)
if(d[p][i].rt)
Merge(p , i , i + x);
tag[p] += x;
}
return ;
}
void modify(int l,int r,int x) {
int p = pos[l],q = pos[r];
if(p == q) {
pushdown(p);
for(int i = l;i <= r;++ i)
if(a[i] > x)
a[i] -= x;
Maintain(p);
}
else {
pushdown(p);
pushdown(q);
for(int i = l;i <= R[p];++ i)
if(a[i] > x)
a[i] -= x;
for(int i = L[q];i <= r;++ i)
if(a[i] > x)
a[i] -= x;
Maintain(p);
Maintain(q);
for(int i = p + 1;i < q;++ i)
gettag(i , x);
}
return ;
}
int query(int l,int r,int x) {
int ans = 0,p = pos[l],q = pos[r];
if(p == q) {
for(int i = l;i <= r;++ i)
if(val[find(i)] - tag[p] == x)
++ ans;
}
else {
for(int i = l;i <= R[p];++ i)
if(val[find(i)] - tag[p] == x)
++ ans;
for(int i = L[q];i <= r;++ i)
if(val[find(i)] - tag[q] == x)
++ ans;
for(int i = p + 1;i < q;++ i)
if(x + tag[i] <= 100000)
ans += d[i][x + tag[i]].sz;
}
return ans;
}
int main() {
n = read();
m = read();
for(int i = 1;i <= n;++ i)
a[i] = read(),pos[i] = (i - 1) / S + 1;
for(int i = 1;i <= n;++ i) {
if(!L[pos[i]])
L[pos[i]] = i;
R[pos[i]] = i;
}
for(int i = 1;i <= pos[n];++ i)
Maintain(i);
while(m --) {
int op = read(),l = read(),r = read(),x = read();
if(op == 1)
modify(l , r , x);
else
print(query(l , r , x)),putchar('\n');
}
return 0;
}