P3660 [USACO17FEB]Why Did the Cow Cross the Road III G

Link

题意：

给定长度为 \(2N\) 的序列，\(1~N\) 各处现过 \(2\) 次，i第一次出现位置记为\(ai\)，第二次记为\(bi\)，求满足\(ai<aj<bi<bj\)的对数.

转化一下题意：求 \(a_i - b_i\) 中出现次数为 \(1\) 的个数。

既然数据范围那么小，直接上莫队。

先预处理出每个数第一次出现以及第二次出现的位置。

然后就变成了我们熟悉的区间问题。就可以套用莫队的板子啦，

但最后答案要除以二，因为 \((x,y)\) 这两个数对，你在 \(x\) 这个位置会算一遍，在 \(y\) 这个位置同样也会被算一遍。

可这个却只能算一遍，所以最后答案要除以二。

计算移动指针的贡献的时候，不要忘记计算移动前和移动后对现在答案的影响。

具体的细节可以看代码：

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

const int N = 1e5+10;

int n,m,ans,tmp,l,r,block,x;

int pos[N],fir[N],sec[N],cnt[N],a[N];

struct node

{

    int l,r,id;

}q[N];

inline int read()

{

    int s = 0,w = 1; char ch = getchar();

    while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}

    while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}

    return s * w;

}

bool comp(node a,node b)

{

    if(pos[a.l] == pos[b.l]) return a.r < b.r;

    return pos[a.l] < pos[b.l];

}

void add(int x)

{

	if(cnt[a[x]] == 0) tmp++;//如果说当前这个数在这段区间第一次出现，对答案的贡献加1

    cnt[a[x]]++;

    if(cnt[a[x]] == 2) tmp--;//出现两次对答案没有贡献

}

void del(int x)

{

    if(cnt[a[x]] == 2) tmp++;//出现次数变为一次，就会对答案的贡献加1

    cnt[a[x]]--;

    if(cnt[a[x]] == 0) tmp--;//没有出现，对答案的贡献就会变为0

}

int main()

{

    n = read(); block = sqrt(2 * n);

    for(int i = 1; i <= 2 * n; i++)

    {

        a[i] = read();

        if(fir[a[i]] == 0) fir[a[i]] = i;//求一个数第一次以及第二次出现的位置

        else sec[a[i]] = i;

    }

    for(int i = 1; i <= 2 * n; i++) pos[i] = (i - 1) / block + 1;//分块预处理，注意是对序列分块

    for(int i = 1; i <= n; i++)

    {

        q[i].l = fir[i];

        q[i].r = sec[i];

        q[i].id = i;

    }

    sort(q+1,q+n+1,comp);

    l = 1, r = 0, tmp = 0;

    for(int i = 1; i <= n; 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 += tmp;

    }

    printf("%d\n",ans/2);//最后不要忘记除以二

    return 0;

}

巴特西

P3660 [USACO17FEB]Why Did the Cow Cross the Road III G

最新文章

热门文章