莫队模板以及常见的例题。 Fast Queries F - XOR and Favorite Number 小Z的袜子
程序员文章站
2022-03-25 20:25:49
...
复杂度n^(1.5)
四个while循环中注意边界处的讨论。
精髓在add和del函数还有其排序的方式。
1.莫队求解l到r中不同数的个数。
1） Fast Queries 题目链接：https://vjudge.net/problem/LightOJ-1188
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize(2)
const int maxx=1e6+19;
int pos[maxx];// 那一块
int a[maxx];// 原数组
struct node // 询问
{
int l,r,id;
}Q[maxx];
bool cmp(node a,node b)
{
if(pos[a.l]==pos[b.l]) return a.r<b.r;//先按l所在的块排，如果相等就按r排
else return pos[a.l]<pos[b.l];
}
int ans[maxx];// 最终答案
ll size,Ans=0; // 每次转换得到的值.
int flag[maxx*2]; // 标记数字出现的次数
// 莫队算法由L-R 转换为 (l-1,R) (l+1,R) (L,R-1) (L,R+1)
void add(int x)
{
flag[a[x]]++;
if(flag[a[x]]==1) Ans++;
}
void del(int x)
{
flag[a[x]]--;
if(flag[a[x]]==0) Ans--;
}
int main()
{
int n,m,t;
int L,R;
scanf("%d",&t);
int p=0;
while(t--)
{
L=1,R=0;
Ans=0;
memset(flag,0,sizeof(flag));
scanf("%d%d",&n,&m);
size=sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
pos[i]=i/size;//别写错地方了！》。。。。
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&Q[i].l,&Q[i].r);
Q[i].id=i;
}
sort(Q+1,Q+1+m,cmp);
for(ll i=1;i<=m;i++)
{
while(R<Q[i].r)
{
R++;
add(R);
}
while(L>Q[i].l) ///前缀和L+1>Q[i].l
{
L--;
add(L);
}
while(L<Q[i].l)///前缀和L+1<Q[i].l
{
del(L);
L++;
}
while(R>Q[i].r)
{
del(R);
R--;
}
ans[Q[i].id]=Ans;
}
printf("Case %d:\n",++p);
for(int i=1;i<=m;i++)
{
printf("%d\n",ans[i]);
}
}
return 0;
}
2.莫队求解l到r中有多少个异或和等于k
1） F - XOR and Favorite Number 题目链 https://vjudge.net/contest/326214#problem/F
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// ai^ai+1...^aj=sumi-1^sumj sum为异或前缀和.
// 莫队算法由L-R 转换为 (l-1,R) (l+1,R) (L,R-1) (L,R+1)
typedef long long ll;
#pragma GCC optimize(2)
const int maxx=1e6+19;
int pos[maxx];// 那一块
ll a[maxx];// 原数组
struct node // 询问
{
int l,r,id;
}Q[maxx];
bool cmp(node a,node b)
{
if(pos[a.l]==pos[b.l]) return a.r<b.r;//先按l所在的块排，如果相等就按r排
else return pos[a.l]<pos[b.l];
}
ll ans[maxx];// 最终答案
ll size,Ans=0; // 每次转换得到的值.
int flag[maxx*2]; // 标记数字出现的次数
int n,m,t,k;
void add(int x)
{
Ans+=flag[a[x]^k];// 假设这一段新增加的数量为x 次数为a也就是flag[ax]的个数 则a^x=k 两边同时异或a 得x=k^a
flag[a[x]]++;
}
void del(int x)
{
flag[a[x]]--;
Ans-=flag[a[x]^k];
}
int main()
{
int L,R;
while(~scanf("%d%d%d",&n,&m,&k))
{
L=1,R=0;
Ans=0;
memset(flag,0,sizeof(flag));
size=sqrt(n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]^=a[i-1];
pos[i]=i/size;//别写错地方了！》。。。。
}
flag[0]=1;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&Q[i].l,&Q[i].r);
Q[i].id=i;
}
sort(Q+1,Q+1+m,cmp);
for(int i=1;i<=m;i++)
{
while(L<Q[i].l)// ai^ai+1...^aj=sumi-1^sumj 答案=l-1到r的值
{
del(L-1);
L++;
}
while(L>Q[i].l)
{
L--;
add(L-1);
}
while(R<Q[i].r)
{
R++;
add(R);
}
while(R>Q[i].r)
{
del(R);
R--;
}
ans[Q[i].id]=Ans;
}
for(int i=1;i<=m;i++)
{
printf("%lld\n",ans[i]);
}
}
return 0;
}3.小Z的袜子
就是组合数求概率然后用莫队处理一下下。
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
const int maxx=5e4+19;
#define ll long long
ll a[maxx];
struct node
{
ll l,r,id;
}Q[maxx];
ll pos[maxx];
ll size=0,Ans=0;
ll ans1[maxx],ans2[maxx];
ll flag[maxx];
ll L=1,R=0;
void add(ll x)
{
flag[a[x]]++;
if(flag[a[x]]>=2)
{
ll p=flag[a[x]];
Ans+=((p*(p-1))/2);// 比如由c32变成了 c42 Ans变化就是加上c42减去c32；
Ans-=(((p-1)*(p-2))/2);
}
}
void del(ll x)
{
// 和加思路一样的。
if(flag[a[x]]>=2) // 如果对答案有贡献
{
ll p=flag[a[x]];
Ans-=((p*(p-1))/2);
Ans+=(((p-1)*(p-2))/2);
}
flag[a[x]]--;
}
bool cmp(node a,node b)
{
if(pos[a.l]==pos[b.l]) return a.r<b.r;
return pos[a.l]<pos[b.l];
}
ll gcd(ll a,ll b)
{
if(b==0) return a;
return gcd(b,a%b);
}
int main()
{
ll n,m,k,i,j,t;
scanf("%lld%lld",&n,&m);
size=sqrt(n*1.0);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
pos[i]=(int)i/size;
}
for(i=1;i<=m;i++)
{
scanf("%lld%lld",&Q[i].l,&Q[i].r);
Q[i].id=i;
}
sort(Q+1,Q+1+m,cmp);
for(i=1;i<=m;i++)
{
while(L<Q[i].l)
{
del(L);
L++;
}
while(L>Q[i].l)
{
L--;
add(L);
}
while(R<Q[i].r)
{
R++;
add(R);
}
while(R>Q[i].r)
{
del(R);
R--;
}
ans1[Q[i].id]=Ans;
ans2[Q[i].id]=(R-L)*(R-L+1)/2; // 分母.
}
for(i=1;i<=m;i++)
{
ll x=gcd(ans1[i],ans2[i]);
if(ans1[i]==0)
{
printf("0/1\n");
}
else
printf("%lld/%lld\n",ans1[i]/x,ans2[i]/x);
}
return 0;
}