HDU5213(容斥定理+莫队算法）

传送门

题意

给出n个数和幸运数k，m次询问，每次询问[l1,r1]和[l2,r2]有多少对数满足x+y=k，x∈[l1,r1],y∈[l2,r2]

分析

看到m只有3e4，可以考虑$m\sqrt{n}$的莫队算法，具体讲解。首先设f(l,r)表示从l到r满足x+y=k的对数，那么由容斥定理得到,$$f(l1,r1,l2,r2)=f(l1,r2)-f(l1,l2-1)-f(r1+1,r2)+f(r1+1,l2-1)$$,那么就可以结合莫队算法离线求出询问结果，具体见代码

trick

代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

const int N = 30030;

int n,k,m,len,ans;

int a[N],cnt[N],res[N];//cnt[i]记录i出现的次数，res[i]代表第i次询问的结果

struct node

{

    int l,r,id,block,f;

    node(){}

    node(int _l,int _r,int _id,int _f):l(_l),r(_r),id(_id),f(_f){block=l/len;}//左端点/块的大小

    bool operator<(const node &p)const

    {

        return block==p.block?r<p.r:block<p.block;//左端点先排序，右端点后排序

    }

}e[N<<2];

void insert(int loc)//插入，即向左/右扩展，先扩展后计算

{

    if(k-a[loc]>=1&&k-a[loc]<=n) ans+=cnt[k-a[loc]];

    cnt[a[loc]]++;

}

void erase(int loc)//删除，即向右/左收缩，先计算后收缩

{

    cnt[a[loc]]--;

    if(k-a[loc]>=1&&k-a[loc]<=n) ans-=cnt[k-a[loc]];

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        scanf("%d",&k);

        F(i,1,n) scanf("%d",a+i);

        scanf("%d",&m);

        int l1,r1,l2,r2;

        len=sqrt(n);//每块的大小

        R(i,0,m)

        {

            scanf("%d%d%d%d",&l1,&r1,&l2,&r2);

            e[i<<2]=node(l1,r2,i,1);

            e[(i<<2)+1]=node(l1,l2-1,i,-1);

            e[(i<<2)+2]=node(r1+1,r2,i,-1);

            e[(i<<2)+3]=node(r1+1,l2-1,i,1);

        }

        sort(e,e+(m<<2));

        ans=0;int l=1,r=0;

        mem(res,0);mem(cnt,0);

        //由第i个区间暴力求出第i+1个区间

        for(int i=0;i<(m<<2);++i)

        {

            while(r<e[i].r) insert(++r);

            while(l>e[i].l) insert(--l);

            while(r>e[i].r) erase(r--);

            while(l<e[i].l) erase(l++);

            res[e[i].id]+=ans*e[i].f;

        }

        R(i,0,m) printf("%d\n",res[i]);

    }

    return 0;

}

巴特西

HDU5213(容斥定理+莫队算法）

传送门

题意

分析

trick

代码

最新文章

热门文章