[DS记录]P4117 [Ynoi2018]五彩斑斓的世界
command_block
·
·
个人记录
题意 : 第二分块。
-
把区间 [l,r] 中大于 x 的数减去 x。
-
询问 [l,r] 中 x 的出现次数。
------------
看起来我们需要一个 $O(n\sqrt{n})$ 时间, $O(n)$ 空间的做法。
观察到值域很小,又涉及**减**和出现次数,做法肯定和值域有关。
先把原序列分块,散块可以暴力,考虑整块如何修改。
批量做估计不行。本题的操作十分特殊,可能可以均摊,我们要想办法构造一个比较紧的解法。
容易发现每个块的最大值不会增大,我们维护块中最大值 $mx$。
- 若 $mx\leq x$ ,则可以忽略。
- 若 $mx\leq 2x$ ,被减的数较少,可以暴力修改 $(x,mx]$ 中的数(减)。
- 若 $mx>2x$ ,被减的数较多,注意到大于 $x$ 的数减去 $x$ $\Longleftrightarrow$ 小于等于 $x$ 的数加 $x$ ,然后全局减 $x$.
可以暴力修改 $[0,x]$ 中的数(加),然后平移值域(指针移动便可)。
我们使用了一点类似启发式合并的思想,每次尽量暴力修改较少的值域范围。
这样的复杂度是啥呢?
不难发现,在 $mx\leq 2x$ 时, $(x,mx]$ 中的数被减一次之后必定小于 $x$ ,于是 $mx$ 至多为 $x$。也就是说我们花费 $O(mx-x)$ 的时间将 $mx$ 减少了 $mx-x$ 。
在 $mx>2x$ 时,最大值至少减少 $x$。我们花费 $O(x)$ 的时间将 $mx$ 减少了 $x$ 。
总而言之,我们花费的时间和 $mx$ 的减少量成正比,而各块的初始 $mx$ 和为 $O(n\sqrt{n})$。
上面我们的描述都默认可以任意在值域中取址,如果要做到这一点,必须对每个块都维护一个完整的值域表,空间上无法承受。
然后我们惊觉居然没有强制在线,而且每个块的贡献是独立的,我们对每个块单独计算贡献就能避免同时处理 $O(\sqrt{n})$ 个值域表了。
还有个问题是,我们有 $O(n)$ 次散块重构,直接遍历值域表显然是不可行的。
可以使用链表来维护,对每个值维护一个链表维护位置。每次查询的是一个区间的链表头,然后快速地将这些链表连接到指定的链表中。
重构时,可以记录操作中可能出现什么数然后暴力遍历。
为了应付查询,还要维护每个链表的大小。
写起来挺顺的,细节适中,就是要注意数组开多一个块。除掉快读仅有`2.3K`,良心大分块。
```cpp
#include<algorithm>
#include<cctype>
#include<cstdio>
#define MaxN 505000
using namespace std;
namespace IO{
char buf[16050000],*s=buf,*t=buf;
int read(){
int x=0;while(!isdigit(*s))++s;
while(isdigit(*s))x=x*10+(*s++^'0');
return x;
}
void print(int x,char c='\n'){
int st[23],top=0;do{st[++top]=x%10,x/=10;}while(x);
while(top){*t++=st[top--]^'0';}*t++=c;
}
void input()
{buf[fread(buf,1,16000000,stdin)]='\n';}
void output()
{fwrite(buf,1,t-buf,stdout);}
};
using IO::read;
using IO::print;
int BS;
struct Data
{int p,nxt;}l[MaxN];
int tl,fir[MaxN],stk[MaxN],tot;
struct List{
int c,f,t;
inline void clr(){c=f=t=0;}
inline void add(int p)
{l[++tl]=(Data){p,f};f=tl;c++;}
}g[MaxN];
void clr()
{for (int i=1;i<=tot;i++)g[stk[i]].clr();tot=tl=0;}
int tp;
void pia(int *a)
{
for (int t=1;t<=tot;t++){
int x=stk[t];
for (int i=g[x].f;i;i=l[i].nxt)
a[l[i].p]=x-tp;
g[x].clr();
}tot=tl=0;
}
int mx;
void Init(int *a){
tp=mx=0;
for (int i=0,x;i<BS;i++){
if (!g[x=a[i]].f){
stk[++tot]=x;
g[x].t=tl+1;
}g[x].add(i);
mx=max(mx,x);
}
}
inline void merge(int x,int y)
{
if (!g[y].f)return ;
if (!g[x].f){
g[stk[++tot]=x]=g[y];
g[y].clr();
}else {
l[g[x].t].nxt=g[y].f;
g[x].c+=g[y].c;
g[x].t=g[y].t;
g[y].clr();
}
}
void chg(int d)
{
if (mx<=d)return ;
if (mx<=d+d){
for (int i=tp+d+1;i<=tp+mx;i++)
merge(i-d,i);
mx=d;
}else {
for (int i=tp+1;i<=tp+d;i++)
merge(i+d,i);
mx-=d;tp+=d;
}
}
int qry(int x,int tl,int tr)
{
x+=tp;
if (x>500000)return 0;
if (tl==0&&tr==BS-1)return g[x].c;
int cnt=0;
for (int i=g[x].f;i;i=l[i].nxt)
cnt+=(tl<=l[i].p&&l[i].p<=tr);
return cnt;
}
int n,m,s[MaxN],ans[MaxN];
struct Order
{int l,r,x;bool op;}b[MaxN];
int main()
{
freopen("a.txt","r",stdin);
IO::input();
n=read();m=read();
for (BS=10;BS*BS<=n;BS++);BS=min(BS,n);
for (int i=0;i<n;i++)s[i]=read();
for (int i=1;i<=m;i++){
b[i].op=(read()==1);
b[i].l=read()-1;b[i].r=read()-1;
b[i].x=read();
}
for (int t=1;t*BS-BS<n;t++){
int br=t*BS,bl=br-BS,*a=&s[bl];
Init(a);
for (int i=1;i<=m;i++){
int l=max(b[i].l-bl,0),r=min(b[i].r-bl,BS-1);
if (l>r)continue;
if (b[i].op==1){
if (l==0&&r==BS-1)chg(b[i].x);
else {
pia(a);
for (int j=l;j<=r;j++)
if (a[j]>b[i].x)a[j]-=b[i].x;
Init(a);
}
}else ans[i]+=qry(b[i].x,l,r);
}clr();
}
for (int i=1;i<=m;i++)
if (b[i].op==0)
print(ans[i]);
IO::output();
return 0;
}
```