Preface
最后一题我一直觉得用莫队是最好的。
数列分块入门 7——区间乘法，区间加法，单点询问
还是很简单的吧，比起数列分块入门 7就多了个区间乘。
类似于线段树，由于乘法的优先级高于加法，因此我们先乘后加。
具体的，我们对于每一个块再额外维护一个乘法标记，每次乘法时同时更新乘法/加法标记。
CODE
#include<cstdio>
#include<cctype>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=100005,BLO=320,mod=10007;
int n,a[N],blk[N],opt,x,y,z,add[BLO],mul[BLO],sum[BLO],size;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch; int flag=1; while (!isdigit(ch=tc())) flag=ch^'-'?1:-1;
while (x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc())); x*=flag;
}
inline void write(int x)
{
if (x<0) putchar('-'),x=-x;
if (x>9) write(x/10); putchar(x%10+'0');
}
inline void inc(int &x,int y)
{
if ((x+=y)>=mod) x-=mod;
}
inline int query(int x)
{
return (1LL*a[x]*mul[blk[x]]+add[blk[x]])%mod;
}
inline void reset(int id)
{
for (register int i=(id-1)*size+1;i<=min(id*size,n);++i)
a[i]=a[i]*mul[id]%mod,inc(a[i],add[id]);
mul[id]=1; add[id]=0;
}
inline void modify_add(int l,int r,int x)
{
register int i;
for (reset(blk[l]),i=l;i<=min(blk[l]*size,r);++i) inc(a[i],x);
if (blk[l]!=blk[r]) for (reset(blk[r]),i=(blk[r]-1)*size+1;i<=r;++i) inc(a[i],x);
for (i=blk[l]+1;i<=blk[r]-1;++i) inc(add[i],x);
}
inline void modify_mul(int l,int r,int x)
{
register int i;
for (reset(blk[l]),i=l;i<=min(blk[l]*size,r);++i) a[i]=a[i]*x%mod;
if (blk[l]!=blk[r]) for (reset(blk[r]),i=(blk[r]-1)*size+1;i<=r;++i) a[i]=a[i]*x%mod;
for (i=blk[l]+1;i<=blk[r]-1;++i) mul[i]=(mul[i]+add[i])*x%mod,add[i]=x;
}
int main()
{
//freopen("7.in","r",stdin); freopen("7.out","w",stdout);
register int i; read(n); size=sqrt(n);
for (fill(mul+1,mul+(n-1)/size+2,1),i=1;i<=n;++i)
read(a[i]),inc(sum[blk[i]=(i-1)/size+1],a[i]);
for (i=1;i<=n;++i)
{
read(opt); read(x); read(y); read(z);
switch (opt)
{
case 0:modify_add(x,y,z);break;
case 1:modify_mul(x,y,z);break;
case 2:write(query(y)),putchar('
');break;
}
}
return 0;
}
数列分块入门 8——区间询问等于一个数 c 的元素，并将这个区间的所有元素改为 c
这个东西看一眼感觉就是除分块不可的东西了。
我们还是维护一个整块的标记，当这一块内所有数的值都相同时我们直接得到值并且修改。
但是有一个很严重的问题，如果值不同怎么办？
没事，我们直接遍历整个块即可，但是这样不会T掉吗？
我们要分析一波性质，我们发现询问和修改是同时的，那么说明在一次暴力统计块后这个块内的元素就有序了。
即便是后面的询问打乱了顺序也每次只需要(O(sqrt n))的复杂度遍历即可
论分块的玄学复杂度食用
CODE
#include<cstdio>
#include<cctype>
#include<cmath>
using namespace std;
const int N=100005,BLO=320;
int n,a[N],blk[N],mark[BLO],size,x,y,z;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));
}
inline void write(int x)
{
if (x>9) write(x/10);
putchar(x%10+'0');
}
inline int min(int a,int b)
{
return a<b?a:b;
}
inline void reset(int id)
{
if (!mark[id]) return;
for (register int i=(id-1)*size+1;i<=id*size;++i)
a[i]=mark[id]; mark[id]=0;
}
inline int count(int id,int x)
{
register int i,res=0;
for (i=(id-1)*size+1;i<=id*size;++i)
(a[i]==x&&++res),a[i]=x; mark[id]=x; return res;
}
inline int solve(int l,int r,int x)
{
register int i,res=0;
for (reset(blk[l]),i=l;i<=min(blk[l]*size,r);++i) (a[i]==x&&++res),a[i]=x;
if (blk[l]!=blk[r]) for (reset(blk[r]),i=(blk[r]-1)*size+1;i<=r;++i) (a[i]==x&&++res),a[i]=x;
for (i=blk[l]+1;i<=blk[r]-1;++i)
if (mark[i]) mark[i]==x&&(res+=size),mark[i]=x; else res+=count(i,x); return res;
}
int main()
{
//freopen("8.in","r",stdin); freopen("8.out","w",stdout);
register int i; read(n); size=sqrt(n);
for (i=1;i<=n;++i)
read(a[i]),blk[i]=(i-1)/size+1;
for (i=1;i<=n;++i)
read(x),read(y),read(z),write(solve(x,y,z)),putchar('
');
return 0;
}
数列分块入门 9——询问区间的最小众数
这个看的题目的第一眼就感觉是莫队板子题
不过莫队的本质好像就是分块吧，只不过是将询问处理
那么我们考虑一波对序列分块的想法看看能不能搞。
首先离散化肯定少不了的（这里懒了直接写了map）
然后我们进行一波预处理，搞出每个块到所有它之后的点的最小众数即可出线个数
同时对于每一个离散过的数开一个vector记录出现位置，之后开始搞
对于每一次询问，我们对于所有整块的操作可以直接利用预处理的东西求出答案
然后就是对于两端不完整的块中元素的出现个数了。我们枚举每一个数，然后利用前面的vector，直接上二分找出现个数即可（我又懒了所有直接用了lower/upper_bound）
所以我就说莫队好写吧！
CODE
#include<cstdio>
#include<cctype>
#include<cmath>
#include<map>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100005,BLO=320;
int n,a[N],blk[N],f[BLO][BLO],r[N],cnt[N],num[BLO][BLO],size,x,y,tot;
map <int,int> h;
vector <int> v[N];
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));
}
inline void write(int x)
{
if (x>9) write(x/10);
putchar(x%10+'0');
}
inline void init(int s)
{
memset(cnt,0,sizeof(cnt)); int ans=0,mx=0;
for (register int i=(s-1)*size+1;i<=n;++i)
{
if (++cnt[a[i]]>mx||(cnt[a[i]]==mx&&r[a[i]]<r[ans])) mx=cnt[a[i]],ans=a[i];
f[s][blk[i]]=ans;
}
}
inline int find(int l,int r,int id)
{
return upper_bound(v[id].begin(),v[id].end(),r)-lower_bound(v[id].begin(),v[id].end(),l);
}
inline int query(int L,int R)
{
register int i; int ans=f[blk[L]+1][blk[R]-1],mx=find(L,R,ans);
for (i=L;i<=min(blk[L]*size,R);++i)
{
int t=find(L,R,a[i]);
if (t>mx||(t==mx&&r[a[i]]<r[ans])) mx=t,ans=a[i];
}
if (blk[L]!=blk[R]) for (i=(blk[R]-1)*size+1;i<=R;++i)
{
int t=find(L,R,a[i]);
if (t>mx||(t==mx&&r[a[i]]<r[ans])) mx=t,ans=a[i];
}
return r[ans];
}
int main()
{
//freopen("9.in","r",stdin); freopen("9.out","w",stdout);
register int i; read(n); size=sqrt(n);
for (i=1;i<=n;++i)
{
read(a[i]); blk[i]=(i-1)/size+1;
if (!h[a[i]]) h[a[i]]=++tot; r[h[a[i]]]=a[i]; a[i]=h[a[i]];
v[a[i]].push_back(i);
}
for (i=1;i<=blk[n];++i) init(i);
for (i=1;i<=n;++i)
read(x),read(y),write(query(x,y)),putchar('
');
return 0;
}