尔尔序的神奇计数问题(set容器)

描述

传送门：swustoj-2612

  现在有4个集合，分别为$A,B,C,D$，且每一个集合的大小都是n。尔尔序想求解一个问题，现在他把$A,B,C$的交集的大小、$A,B,D$的交集的大小，$A,C,D$的交集的大小，$B,C,D$的交集的大小之和记为$X$，同时把$A,B$的交集的大小、$A,C$的交集的大小、$A,D$的交集的大小、$B,C$的交集的大小、$B,D$的交集的大小之和记为Y，求解$|X−Y|$的值。

Input

第一行输入一个整数$n(1\leq n \leq5 \times 10^4)$代表这4个集合的大小。
第二行输入$n$整数$A_i\ (1\leq A_i \leq10^{18})$，代表集合$A$中的数。
第三行输入$n$整数$B_i\ (1\leq B_i \leq10^{18})$，代表集合$B$中的数。
第四行输入$n$整数$C_i\ (1\leq C_i \leq10^{18})$，代表集合$C$中的数。
第五行输入$n$整数$D_i\ (1\leq D_i \leq10^{18})$，代表集合$D$中的数。
保证在同一集合内没有重复的数。

Output

输出$|X−Y|$的值。

Examples

• intput

  4
  1 2 3 4
  2 3 4 5
  3 4 5 7
  7 6 3 1
  4
  1 2 3 4
  1 2 3 4
  1 2 3 5
  3 4 5 6

• output

  6
  7

思路

• 其实就是set的直接应用，求： $$|A∩B∩C+A∩B∩D+A∩C∩D+B∩C∩D-A∩B-A∩D-B∩C-B∩D|$$
• 也可以用容次原理转换成 $$A∪B∪C∪D-(A+B+C+D)+A∩B∩C∩D+C∩D$$ 但是莫名其妙要比直接的慢就没用这个
• x在set1中存在就是set1.find(x)!=set1.end();
• 然后暴力出奇迹即可，具体看代码。

代码

#include<bits/stdc++.h>
using namespace std;
#define CRL(a) memset(a,0,sizeof(a))
#define MAX 0xfffffff
typedef unsigned long long LL;
typedef  long long ll;
const double Pi = acos(-1);
const double e = exp(1.0);
const int mod =1e9+7;

set <ll> set1,set2,set3,set4;
ll a[50005],b[50005],c[50005],d[50005],ans=0;

int main()
{
    int n,x;
    while(cin>>n)
    {
        ans=0;
        set1.clear();		//清空set
        set2.clear();
        set3.clear();
        set4.clear();
        for(int i=0; i<n; i++)
        {
            scanf("%lld",&a[i]);
            set1.insert(a[i]);
        }

        for(int i=0; i<n; i++)
        {
            scanf("%lld",&b[i]);
            set2.insert(b[i]);
        }

        for(int i=0; i<n; i++)
        {
            scanf("%lld",&c[i]);
            set3.insert(c[i]);
        }

        for(int i=0; i<n; i++)
        {
            scanf("%lld",&d[i]);
            set4.insert(d[i]);
            if(set2.find(d[i])!=set2.end()&&set3.find(d[i])!=set3.end())
                ans++;
            if(set1.find(d[i])!=set1.end()&&set3.find(d[i])!=set3.end())
                ans++;
            if(set1.find(d[i])!=set1.end()&&set2.find(d[i])!=set2.end())
                ans++;

            if(set1.find(d[i])!=set1.end())
                ans--;
            if(set2.find(d[i])!=set2.end())
                ans--;
        }

        for(int i=0; i<n; i++)
        {
            if(set1.find(c[i])!=set1.end()&&set2.find(c[i])!=set2.end())
                ans++;

            if(set1.find(b[i])!=set1.end())
                ans--;

            if(set1.find(c[i])!=set1.end())
                ans--;

            if(set2.find(c[i])!=set2.end())
                ans--;
        }

        cout<<abs(ans)<<endl;
    }

    return 0;
}