P2184 【贪婪大陆】

看到全是线段树或者树状数组写法，就来提供一发全网唯一cdq分治三维偏序解法吧

容易发现，这个题的查询就是对于每个区间l,r，查询有多少个修改区间l_i,r_i与l,r有交集

转化为数学语言，就是查询满足l_i<=r且r_i>=l的修改个数

一个二维偏序问题，但是我们发现，这是个动态插入的二维偏序问题

_(:з」∠)_一时不知所措

再想一想，不妨把时间另开一个维度作为第三维，然后就是这样了

对于每个查询，我们要求出它之前有多少个修改区间与其相交

数学语言：

查询满足l_i<=r且r_i>=l且[l_i,r_i].time<[l,r].time的修改个数

思路清晰明了，而且敲好想，但是实现细节还是比较麻烦的（一部分是因为我的奇葩cdq写法），在代码注释里解释一下（模板这种的就不解释了）

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

const int maxn=1e5+;

struct node{

    int a,b,c,q,w;

//a,b,c表示三个维度，q记录这个操作是修改还是查询

//w表示这个是否有效（和q差不多，查询是不需要统计的，w=0；修改的w=1）

}v[maxn];

int n,m,cnt,tot,c[maxn],ans[maxn];

bool vis[maxn];

bool cmpx(const node &a,const node &b)

{

    return a.a==b.a?(a.b==b.b?a.c<b.c:a.b<b.b):a.a<b.a;

}

bool cmpy(const node &a,const node &b)

{

    return a.b==b.b?a.c<b.c:a.b<b.b;

}

int lowbit(int x)

{

    return x&-x;

}

void add(int x,int ch)

{

    while(x<=n)

    {

        c[x]+=ch;

        x+=lowbit(x);

    }

}

int sum(int x)

{

    int ret=;

    while(x)

    {

        ret+=c[x];

        x-=lowbit(x);

    }

    return ret;

}

void cdq(int l,int r)

{

    if(l==r)

        return;

    int mid=l+r>>;

    cdq(l,mid),cdq(mid+,r);

    sort(v+l,v+mid+,cmpy),sort(v+mid+,v+r+,cmpy);

    int i=l,j=mid+;

    for(;j<=r;j++)

    {

        while(v[i].b<=v[j].b&&i<=mid)

            add(v[i].c,v[i].w),i++;

        if(v[j].q==)

            ans[v[j].a]+=sum(n)-sum(v[j].c-);

            //统计贡献到ans数组中

    }

    for(j=l;j<i;j++)

        add(v[j].c,-v[j].w);

}

int main()

{

    scanf("%d%d",&n,&m);

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

    {

        scanf("%d%d%d",&v[i].q,&v[i].b,&v[i].c);

        v[i].w=;

        if(v[i].q==)

            swap(v[i].b,v[i].c),v[i].w=,vis[i]=;

            //标记每个操作是否需要输出

        v[i].a=i;

    }

    cdq(,m);

    //枚举每个操作，需要输出就输出

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

        if(vis[i])

            printf("%d\n",ans[i]);

    return ;

}

巴特西

P2184 【贪婪大陆】

最新文章

热门文章