Kattis-Curious Cupid(莫队)

admin管理员组

文章数量:1612099

题目链接

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  i th man speaks language  ai  and the  i th 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  i th man.

• The third line contains  N  integers  b0,b1,b2,…,bN−1 , where  bi  ( 0≤bi<K ) is the language spoken by the  i th 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.

3 4 2
0 0 1
0 0 0
0 0
2 2
0 1
1 2

1
0
2
1

有K种不同的语言，每个人只说一种语言。有N个男性，N个女性。

现在需要进行男女配对，每个人都想找一个和自己用同一种语言的异性，第i个男性的语言是ai, 第i个女性的语言是bi。

现在给出M个区间作为询问，每次需要回答在[L, R]区间的男女最多能够配对成多少对情侣。

题解：

这题是多组区间查询，我们考虑莫队算法对查询排序
相邻两个区间的转移可以通过维护区间内不同数字的个数进行转移
转移复杂度O(1)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const int inf=0x3fffffff;
const ll mod=1000000007;
const int maxn=5e4+100;
const int maxm=1e6+100;
int a[maxn],b[maxn];
int cnt1[maxm],cnt2[maxm];

int n,m,k;
int unit;

struct node
{
    int l,r,id,ans;
    bool operator < (const node &t) const{
        if(l/unit==t.l/unit) return r<t.r;
        else return l/unit<t.l/unit;
    }
}q[maxm];
void solve()
{
    int l=1,r=0;
    int ans=0;
    rep(i,1,m+1)
    {
        while(l<q[i].l)
        {
            if(a[l]==b[l]) ans--;
            else
            {
                if(cnt1[a[l]]<=cnt2[a[l]]) ans--;
                if(cnt2[b[l]]<=cnt1[b[l]]) ans--;
            }
            cnt1[a[l]]--,cnt2[b[l]]--;
            l++;
        }
        while(l>q[i].l)
        {
            l--;
            if(a[l]==b[l]) ans++;
            else
            {
                if(cnt1[a[l]]<cnt2[a[l]]) ans++;
                if(cnt2[b[l]]<cnt1[b[l]]) ans++;
            }
            cnt1[a[l]]++,cnt2[b[l]]++;
        }
        while(r>q[i].r)
        {
            if(a[r]==b[r]) ans--;
            else
            {
                if(cnt1[a[r]]<=cnt2[a[r]]) ans--;
                if(cnt2[b[r]]<=cnt1[b[r]]) ans--;
            }
            cnt1[a[r]]--,cnt2[b[r]]--;
            r--;
        }
        while(r<q[i].r)
        {
            r++;
            if(a[r]==b[r]) ans++;
            else
            {
                if(cnt1[a[r]]<cnt2[a[r]]) ans++;
                if(cnt2[b[r]]<cnt1[b[r]]) ans++;
            }
            cnt1[a[r]]++,cnt2[b[r]]++;
        }
        q[i].ans=ans;
    }
}
bool cmp(node a,node b)
{
    return a.id<b.id;
}


int main()
{
    scanf("%d%d%d",&n,&m,&k);
    rep(i,1,n+1) scanf("%d",&a[i]);
    rep(i,1,n+1) scanf("%d",&b[i]);
    rep(i,1,m+1) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i,q[i].l++,q[i].r++;
    unit=(int)sqrt(n);
    sort(q+1,q+m+1);
    solve();
    sort(q+1,q+m+1,cmp);
    rep(i,1,m+1) printf("%d\n",q[i].ans);
    return 0;
}

本文标签： curiousKattis莫队Cupid