数列分块入门 8
链接：LibreOj6284
题目描述
给出一个长为n的数列，以及n个操作，操作涉及区间询问等于一个数c的元素的个数，并将这个区间的所有元素改为c。
输入格式
第一行输入一个数字n。
第二行输入n个数字，第i个数字为 a[i]，以空格隔开。
接下来输入n行询问，每行输入四个数字l、r、c，以空格隔开。
表示先查询位于[l,r]的数字有多少个是c，再把位于[l,r]的数字都改为c。
输出格式
对于每次询问，输出一行一个数字表示答案。
样例输入
4 1 2 2 4 1 3 1 1 4 4 1 2 2 1 4 2
样例输出
1 1 0 2
分析：
开一个mark数组，用于标记某一块是否是同一个元素。 例如mark[i]=50表示块内所有元素都等于50. 开始我感觉维护mark的时候其实有点麻烦，搞了挺久的一直没有很棒的思路， 最后想的是，分块本来就是暴力，那就暴力一点叭，然后直接瞎写完结束 这题的mark用-1表示不是用一个元素，一般不应该用-1，这题目数据不太行
我的代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<sstream>
#include<memory>
#include<utility>
#include<functional>
#include<iterator>
typedef long long ll
;
const int inf
=0x3f3f3f3f;
const int inn
=0x80808080;
using namespace std
;
const int maxm
=1e5+5;
int l
[maxm
],r
[maxm
];
int belong
[maxm
];
int mark
[maxm
];
int a
[maxm
];
int block
,num
;
int n
;
void build(){
block
=sqrt(n
);
num
=n
/block
;
if(n
%block
)num
++;
for(int i
=1;i
<=num
;i
++){
l
[i
]=(i
-1)*block
+1;
r
[i
]=i
*block
;
mark
[i
]=-1;
}
r
[num
]=n
;
}
void check(int node
,int val
){
for(int i
=l
[node
];i
<=r
[node
];i
++){
if(a
[i
]!=val
){
mark
[node
]=-1;
return ;
}
}
mark
[node
]=val
;
}
void reset(int node
){
int temp
=mark
[node
];
if(temp
==-1)return ;
for(int i
=l
[node
];i
<=r
[node
];i
++){
a
[i
]=temp
;
}
}
int ffind(int x
,int y
,int val
){
int ans
=0;
if(belong
[x
]==belong
[y
]){
reset(belong
[x
]);
for(int i
=x
;i
<=y
;i
++){
if(a
[i
]==val
)ans
++;
a
[i
]=val
;
}
check(belong
[x
],val
);
return ans
;
}
reset(belong
[x
]);
reset(belong
[y
]);
for(int i
=x
;i
<=r
[belong
[x
]];i
++){
if(a
[i
]==val
)ans
++;
a
[i
]=val
;
}
check(belong
[x
],val
);
for(int i
=l
[belong
[y
]];i
<=y
;i
++){
if(a
[i
]==val
)ans
++;
a
[i
]=val
;
}
check(belong
[y
],val
);
for(int i
=belong
[x
]+1;i
<belong
[y
];i
++){
if(mark
[i
]!=-1){
if(mark
[i
]==val
){
ans
+=block
;
}else{
mark
[i
]=val
;
}
}else{
for(int j
=l
[i
];j
<=r
[i
];j
++){
if(a
[j
]==val
)ans
++;
a
[j
]=val
;
}
mark
[i
]=val
;
}
}
return ans
;
}
int main(){
scanf("%d",&n
);
build();
for(int i
=1;i
<=n
;i
++){
belong
[i
]=(i
-1)/block
+1;
scanf("%d",&a
[i
]);
}
for(int i
=1;i
<=n
;i
++){
int x
,y
,c
;
scanf("%d%d%d",&x
,&y
,&c
);
printf("%d\n",ffind(x
,y
,c
));
}
return 0;
}
