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
莫隊(duì)算法描述
這里和這里還有這里是一些資料载荔。我個(gè)人的理解是這樣的陪毡，給你一堆查詢(xún)區(qū)間，如果q(l,r)可以用q(l+/-n)(r+/-m)以O(shè)(n)復(fù)雜度推出來(lái)，就可以用莫隊(duì)算法，所以實(shí)際上求的是每個(gè)(l,r)點(diǎn)的最小曼哈頓距離樹(shù)耸三，莫隊(duì)算法的處理是將這些點(diǎn)分塊排序拓轻，改變了查詢(xún)的順序旬盯，從而降低算法復(fù)雜度而钞。具體見(jiàn)上面的鏈接和代碼注釋沙廉。
題意
給你兩串?dāng)?shù)，一串代表男的臼节，一串代表女的撬陵，每個(gè)數(shù)代表這個(gè)人說(shuō)的語(yǔ)言，現(xiàn)在要給一個(gè)區(qū)間[L,R]里面的人配對(duì)网缝，只有語(yǔ)言相同的才能配一對(duì)巨税，問(wèn)對(duì)于每個(gè)區(qū)間，最多能配成幾對(duì)粉臊。莫隊(duì)算法處理草添。
N：男人和女人的個(gè)數(shù)
M：查詢(xún)次數(shù)
K：語(yǔ)言總數(shù)
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 查詢(xún)的順序編號(hào)
}
}p[N]; // p數(shù)組存儲(chǔ)查詢(xún)
bool cmp(node a, node b) { // 排序 塊的順序?yàn)榈谝魂P(guān)鍵字，r為第二關(guān)鍵字
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的時(shí)候更新某種語(yǔ)言人數(shù)扼仲，取男女中的較小值更新到答案中
if(a[x] != b[x])
//男人女人語(yǔ)言不一樣 cnt減去男人和女人說(shuō)a[x]語(yǔ)言的最小值和男人和女人說(shuō)b[x]語(yǔ)言的最小值
cnt -= min(c[0][a[x]], c[1][a[x]]) + min(c[0][b[x]], c[1][b[x]]);
else //男人女人語(yǔ)言一樣 cnt減去男人和女人說(shuō)a[x]語(yǔ)言的最小值
cnt -= min(c[0][a[x]], c[1][a[x]]);
c[0][a[x]] += y; //更新語(yǔ)言數(shù)量
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() { //輸出數(shù)組c 測(cè)試用函數(shù)
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數(shù)組 0男人 1女人 c[0/1][x]為該性別說(shuō)x語(yǔ)言的人的數(shù)量
int pl = 0, pr = 0;
cnt = a[0] == b[0] ? 1 : 0;
//cnt 計(jì)數(shù)變量 如果第0個(gè)男人和第0個(gè)女人說(shuō)的語(yǔ)言相同 cnt為1 否則為0
c[0][a[0]]++; //說(shuō)a[0] b[0]語(yǔ)言的男人和女人數(shù)量 + 1
c[1][b[0]]++;
for(int i = 0;i < m;i++) { //對(duì)查詢(xún)次數(shù)遍歷
int id = p[i].id, l = p[i].l, r = p[i].r;
//第i次查詢(xún)的id l r（此時(shí)p數(shù)組已經(jīng)排序远寸，排序方法見(jiàn)cmp
for(int j = pr + 1;j <= r;j++) //從pr和pl開(kāi)始O(1)的推到r和l的查詢(xún)次數(shù)
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; //然后把開(kāi)始的那個(gè)點(diǎn)更新為這個(gè)點(diǎn)
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 男人和女人的個(gè)數(shù) m 查詢(xún)次數(shù) k 語(yǔ)言總數(shù)
for(int i = 0;i < n;i++) //數(shù)組a[i] 第i個(gè)男人說(shuō)的語(yǔ)言
scanf("%d", &a[i]);
for(int i = 0;i < n;i++) //數(shù)組b[i] 第i個(gè)女人說(shuō)的語(yǔ)言
scanf("%d", &b[i]);
int bk = sqrt(n + 1.0); // bk 分塊的塊數(shù)
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); //輸入查詢(xún) 保存在node數(shù)組 p[i] 中
sort(p, p+m, cmp); //為p排序
solve();
}
return 0;
}
