upc Cafebazaar’s Chess Tournament 思维 + FFT

说实话，题我没大读懂。
听zwz大佬说这个题挑战者的两个能力值不能与被挑战者能力值相等，不过可以取实数，所以这句话看没看到都不影响这个思路，因为每个相等的数都可以+0.1或-0.1来实现不相等且不影响答案，所以以下按照能力值可以相等来讲比较清楚，具体的还是看下面吧。。。
以下设挑战者(能力值不固定的人)为A，给出的n个人都为B。
这个题容易被两个能力值限制住思维，觉得两个变量应该放在一起看。先说一下怎么做。我们尝试是否可以把两个值分开看。而考虑单个值的贡献时候，显然只需要考虑A在 [ 0 , n + 1 ] [0,n+1] [0,n+1]的贡献，0为全输，n+1为全赢。那么对于B一个能力值 x ，当且仅当A的能力值 >x 的时候才能有贡献(注意是要大于)。那么对于每个 x ，可以利用差分将 [ x + 1 , n + 1 ] [x+1,n+1] [x+1,n+1]全加一。对于前后两个能力值都这么做一遍，让后得到两个A前后能力值在 [ 0 , n + 1 ] [0,n+1] [0,n+1]的贡献，去重之后求一下两个数组每个数相加之后能得到的不同数的数量即为答案。至于这个怎么求，显然有个 O ( n 2 ) O(n^2) O(n2)的算法(划掉，让后lcdl用FFT O ( N l o g N ) O(NlogN) O(NlogN)秒了(在线%lc学长)。把两个数组看成两个多项式，数组元素看成多项式的指数，将其系数设为1，让后乘起来之后看看有几项系数不为1即可。
下面瞎扯一下为啥是对的。
我们可以想想胜利的2分怎么来的(为了避免小数，我都乘了2)，显然是A的两个能力值都大于B的。那么如果只有其中一个大于，另一个小于，得分是不是应该也取一半呢？显然这种是平局得分为1=2/2。再看输的情况显然为0。两个能力值对应两分，一个能力值对应一分，零个能力值对应零分，而且最终还是算总分。这种种巧合不就是暗示我们可以分开看嘛。。。就是左边能力值取 [ 0 , n + 1 ] [0,n+1] [0,n+1]之间一个值，右边也是取 [ 0 , n + 1 ] [0,n+1] [0,n+1]之间一个值，两个的贡献加起来不就是总得分嘛，而且我们可以处理出他们的贡献，显然这种方法正确。

虽然我不会FFT，但是某谷有板子啊。
我把我的代码和板子分开了，可读性能高点吧。。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#define pb push_back
using namespace std;
const int MAXN=1e7+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
//以下为板子
const double Pi=acos(-1.0);
struct complex
{
    double x,y;
    complex (double xx=0,double yy=0){x=xx,y=yy;}
}a[MAXN],b[MAXN];
complex operator + (complex a,complex b){ return complex(a.x+b.x , a.y+b.y);}
complex operator - (complex a,complex b){ return complex(a.x-b.x , a.y-b.y);}
complex operator * (complex a,complex b){ return complex(a.x*b.x-a.y*b.y , a.x*b.y+a.y*b.x);}
int N,M;
int l,r[MAXN];
int limit=1;
void fast_fast_tle(complex *A,int type)
{
    for(int i=0;i<limit;i++)
        if(i<r[i]) swap(A[i],A[r[i]]);
    for(int mid=1;mid<limit;mid<<=1)
    {
        complex Wn( cos(Pi/mid) , type*sin(Pi/mid) );
        for(int R=mid<<1,j=0;j<limit;j+=R)
        {
            complex w(1,0);
            for(int k=0;k<mid;k++,w=w*Wn)
            {
                 complex x=A[j+k],y=w*A[j+mid+k];
                A[j+k]=x+y;
                A[j+mid+k]=x-y;
            }
        }
    }
}
//以上为板子
int n,cnt;
int aa[MAXN],bb[MAXN];
int p1[MAXN],p2[MAXN];

void change(vector<int>&v)
{
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}
int main()
{
//以下处理两个能力值[0,n+1]的贡献
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&aa[i],&bb[i]);
        p1[n+2]--; p1[aa[i]+1]++;
        p2[n+2]--; p2[bb[i]+1]++;
    }
    for(int i=1;i<=n+1;i++) p1[i]+=p1[i-1],p2[i]+=p2[i-1];
    vector<int>v1,v2;
    for(int i=0;i<=n+1;i++) v1.pb(p1[i]),v2.pb(p2[i]);
    change(v1); change(v2);
    N=v1.size(),M=v2.size();
    for(int i=0;i<N;i++) a[v1[i]].x=1;
    for(int i=0;i<M;i++) b[v2[i]].x=1;
//以下为板子
//-------------------------------------------------------------------

    N=n+1,M=n+1;
    while(limit<=N+M) limit<<=1,l++;
    for(int i=0;i<limit;i++)
        r[i]= ( r[i>>1]>>1 )| ( (i&1)<<(l-1) ) ;
    fast_fast_tle(a,1);
    fast_fast_tle(b,1);
    for(int i=0;i<=limit;i++) a[i]=a[i]*b[i];
    fast_fast_tle(a,-1);
    int ans=0;

//-------------------------------------------------------------------
//以上为板子

    for(int i=0;i<=N+M;i++)
        if((int)(a[i].x/limit+0.5)>=1) ans++;
    printf("%d\n",ans);
    return 0;
}