分析第一个操作
朴素的做法，遍历一遍大于x就-=x，极限复杂度O(mn)
分块做法
整块:我们维护一个最大值，从mx到x遍历一遍（减去x)用并查集操作merge(i,i-x),考虑mx=100001,x=1,极限复杂度O(mV)
我们可以分析
1.x>(mx/2),从mx到x遍历一遍,应该是最优的复杂度O(mx-x)
2.x<(mx/2),最优的复杂度应该是O(x),因此思考在这种情况下如何操作使得复杂度为O(x)，从x到0遍历一遍呗，我们可以遍历一遍x到0,merge(i,i+x),打上区间减法标记
3.x==(mx/2)都行
通过势能分析法总复杂度应该是O(sqrt(n)V) （我母鸡）（操作让区间最大值和区间最小值的差值变小,，值域缩小）
考虑每次都是x==(mx/2),且mx==V,O(V/2*sqrt(m))?
散块:暴力操作，再重构，无脑真不错，每次最多重构O(2*sqrt(n)),总共O(m*sqrt(n))
分析第二个操作
整块:直接得到并查集的大小
散块:遍历l到r,查询并查集==x,res++;
分析总时间复杂度O(Vsqrt(n)+msqrt(n)),快O(1e9),卡卡常啦
如果这样操作我们应该需要一个O(V*sqrt(n))数组，开不下这么大的数组;
lxl这个trick很妙啊
因为我们块与块之间没有关系，且时间挺多，可以离线下来，答案还有可加性，所以我们可以计算每个块的贡献这样只要开O(V)的数组即可
因此空间复杂度是O(V)，1e6随便开
接下来，我们用代码实现一下。。。
先分析一下我们定义哪些数据
fa[N]并查集，index[V](存储该值的位置)，val[N](存储该位置的值)，num[V](存储该值的数量),lazy(减法懒标记)，mx(最大值),ans[M](询问的答案）
int a[N];
int fa[N],index[V],num[V],val[N];//fa，该值的位置，大小，该位置的值
int L[B],R[B];//记录每个块的范围[l,r]
int ans[M];
int mx=-INF;
int lazy;//减法懒标记L,R(设为全局变量也行)
并查集2个操作
1.find
inline int find(int x){
if(fa[x]==x){
return x;
}
return fa[x]=find(fa[x]);
}2.merge
合并2个值的位置，2个值的数量，以及合并后要对原数组清空
inline void merge(int x,int y){
if(index[y]){//值存在
fa[index[x]]=index[y];//合并
}else{//不存在
index[y]=index[x];
val[index[x]]=y;//赋值为y
}
num[y]+=num[x];//合并
index[x]=0;//清空
num[x]=0;//清空
}重构
重新维护一遍之前的量
inline void rebuild(int pos){//记录最大值,合并值,处理值的数量
mx=-INF;
lazy=0;
for(int i=L[pos];i<=R[pos];i++){
mx=max(mx,a[i]);
if(!index[a[i]]){
index[a[i]]=i;
fa[i]=i;
val[i]=a[i];
}else{
fa[i]=index[a[i]];
}
num[a[i]]++;
}
}操作一
1.整块
inline void modify(int x){//区间 O(V)
if((x<<1)<=(mx-lazy)){//x*2<=mx,
for(int i=lazy;i<=x+lazy;i++){//a[i]<=x 都加x,lazy+x;O(x);
if(index[i]){
merge(i,i+x);
}
}
lazy+=x;
}else{//2*x>mx
for(int i=mx;i>x+lazy;i--){//a[i]>x 减去x,O(mx-x);
if(index[i]){
merge(i,i-x);
}
}
//最大的值可能有x,与原本的mx取小
mx=min(mx,x+lazy);
}
}min解释一下(我一开始不会)，现在的情况是2*x>mx,可以转化成x>mx-x
分析2种情况
1.mx>x && x(数组中存在x),x
2.mx<x,mx
因此要取min
2.散块
我们要只需要下传懒标记，操作完重构一下即可
inline void update(int l,int r,int x,int pos){
//下传lazy
for(int i=L[pos];i<=R[pos];i++){
int temp=val[find(i)];
a[i]=temp-lazy;
index[temp]=0;
num[temp]=0;
}
for(int i=L[pos];i<=R[pos];i++){
val[i]=0;
}
l=max(l,L[pos]);
r=min(r,R[pos]);
//暴力操作
for(int i=l;i<=r;i++){
if(a[i]>x){
a[i]-=x;
}
}
rebuild(pos);
}操作二
1.整块
直接加num[]
ans[j]+=num[que[j].x+lazy];2.遍历一遍
inline int query(int l,int r,int x,int pos){
int res=0;
l=max(l,L[pos]);
r=min(r,R[pos]);
for(int i=l;i<=r;i++){
if(val[find(i)]-lazy==x){
res++;
}
}
return res;
}感觉询问比较轻松，主要是操作维护这块是难点
完整代码
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#define INF 2147483647
using namespace std;
typedef long long ll;
const int N=1e6+9;
const int B=1e4+9;
const int V=1e5+9;
const int M=5e5+9;
namespace Lan {
inline string sread() {
string s=" ";char e=getchar();
while(e==' '||e=='\n')e=getchar();
while(e!=' '&&e!='\n')s+=e,e=getchar();
return s;
}
inline void swrite(string s){
for(char e:s)putchar(e);
printf("\n");
}
inline ll read() {
ll x=0,y=1;char c=getchar();
while(!isdigit(c)){if(c=='-')y=-1;c=getchar();}
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*=y;
}
inline void write(ll x) {
if(x<0){x=-x,putchar('-');}ll sta[35],top=0;
do sta[top++]=x%10,x/=10;while(x);
while(top)putchar(sta[--top]+'0');
}
inline int max(int a,int b){
if(a>b){
return a;
}
return b;
}
inline int min(int a,int b){
if(a>b){
return b;
}
return a;
}
}using namespace Lan;
int a[N];
int fa[N],index[V],num[V],val[N];//fa，该值的位置，大小，该位置的值
int L[B],R[B];//记录每个块的范围[l,r]
int ans[M];
int mx=-INF;
int lazy;//减法懒标记
struct Q{
int op,l,r,x;
}que[M];
inline int find(int x){
if(fa[x]==x){
return x;
}
return fa[x]=find(fa[x]);
}
inline void merge(int x,int y){
if(index[y]){//值存在
fa[index[x]]=index[y];//合并
}else{//不存在
index[y]=index[x];
val[index[x]]=y;//赋值为y
}
num[y]+=num[x];//合并
index[x]=0;//清空
num[x]=0;//清空
}
inline void rebuild(int pos){//记录最大值,合并值,处理值的数量
mx=-INF;
lazy=0;
for(int i=L[pos];i<=R[pos];i++){
mx=max(mx,a[i]);
if(!index[a[i]]){
index[a[i]]=i;
fa[i]=i;
val[i]=a[i];
}else{
fa[i]=index[a[i]];
}
num[a[i]]++;
}
}
inline void modify(int x){//区间 O(V)
if((x<<1)<=(mx-lazy)){//x*2<=mx,
for(int i=lazy;i<=x+lazy;i++){//a[i]<=x 都加x,lazy+x;O(x);
if(index[i]){
merge(i,i+x);
}
}
lazy+=x;
}else{//2*x>mx
for(int i=mx;i>x+lazy;i--){//a[i]>x 减去x,O(mx-x);
if(index[i]){
merge(i,i-x);
}
}
//最大的值可能有x,与原本的mx取小
mx=min(mx,x+lazy);
}
}
inline int query(int l,int r,int x,int pos){
int res=0;
l=max(l,L[pos]);
r=min(r,R[pos]);
for(int i=l;i<=r;i++){
if(val[find(i)]-lazy==x){
res++;
}
}
return res;
}
inline void update(int l,int r,int x,int pos){
//下传lazy
for(int i=L[pos];i<=R[pos];i++){
int temp=val[find(i)];
a[i]=temp-lazy;
index[temp]=0;
num[temp]=0;
}
for(int i=L[pos];i<=R[pos];i++){
val[i]=0;
}
l=max(l,L[pos]);
r=min(r,R[pos]);
//暴力操作
for(int i=l;i<=r;i++){
if(a[i]>x){
a[i]-=x;
}
}
rebuild(pos);
}
inline void init(){
mx=-INF;
lazy=0;
memset(num,0,sizeof(num));
memset(index,0,sizeof(index));
}
inline bool inrange(int L,int R,int l,int r){//[l[L,R]r]
return L>=l && R<=r;
}
inline bool outofrange(int L,int R,int l,int r){
return L>r || l>R;
}
int main(){
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int n,m;
n=read();
m=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=m;i++){
que[i].op=read();
que[i].l=read();
que[i].r=read();
que[i].x=read();
}
int blo=sqrt(n);
int t=ceil(n*1.0/blo);
for(int i=1;i<=t;i++){
L[i]=(i-1)*t+1;
R[i]=i*t;
}
//逐块处理
for(int i=1;i<=t;i++){
init();
rebuild(i);
for(int j=1;j<=m;j++){
if(que[j].l>que[j].r){
continue;
}
if(outofrange(L[i],R[i],que[j].l,que[j].r)){//不在这个区间
continue;
}
if(que[j].op==1){
if(inrange(L[i],R[i],que[j].l,que[j].r)){//询问区间包含这个块
modify(que[j].x);//整块处理
}else{
update(que[j].l,que[j].r,que[j].x,i);//这一块处理完重构
}
}else{
if(que[j].x+lazy>1e5+1){//没有贡献
continue;
}
if(inrange(L[i],R[i],que[j].l,que[j].r)){//询问区间包含这一块
ans[j]+=num[que[j].x+lazy];
}else{
ans[j]+=query(que[j].l,que[j].r,que[j].x,i);//只能处理这一块的
}
}
}
}
for(int i=1;i<=m;i++){
if(que[i].op==2){
write(ans[i]);
putchar('\n');
}
}
return 0;
}
不愧是大分块，lxl orz，还是刷刷简单点的分块题再来挑战ynoi吧
无期稿件P4119 [Ynoi2018] 未来日记
