admin管理员组

文章数量:1612097


.
.
给定n个男女排列，每个人会说一种语言，相同语言的一对男女可以组成一对cp，问区间 [l,r] 之间最多有多少对cp
.
.
直接套莫队就好了
.
.

#include <cstdio>
#include <iostream>
#include <complex>
#include <cmath>
#include <map>
#include <algorithm>

using namespace std;

typedef long long LL;
const int maxn=50000+5;
const int maxk=1000000+5;
int n, m, k, a[maxn], b[maxn], unit;
int ca[maxk], cb[maxk], ans[maxn];

struct Query {
    int l, r, id;
} node[maxn];

bool cmp(Query a, Query b) {
    if (a.l/unit!=b.l/unit) return a.l/unit<b.l/unit;
    else return a.r<b.r;
}
int tmp;

void add(int x) {
    if (a[x]==b[x]) {
        tmp++;
        ca[a[x]]++;
        cb[b[x]]++;
    }
    else {
        if (ca[a[x]]<cb[a[x]]) tmp++;
        ca[a[x]]++;
        if (ca[b[x]]>cb[b[x]]) tmp++;
        cb[b[x]]++;
    }
}
void rmv(int x) {
    if (a[x]==b[x]) {
        tmp--;
        ca[a[x]]--;
        cb[b[x]]--;
    }
    else {
        if (ca[a[x]]<=cb[a[x]]) tmp--;
        ca[a[x]]--;
        if (ca[b[x]]>=cb[b[x]]) tmp--;
        cb[b[x]]--;
    }
}
void work() {
    int l=1, r=0;
    for (int i=0; i<m; i++) {
        while (r<node[i].r) {
            add(++r);
        }
        while (r>node[i].r) {
            rmv(r--);
        }
        while (l<node[i].l) {
            rmv(l++);
        }
        while (l>node[i].l) {
            add(--l);
        }
        ans[node[i].id]=tmp;
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i=0; i<n; i++) scanf("%d", a+i);
    for (int i=0; i<n; i++) scanf("%d", b+i);
    for (int i=0; i<m; i++) {
        scanf("%d%d", &node[i].l, &node[i].r);
        node[i].id=i;
    }
    unit=(int)sqrt(n);
    sort(node, node+m, cmp);
    work();
    for (int i=0; i<m; i++) printf("%d\n", ans[i]);
}

本文标签： curiousCupid

版权声明：本文标题：Curious Cupid 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dianzi/1728631004a1167082.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。