Problem D
Curious Cupid
There are K different languages in the world. Each person speaks one and only one language. There are exactly N single men and N single women.
Cupid, the god of love, wants to match every single man to a single woman, and vice versa. Everybody wants to find a partner who speaks the same language as s/he does. Communication between the couple is very important! Cupid asks these N men to stand in a line, and likewise for the N women. Cupid knows that the ith man speaks language ai and the ith woman speaks language bi.
It is too hard for Cupid to match all people at the same time. What Cupid does is to repeatedly look at some specific interval in these two lines, pick the men and women in that interval and find the maximum number of man-woman pairs who speak the same language and can be matched.
Input
- The first line contains three integers N, M and K (1≤N≤50000,1≤M≤50000,1≤K≤1000000).
- The second line contains N integers a0,a1,a2,…,aN−1, where ai (0≤ai<K) is the language spoken by the ith man.
- The third line contains N integers b0,b1,b2,…,bN−1, where bi (0≤bi<K) is the language spoken by the ith woman.
- In the next M lines, each line contains two integers L and R (0≤L≤R<N), representing the starting and ending index of the interval. That is, Cupid is looking at men L,L+1,…,R and women L,L+1,…,R.
Output
For each interval, print the maximum number of couples Cupid could match.
Sample Input 1
3 4 2
0 0 1
0 0 0
0 0
2 2
0 1
1 2
Sample output 1
1
0
2
1
莫队算法描述
这里和这里还有这里是一些资料。我个人的理解是这样的，给你一堆查询区间，如果q(l,r)可以用q(l+/-n)(r+/-m)以O(n)复杂度推出来，就可以用莫队算法，所以实际上求的是每个(l,r)点的最小曼哈顿距离树，莫队算法的处理是将这些点分块排序，改变了查询的顺序，从而降低算法复杂度。具体见上面的链接和代码注释。
题意
给你两串数，一串代表男的，一串代表女的，每个数代表这个人说的语言，现在要给一个区间[L,R]里面的人配对，只有语言相同的才能配一对，问对于每个区间，最多能配成几对。莫队算法处理。
N：男人和女人的个数
M：查询次数
K：语言总数
AC代码
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 51000
#define K 1000100
int n, m, k;
int a[N], b[N], pos[N], c[2][K], ans[N], cnt;
struct node {
int l, r, id;
void sc(int i){
scanf("%d%d", &l, &r);
id = i; //id 查询的顺序编号
}
}p[N]; // p数组存储查询
bool cmp(node a, node b) { // 排序 块的顺序为第一关键字，r为第二关键字
if(pos[a.l] == pos[b.l])
return a.r < b.r;
return pos[a.l] < pos[b.l];
}
void update(int x, int y) {
//每次update的时候更新某种语言人数，取男女中的较小值更新到答案中
if(a[x] != b[x])
//男人女人语言不一样 cnt减去男人和女人说a[x]语言的最小值和男人和女人说b[x]语言的最小值
cnt -= min(c[0][a[x]], c[1][a[x]]) + min(c[0][b[x]], c[1][b[x]]);
else //男人女人语言一样 cnt减去男人和女人说a[x]语言的最小值
cnt -= min(c[0][a[x]], c[1][a[x]]);
c[0][a[x]] += y; //更新语言数量
c[1][b[x]] += y;
if(a[x] != b[x]) //然后再加回去
cnt += min(c[0][a[x]], c[1][a[x]]) + min(c[0][b[x]], c[1][b[x]]);
else
cnt += min(c[0][a[x]], c[1][a[x]]);
}
/*
void pri() { //输出数组c 测试用函数
for(int j = 0;j < 2;j++)
for(int i = 0;i < n;i++)
printf("%d%c", c[j][i], " \n"[i==n-1]);
}
*/
void solve() {
memset(c, 0, sizeof(c));//c数组 0男人 1女人 c[0/1][x]为该性别说x语言的人的数量
int pl = 0, pr = 0;
cnt = a[0] == b[0] ? 1 : 0;
//cnt 计数变量 如果第0个男人和第0个女人说的语言相同 cnt为1 否则为0
c[0][a[0]]++; //说a[0] b[0]语言的男人和女人数量 + 1
c[1][b[0]]++;
for(int i = 0;i < m;i++) { //对查询次数遍历
int id = p[i].id, l = p[i].l, r = p[i].r;
//第i次查询的id l r（此时p数组已经排序，排序方法见cmp
for(int j = pr + 1;j <= r;j++) //从pr和pl开始O(1)的推到r和l的查询次数
update(j, 1);
for(int j = pr;j > r;j--)
update(j, -1);
for(int j = pl;j < l;j++)
update(j, -1);
for(int j = pl-1; j >= l;j--)
update(j, 1);
pr = r; pl = l; //然后把开始的那个点更新为这个点
ans[id] = cnt; //记录ans的cnt
}
for(int i = 0;i < m;i++) //以输入的顺序输出答案
printf("%d\n", ans[i]);
}
int main() {
while(~scanf("%d%d%d", &n, &m, &k)) {
//输入n 男人和女人的个数 m 查询次数 k 语言总数
for(int i = 0;i < n;i++) //数组a[i] 第i个男人说的语言
scanf("%d", &a[i]);
for(int i = 0;i < n;i++) //数组b[i] 第i个女人说的语言
scanf("%d", &b[i]);
int bk = sqrt(n + 1.0); // bk 分块的块数
for(int i = 0;i < n;i++)
pos[i] = i / bk; // pos[i] 第i组 ？？ 被分到第pos[i]块
for(int i = 0;i < m;i++)
p[i].sc(i); //输入查询 保存在node数组 p[i] 中
sort(p, p+m, cmp); //为p排序
solve();
}
return 0;
}
