根号算法
莫队
普通莫队
P1972 [SDOI2009] HH的项链
正解是可持久化线段树，但是莫队能拿部分分。 :::info[代码]
#include<bits/stdc++.h>
using namespace std;
struct que{
int l,r,lblock,num;
friend bool operator<(que x,que y){
if(x.lblock==y.lblock){
if(x.r==y.r)return x.l<y.l;
return x.r<y.r;
}
return x.lblock<y.lblock;
}
}q[1000005];
int n,m,a[1000005],bk[1000005],cnt,aa[1000005];
void ins(int x){
if(!bk[a[x]])cnt++;
bk[a[x]]++;
}
void del(int x){
if(bk[a[x]]==1)cnt--;
bk[a[x]]--;
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
cin>>m;
int blen=sqrt(n);
for(int i=1;i<=m;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].lblock=(q[i].l+blen-1)/blen;
q[i].num=i;
}
sort(q+1,q+1+m);
int nl=1,nr=1;
ins(1);
for(int i=1;i<=m;i++){
while(nl<q[i].l){
del(nl++);
}
while(nr>q[i].r){
del(nr--);
}
while(nl>q[i].l){
ins(--nl);
}
while(nr<q[i].r){
ins(++nr);
}
aa[q[i].num]=cnt;
}
for(int i=1;i<=m;i++)
printf("%d\n",aa[i]);
return 0;
}
:::
P1494 [国家集训队] 小 Z 的袜子
纯莫队板子题。 :::info[代码]
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct que{
int l,r,lblock,num;
friend bool operator<(que x,que y){
if(x.lblock==y.lblock){
if(x.r==y.r)return x.l<y.l;
return x.r<y.r;
}
return x.lblock<y.lblock;
}
}q[1000005];
int n,m,a[1000005],bk[1000005],cnt,aa[1000005],bb[1000005];
void ins(int x){
cnt-=bk[a[x]]*(bk[a[x]]-1);
bk[a[x]]++;
cnt+=bk[a[x]]*(bk[a[x]]-1);
}
void del(int x){
cnt-=bk[a[x]]*(bk[a[x]]-1);
bk[a[x]]--;
cnt+=bk[a[x]]*(bk[a[x]]-1);
}
int gcd(int x,int y){
if(y==0)return x;
return gcd(y,x%y);
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>n;
cin>>m;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int blen=sqrt(n);
for(int i=1;i<=m;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].lblock=(q[i].l+blen-1)/blen;
q[i].num=i;
}
sort(q+1,q+1+m);
int nl=1,nr=1;
ins(1);
for(int i=1;i<=m;i++){
while(nl<q[i].l){
del(nl++);
}
while(nr>q[i].r){
del(nr--);
}
while(nl>q[i].l){
ins(--nl);
}
while(nr<q[i].r){
ins(++nr);
}
aa[q[i].num]=cnt;
int cc=q[i].r-q[i].l+1;
bb[q[i].num]=cc*(cc-1);
}
for(int i=1;i<=m;i++){
if(aa[i]==0)puts("0/1");
else{
int gcdd=gcd(aa[i],bb[i]);
printf("%lld/%lld\n",aa[i]/gcdd,bb[i]/gcdd);
}
}
return 0;
}
:::
带修莫队
P1903 [国家集训队] 数颜色 / 维护队列
:::info[代码]
#include<bits/stdc++.h>
using namespace std;
struct que{
int l,r,t,lblock,rblock,num;
friend bool operator<(que x,que y){
if(x.lblock==y.lblock){
if(x.rblock==y.rblock)return x.t<y.t;
return x.rblock<y.rblock;
}
return x.lblock<y.lblock;
}
}q[1000005];
int qcnt,rcnt;
struct remove{
int x,c,backc;
}re[1000005];
int a[1000005],bk[1000005],ti,b[1000005],aa[1000005];
int nl=1,nr=1,cnt;
void ins(int x){
if(!bk[a[x]])cnt++;
bk[a[x]]++;
}
void del(int x){
bk[a[x]]--;
if(!bk[a[x]])cnt--;
}
void tplus(){
ti++;
int u=re[ti].x;
if(u>=nl&&u<=nr)
del(u);
a[u]=re[ti].c;
if(u>=nl&&u<=nr)
ins(u);
}
void tminus(){
int u=re[ti].x;
if(u>=nl&&u<=nr)
del(u);
a[u]=re[ti].backc;
if(u>=nl&&u<=nr)
ins(u);
ti--;
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
int blen=pow(n,2.0/3);
for(int i=1;i<=m;i++){
char op;
int l,r;
cin>>op>>l>>r;
if(op=='Q'){
q[++qcnt].l=l;
q[qcnt].r=r;
q[qcnt].lblock=(l+blen-1)/blen;
q[qcnt].rblock=(r+blen-1)/blen;
q[qcnt].t=rcnt;
q[qcnt].num=qcnt;
}
else{
re[++rcnt]={l,r,b[l]};
b[l]=r;
}
}
sort(q+1,q+1+qcnt);
ins(1);
for(int i=1;i<=qcnt;i++){
while(nl<q[i].l){
del(nl++);
}
while(nr>q[i].r){
del(nr--);
}
while(nl>q[i].l){
ins(--nl);
}
while(nr<q[i].r){
ins(++nr);
}
while(ti<q[i].t){
tplus();
}
while(ti>q[i].t){
tminus();
}
aa[q[i].num]=cnt;
}
for(int i=1;i<=qcnt;i++)
printf("%d\n",aa[i]);
return 0;
}:::
毒瘤大分块
P4168 [Violet] 蒲公英
求区间众数，相当于维护区间中可能成为众数的所有数与每个数在区间内出现的次数。
考虑分块，零散块暴力查询可能成为众数的所有数与每个数在区间内出现的次数，整块预处理（由于是静态问题 :::info[代码]
#include<bits/stdc++.h>
using namespace std;
int n,Q,blen,bnum=1,a[40005],cnt;
int Ma[205][205],bk[40005],vis[205][40005],rep[40005],bplace[40005];
map<int,int> mp;
struct blck{
int lp,rp,sz;
}b[205];
int posMa[4100],Manum,Maans[4100];
int que(int l,int r){
Manum=0;
memset(Maans,0,sizeof(Maans));
if(Ma[bplace[l]+1][bplace[r]-1]){
posMa[++Manum]=Ma[bplace[l]+1][bplace[r]-1];
bk[posMa[Manum]]=1;
}
for(int i=l;i<=b[bplace[l]].rp&&i<=r;i++){
if(!bk[a[i]]){
posMa[++Manum]=a[i];
bk[a[i]]=Manum;
}
}
for(int i=max(b[bplace[r]].lp,l);i<=r;i++){
if(!bk[a[i]]){
posMa[++Manum]=a[i];
bk[a[i]]=Manum;
}
}
for(int i=1;i<=Manum;i++){
Maans[i]=vis[bplace[r]-1][posMa[i]]-vis[bplace[l]][posMa[i]];
Maans[i]=max(Maans[i],0);
}
if(bplace[l]==bplace[r]){
for(int i=l;i<=r;i++){
Maans[bk[a[i]]]++;
}
}
else{
for(int i=l;i<=b[bplace[l]].rp;i++){
Maans[bk[a[i]]]++;
}
for(int i=b[bplace[r]].lp;i<=r;i++){
Maans[bk[a[i]]]++;
}
}
for(int i=1;i<=Manum;i++){
bk[posMa[i]]=0;
}
int maxx=1;
for(int i=2;i<=Manum;i++){
if(Maans[i]>Maans[maxx]||(Maans[i]==Maans[maxx]&&rep[posMa[i]]<rep[posMa[maxx]]))maxx=i;
}
return posMa[maxx];
}
int main(){
cin>>n>>Q;
blen=sqrt(n);
b[bnum]={1,blen,blen};
for(int i=1,l=1,r=blen;i<=n;i++){
if(r<i){
l+=blen,r+=blen,bnum++;
r=min(r,n);
b[bnum]={l,r,r-l+1};
}
bplace[i]=bnum;
int x;
scanf("%d",&x);
if(!mp[x])mp[x]=++cnt;
a[i]=mp[x];
rep[a[i]]=x;
}
for(int i=1;i<=bnum;i++){
memset(bk,0,sizeof(bk));
int k=b[i].lp,mj;
bk[a[k]]++;
mj=k;
k++;
for(int j=i;j<=bnum;j++){
while(k<=b[j].rp){
bk[a[k]]++;
if(bk[a[mj]]<bk[a[k]]) mj=k;
else if(bk[a[mj]]==bk[a[k]]&&rep[a[mj]]>rep[a[k]])mj=k;
k++;
}
Ma[i][j]=a[mj];
}
}
for(int i=1;i<=bnum;i++){
for(int j=1;j<=cnt;j++)
vis[i][j]=vis[i-1][j];
for(int j=b[i].lp;j<=b[i].rp;j++){
vis[i][a[j]]++;
}
}
memset(bk,0,sizeof(bk));
int lastans=0;
while(Q--){
int l,r;
cin>>l>>r;
l=(l+lastans-1)%n+1;
r=(r+lastans-1)%n+1;
if(l>r)swap(l,r);
lastans=que(l,r);
lastans=rep[lastans];
printf("%d\n",lastans);
}
return 0;
}:::
CF896E Welcome home, Chtholly
虽然 NOI 不考 (NOI2020时代的眼泪：你说什么
第二分块板子题。我们注意到该题的值域很小，所以对于每一个块，建一个并查集，恰好等于
我们发现，每次修改之后