头部背景图片
Decaku 's Blog |
Decaku 's Blog |

莫队题集(不定时更新)

$普通莫队,主要用于解决一类无修改可离线的区间问题。$


描述:

$ 洛谷2709 $
传送门


思路:

$ 和国家集训队小Z的袜子这题一样,用莫队维护区间元素 \\
出现次数即可。$


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=5e4+5;
int n,m,k,a[maxn],block,c[maxn];
ll ans[maxn],tem;
struct Query
{
int l,r,id;
} q[maxn];

bool cmp(Query x,Query y)
{
if(x.l/block==y.l/block)
return x.r<y.r;
return x.l/block<y.l/block;
}

void add(int x)
{
tem+=1LL*c[a[x]]*2+1;
c[a[x]]++;
}


void rem(int x)
{
tem-=1LL*c[a[x]]*2-1;
c[a[x]]--;
}
int main()
{
scanf("%d %d %d",&n,&m,&k);
block=sqrt(n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
for(int i=1; i<=m; i++)
{
scanf("%d %d",&q[i].l,&q[i].r);
q[i].id=i;
}

sort(q+1,q+m+1,cmp);
int l=1,r=0;
tem=0;
for(int i=1; i<=m; i++)
{
while(q[i].l<l)
add(--l);
while(q[i].l>l)
rem(l++);
while(q[i].r<r)
rem(r--);
while(q[i].r>r)
add(++r);
ans[q[i].id]=tem;
}
for(int i=1; i<=m; i++)
printf("%lld\n",ans[i]);
}

描述:

$ bzoj1878 $
传送门


思路:

$ 莫队维护区间种类,虽然可以主席树。$


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
const int maxm=1e6+5;

int n,m,l,r,cur,tem;
int a[maxn],ans[maxn],num[maxn];
struct query
{
int l,r,pos;
} q[maxm];
bool cmp(query q1,query q2)
{
//if(q1.l/cur==q2.l/cur) return q1.r<q2.r;
return q1.l/cur == q2.l/cur ? (q1.l/cur & 1) ? q1.r < q2.r : q1.r >q2.r : q1.l/cur < q2.l/cur;

//else return q1.l/cur<q2.l/cur;
}
void Add(int x)
{
num[a[x]]++;
if(num[a[x]]==1) tem++;
}
void Remove(int x)
{
num[a[x]]--;
if(num[a[x]]==0)tem--;
}
inline int read()
{
char c=getchar();
int x=0,f=1;
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*f;
}

int main()
{
while(~scanf("%d",&n))
{
cur=sqrt(n);
for(int i=1; i<=n; ++i)
a[i]=read();
//scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1; i<=m; i++)
{
q[i].l=read();
q[i].r=read();
//scanf("%d%d",&q[i].l,&q[i].r);
q[i].pos=i;
}
sort(q+1,q+m+1,cmp);
int nowl=0,nowr=0;
for(int i=1;i<=m;i++)
{
while(nowl<q[i].l)
{
Remove(nowl);
nowl++;
}
while(nowr>q[i].r)
{
Remove(nowr);
nowr--;
}
while(nowl>q[i].l)
{
nowl--;
Add(nowl);
}
while(nowr<q[i].r)
{
nowr++;
Add(nowr);
}
ans[q[i].pos]=tem;
}
for(int i=1;i<=m;i++)
printf("%d\n",ans[i]);
}
return 0;
}

描述:

$ bzoj4540&codeforces $
传送门


思路:

$ 先预处理异或的前缀和sum,然后对于询问[l,r]来说等价于 \\
询问sum[l-1]到sum[r]里异或为k的数对个数,莫队更新即可。$


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+5;
int n,m,k,a[maxn],block,cnt[maxn*20];
ll ans[maxn],tem;
struct Query
{
int l,r,id;
} q[maxn];
bool cmp(Query x,Query y)
{
if(x.l/block==y.l/block)
return x.r<y.r;
return x.l/block<y.l/block;
}

void add(int x)
{
tem+=cnt[k^a[x]];
cnt[a[x]]++;
}


void del(int x)
{
cnt[a[x]]--;
tem-=cnt[k^a[x]];
}
int main()
{
scanf("%d %d %d",&n,&m,&k);
block=sqrt(n);
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
a[i]^=a[i-1];
}
for(int i=1; i<=m; i++)
{
scanf("%d %d",&q[i].l,&q[i].r);
q[i].l--;
q[i].id=i;
}
sort(q+1,q+m+1,cmp);
int l=0,r=-1;
tem=0;
for(int i=1; i<=m; i++)
{
while(l<q[i].l)
{
del(l++);
}
while(l>q[i].l)
{
add(--l);
}
while(r<q[i].r)
{
add(++r);
}
while(r>q[i].r)
{
del(r--);
}
ans[q[i].id]=tem;
}
for(int i=1; i<=m; i++)
printf("%lld\n",ans[i]);
}

描述:

$ hdu5213$
传送门


思路:

$ 简单容斥一下,设f(l,r)为[l,r]内和为k的数对个数,对于询问 \\
(l,r,u,v),Ans=f(l,v)-f(l,u-1)-f(r+1,v)+f(r+1,u-1)。 $


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
const int maxn=30000+10;
int n,m,k,a[maxn],block,ans[maxn],tem,cnt[maxn<<1];
struct Query
{
int l,r,id,op;
} q[maxn<<2];

bool cmp(Query x,Query y)
{
if(x.l/block==y.l/block)
return x.r<y.r;
return x.l/block<y.l/block;
}

void add(int x)
{
if(k>=a[x])
tem+=cnt[k-a[x]];
cnt[a[x]]++;
}

void del(int x)
{
cnt[a[x]]--;
if(k>=a[x])
tem-=cnt[k-a[x]];
}


int main()
{
while(~scanf("%d",&n))
{
memset(cnt,0,sizeof(cnt));
memset(ans,0,sizeof(ans));
block=sqrt(n);
scanf("%d",&k);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
scanf("%d",&m);
int cnt=0;
for(int i=1; i<=m; i++)
{
int l,r,u,v;
scanf("%d %d %d %d",&l,&r,&u,&v);
q[++cnt].l=l,q[cnt].r=v,q[cnt].id=i,q[cnt].op=1;
q[++cnt].l=r+1,q[cnt].r=u-1,q[cnt].id=i,q[cnt].op=1;
q[++cnt].l=l,q[cnt].r=u-1,q[cnt].id=i,q[cnt].op=-1;
q[++cnt].l=r+1,q[cnt].r=v,q[cnt].id=i,q[cnt].op=-1;
}
sort(q+1,q+cnt+1,cmp);
int l=1,r=0;
tem=0;
for(int i=1; i<=cnt; i++)
{
while(l<q[i].l)
{
del(l++);
}
while(l>q[i].l)
{
add(--l);
}
while(r<q[i].r)
{
add(++r);
}
while(r>q[i].r)
{
del(r--);
}
ans[q[i].id]+=q[i].op*tem;
}
for(int i=1; i<=m; i++)
printf("%d\n",ans[i]);
}
}

描述:

$ hdu4638$
传送门


思路:

$ 首先应该发现,让段数尽量少更优,设加进来的数为x,若x-1和x+1 \\
都在区间中出现了,Ans—,只出现一个,Ans不变,都不出现,Ans++, \\
减去一个数同理。 $


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int t,n,m,a[maxn],block,ans[maxn],tem,cnt[maxn];
struct Query
{
int l,r,id;
} q[maxn];

bool cmp(Query x,Query y)
{
if(x.l/block==y.l/block)
return x.r<y.r;
return x.l/block<y.l/block;
}

void add(int x)
{
if(cnt[a[x]-1]&&cnt[a[x]+1])
tem--;
else if(!cnt[a[x]-1]&&!cnt[a[x]+1])
tem++;
cnt[a[x]]++;
}

void del(int x)
{
cnt[a[x]]--;
if(cnt[a[x]-1]&&cnt[a[x]+1])
tem++;
else if(!cnt[a[x]-1]&&!cnt[a[x]+1])
tem--;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
for(int i=0;i<=n;i++) cnt[i]=0;
for(int i=0;i<=m;i++) ans[i]=0;
block=sqrt(n);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
for(int i=1; i<=m; i++)
{
scanf("%d %d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+1,q+m+1,cmp);
int l=1,r=0;
tem=0;
for(int i=1; i<=m; i++)
{
while(l<q[i].l)
{
del(l++);
}
while(l>q[i].l)
{
add(--l);
}
while(r<q[i].r)
{
add(++r);
}
while(r>q[i].r)
{
del(r--);
}
ans[q[i].id]=tem;
}
for(int i=1; i<=m; i++)
printf("%d\n",ans[i]);
}
}

描述:

$ 洛谷4396$
传送门


思路:

$ 统计区间内权值在[u,v]之间的数的个数,在莫队转移的时候 \\
把数插进树状数组里即可,复杂度O(n$sqrt{n}$logn)。 $


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+10;
int n,m,a[maxn],block,b[maxn],tree[maxn],tree2[maxn],cnt[maxn],tem,tem2,mx;

void change(int x,int d)
{
while(x<=maxn)
{
tree[x]+=d;
x+=(x&-x);
}
}

int query(int x)
{
int res=0;
while(x>0)
{
res+=tree[x];
x-=(x&-x);
}
return res;
}
void change2(int x,int d)
{
while(x<=maxn)
{
tree2[x]+=d;
x+=(x&-x);
}
}

int query2(int x)
{
int res=0;
while(x>0)
{
res+=tree2[x];
x-=(x&-x);
}
return res;
}

struct Query
{
int l,r,low,high,id;
} q[maxn];

bool cmp(Query x,Query y)
{
if(b[x.l]==b[y.l])
return x.r<y.r;
return x.l<y.l;
}

struct Ans
{
int ans1,ans2;
} ans[maxn];

void add(int x)
{
change(a[x],1);
cnt[a[x]]++;
if(cnt[a[x]]==1)
change2(a[x],1);
}


void rem(int x)
{
change(a[x],-1);
cnt[a[x]]--;
if(cnt[a[x]]==0)
change2(a[x],-1);
}



int main()
{
scanf("%d %d",&n,&m);
block=sqrt(n);
mx=1e9;
for(int i=1; i<=n; i++)
scanf("%d",&a[i]),mx=max(a[i],mx);
for(int i=1; i<=m; i++)
{
scanf("%d %d %d %d",&q[i].l,&q[i].r,&q[i].low,&q[i].high);
q[i].id=i;
b[i]=(i-1)/block+1;
}

sort(q+1,q+m+1,cmp);
int l=1,r=0;
tem=tem2=0;
for(int i=1; i<=m; i++)
{
while(q[i].l<l)
add(--l);
while(q[i].l>l)
rem(l++);
while(q[i].r<r)
rem(r--);
while(q[i].r>r)
add(++r);
tem=query(q[i].high)-query(q[i].low-1);
tem2=query2(q[i].high)-query2(q[i].low-1);

ans[q[i].id].ans1=tem;
ans[q[i].id].ans2=tem2;
}
for(int i=1; i<=m; i++)
printf("%d %d\n",ans[i].ans1,ans[i].ans2);
}

描述:

$ hdu6534$
传送门


思路:

$ 和上面那题是一样的,莫队转移的时候维护一个树状数组即可 \\
预处理把a[i],a[i]-k和a[i]+k离散。$


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=27000+10;
int n,m,k,a[maxn],ans[maxn],block,c[maxn*3],tem,X[maxn],Y[maxn];
struct Query
{
int l,r,id;
} q[maxn];

bool cmp(Query x,Query y)
{
if(x.l/block!=y.l/block)
return x.l/block<y.l/block;
return x.r<y.r;
}

void ins(int x,int d)
{
while(x<maxn*3)
{
c[x]+=d;
x+=(x&-x);
}
}

int query(int x)
{
int res=0;
while(x>0)
{
res+=c[x];
x-=(x&-x);
}
return res;
}

void add(int x)
{
tem+=query(X[x]);
if(Y[x]-1>=1)
tem-=query(Y[x]-1);
ins(a[x],1);
}

void del(int x)
{
ins(a[x],-1);
tem-=query(X[x]);
if(Y[x]-1>=1)
tem+=query(Y[x]-1);
}


vector<int>disc,order;
bool cmp2(int x,int y)
{
return disc[x]<disc[y];
}

void discrete()
{
order.clear();
int n=disc.size();
for(int i=0; i<n; i++)
order.push_back(i);
sort(order.begin(),order.end(),cmp2);
for(int i=0,j=1; i<n; i++)
{
if(i+1<n&&disc[order[i]]!=disc[order[i+1]])
disc[order[i]]=j++;
else
disc[order[i]]=j;
}
}

int main()
{
scanf("%d %d %d",&n,&m,&k);
block=sqrt(n);

for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
disc.push_back(a[i]);
disc.push_back(a[i]+k);
disc.push_back(a[i]-k);
}

discrete();

for(int i=0; i<disc.size(); i+=3)
{
a[i/3+1]=disc[i];
X[i/3+1]=disc[i+1];
Y[i/3+1]=disc[i+2];
}

for(int i=1; i<=m; i++)
{
scanf("%d %d",&q[i].l,&q[i].r);
q[i].id=i;
}

sort(q+1,q+m+1,cmp);
int l=1,r=0;
tem=0;
for(int i=1; i<=m; i++)
{
while(q[i].l<l)
{
add(--l);
}
while(q[i].l>l)
{
del(l++);
}
while(q[i].r<r)
{
del(r--);
}
while(q[i].r>r)
{
add(++r);
}
ans[q[i].id]=tem;
}
for(int i=1; i<=m; i++)
printf("%d\n",ans[i]);
}

$hdu4676与fuzhou university 2226待补, 未完待续…$

avatar Decaku 很菜但也很想carry