洛谷P4390 [BOI2007]Mokia 摩基亚 题解

题目链接：P4390 [BOI2007]Mokia 摩基亚

题意：摩尔瓦多的移动电话公司摩基亚（Mokia）设计出了一种新的用户定位系统。和其他的定位系统一样，它能够迅速回答任何形如“用户 C 的位置在哪？”的问题，精确到毫米。但其真正高科技之处在于，它能够回答形如“给定区域内有多少名用户？”的问题。

在定位系统中，世界被认为是一个 $w×w$ 的正方形区域，由 $1\times 1$ 的方格组成。每个方格都有一个坐标 $(x,y)$，$1\leq x,y\leq w$。坐标的编号从 $1$ 开始。对于一个 $4\times 4$ 的正方形，就有 $1\leq x\leq 4$，$1\leq y\leq 4$（如图）：

请帮助 Mokia 公司编写一个程序来计算在某个矩形区域内有多少名用户。

这道题的题解区一片互相抄袭的烂货，实在受不了了就来水一篇题解

可以发现这道题目就是个二维数点问题，不知道的推荐看看 这篇博客

然后这道题目，我们不能用归并排序来做

为什么呢？因为这个题目它还有一个维度：时间顺序

因此我们可以使用CDQ分治（第一维是时间，第二维是 $x$ ，第三维是 $y$ ）

这里我们甚至不用按时间排序，它本来就是顺序的

注意到 $w\le 2\times 10^6$ ，有一丢丢大，所以可以不必要地离散化一下 $y$

因此时间复杂度 $O(n\log^2 n)$

然后就跑到了最优解第一页，嘿嘿树状数组跑的飞快🤤（逃~

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() getchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
#define lb lower_bound
char buf1[SIZ],*p1,*p2;
char readchar()
{
    if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
    return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){pc('-');k=-k;}
    static T stk[66];T top=0;
    do{stk[top++]=k%10,k/=10;}while(k);
    while(top){pc(stk[--top]+'0');}
}
#define N (int)(2e6+15)
struct node
{
    int x,y,typ,add,id,ans;
}t[N],b[N];
int w,n,Q,pos,tcnt;
int tree[N],ans[N],tmp[N];
void addQ(int a,int b,int c,int d=0,int e=0)
{
    t[++pos]={a,b,c,d,e};
}
#define lowbit(x) (x&(-x))
void add(int x,int v)
{
    while(x&&x<=n)
    {
        tree[x]+=v;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int res=0;
    while(x>=1)
    {
        res+=tree[x];
        x-=lowbit(x);
    }
    return res;
}
void init()
{
    for(int i=1; i<=pos; i++)
        tmp[i]=t[i].y;
    sort(tmp+1,tmp+1+pos);
    n=unique(tmp+1,tmp+1+pos)-tmp-1;
    for(int i=1; i<=pos; i++)
        t[i].y=lb(tmp+1,tmp+1+n,t[i].y)-tmp;
}
void cdq(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    int i=mid+1,j=l,cnt=0;
    for(;i<=r; i++)
    {
        while(t[j].x<=t[i].x&&j<=mid)
        {
            if(t[j].typ==1)add(t[j].y,t[j].add);
            b[++cnt]=t[j++];
        }
        if(t[i].typ==2)t[i].ans+=sum(t[i].y);
        b[++cnt]=t[i];
    }
    for(int i=l; i<j; i++)
        if(t[i].typ==1)add(t[i].y,-t[i].add);
    while(j<=mid)
        b[++cnt]=t[j++];
    for(int i=1; i<=cnt; i++)
        t[l+i-1]=b[i];
}
signed main()
{
    read(w);read(w);
    int op;
    while(read(op),op!=3)
    {
        int a,b,c,d;
        if(op==1)
        {
            read(a);read(b);read(c);
            addQ(a,b,1,c);
        }else if(op==2)
        {
            read(a);read(b);read(c);read(d);++Q;
            addQ(c,d,2,1,Q);
            addQ(a-1,d,2,-1,Q);
            addQ(c,b-1,2,-1,Q);
            addQ(a-1,b-1,2,1,Q);
        }
    }
    init();
    cdq(1,pos);
    for(int i=1; i<=pos; i++)
    {
        if(t[i].typ==2)
            ans[t[i].id]+=t[i].add*t[i].ans;
    }
    for(int i=1; i<=Q; i++)
        write(ans[i]),pc('\n');
    return 0;
}

这里还有非离散化版本的

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define gc() getchar()
#define pc(a) putchar(a)
#define SIZ (int)(1e5+15)
#define lb lower_bound
char buf1[SIZ],*p1,*p2;
char readchar()
{
    if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
    return p1==p2?EOF:*p1++;
}
template<typename T>void read(T &k)
{
    char ch=gc();T x=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
    k=x*f;
}
template<typename T>void write(T k)
{
    if(k<0){pc('-');k=-k;}
    static T stk[66];T top=0;
    do{stk[top++]=k%10,k/=10;}while(k);
    while(top){pc(stk[--top]+'0');}
}
#define N (int)(2e6+15)
struct node
{
    int x,y,typ,add,id,ans;
}t[N],b[N];
int w,n,Q,pos,tcnt;
int tree[N],ans[N],tmp[N];
void addQ(int a,int b,int c,int d=0,int e=0)
{
    t[++pos]={a,b,c,d,e};
}
#define lowbit(x) (x&(-x))
void add(int x,int v)
{
    while(x&&x<=w)
    {
        tree[x]+=v;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    int res=0;
    while(x>=1)
    {
        res+=tree[x];
        x-=lowbit(x);
    }
    return res;
}
void cdq(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    int i=mid+1,j=l,cnt=0;
    for(;i<=r; i++)
    {
        while(t[j].x<=t[i].x&&j<=mid)
        {
            if(t[j].typ==1)add(t[j].y,t[j].add);
            b[++cnt]=t[j++];
        }
        if(t[i].typ==2)t[i].ans+=sum(t[i].y);
        b[++cnt]=t[i];
    }
    for(int i=l; i<j; i++)
        if(t[i].typ==1)add(t[i].y,-t[i].add);
    while(j<=mid)
        b[++cnt]=t[j++];
    for(int i=1; i<=cnt; i++)
        t[l+i-1]=b[i];
}
signed main()
{
    read(w);read(w);
    int op;
    while(read(op),op!=3)
    {
        int a,b,c,d;
        if(op==1)
        {
            read(a);read(b);read(c);
            addQ(a,b,1,c);
        }else if(op==2)
        {
            read(a);read(b);read(c);read(d);++Q;
            addQ(c,d,2,1,Q);
            addQ(a-1,d,2,-1,Q);
            addQ(c,b-1,2,-1,Q);
            addQ(a-1,b-1,2,1,Q);
        }
    }
    cdq(1,pos);
    for(int i=1; i<=pos; i++)
    {
        if(t[i].typ==2)
            ans[t[i].id]+=t[i].add*t[i].ans;
    }
    for(int i=1; i<=Q; i++)
        write(ans[i]),pc('\n');
    return 0;
}