题解 P4390 【[BOI2007]Mokia 摩基亚】

· · 题解

P4390 Mokia 摩基亚

主体思路：cdq分治

前置芝士：三维偏序，以及大家都会的一点点容斥技巧

代码效率：1527ms 个人认为是还不错的效率，毕竟没有刻意去卡常数qwq

因为并不是强制在线，所以不考虑常数较大的树套树和我并不会的K-D Tree做法。

对于每一个询问的矩阵（x1,y1）（x2,y2），考虑利用容斥小技巧把它拆成四个询问（0,0）（x2,y2）、（0,0）（x1-1,y1-1）以及（0,0）（x1-1,y2）、（0,0）（x2,y1-1），前者对答案做出正贡献而后者做出负贡献。

然后我们发现：诶，只有横坐标，纵坐标，以及出现时间三者都小于当前询问的才能对当前询问做出贡献！

这是……三维偏序的味道！

接下来，除了套模板，还有一点点需要注意的地方：

我们可以把这种情况特判掉，但特判好麻烦啊qwq

所以我们需要把所有坐标都+1，还有w也别忘了+1哦qwq，这样我们就完美避免了0的出现。

三维偏序的板子不去重应该会WA的很惨，但我们这里不用去重。

考虑我们的元素特点。对于修改操作，我们不需要记录答案，对于询问操作，它没有做出贡献。所以我们只需在第一次排序时保证所有询问操作在三维都相等的修改操作之后就可以保证所有修改的贡献都被统计。这可以通过修改cmp函数实现。

如果执意要去重，你会无从下手的qwq

更多的小细节，请看代码实现。

如果有帮助到你，记得点赞哦qwq

#include <stdio.h>
#include <algorithm>
using namespace std;
const int N=200010;
int w,cnt,qcnt,fcnt,ans[N],c[N];
struct Node{
    int x,y,ti,pos,opt,val; 
}node[N],temp[N];
/*
 pos是询问的位置
 opt是操作种类，等于0是修改，1和-1分别代表询问应该统计正贡献或负贡献。
 val是贡献 
*/ 
int read(){
    int x=0,w=1;char ch;ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*w;
}
bool cmp(const Node &a,const Node &b){
    if(a.x!=b.x) return a.x<b.x;
    if(a.y!=b.y) return a.y<b.y;
    if(a.ti!=b.ti) return a.ti<b.ti;//
    return a.val>b.val;//请注意这两行与三维偏序模板的不同之处qwq 
}
int lowbit(int x){
    return x&(-x);
}
void add(int x,int v){
    for(;x<=cnt;x+=lowbit(x))
     c[x]+=v;
}
int query(int x){
    int v=0;
    for(;x;x-=lowbit(x))//如果不+1这里就死了哦qwq 
     v+=c[x];
    return v;
}
void cdq(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r){
        if(node[i].y<=node[j].y){
            if(!node[i].opt)
             add(node[i].ti,node[i].val);
            temp[k++]=node[i++];
        }
        else{
            if(node[j].opt){
                int s=query(node[j].ti);
                ans[node[j].pos]+=s*node[j].opt;
            }
            temp[k++]=node[j++];
        }
    }
    while(j<=r){
        if(node[j].opt){
            int s=query(node[j].ti);
            ans[node[j].pos]+=s*node[j].opt;
        }
        temp[k++]=node[j++];
    }
    for(int o=l;o<i;o++)
     if(!node[o].opt)
      add(node[o].ti,-node[o].val);
    while(i<=mid)
     temp[k++]=node[i++];
    for(int i=l;i<=r;i++)
     node[i]=temp[i];
}
int main()
{
    int opt,x,y,xx,yy,num,t=0;
    read();w=read()+1;
    while(1){
        opt=read();
        if(opt==1){
            x=read()+1;y=read()+1;num=read();t++;
            node[++cnt]=Node{x,y,t,0,0,num};
        }
        else if(opt==2){
            x=read(),y=read();xx=read()+1,yy=read()+1;
            node[++cnt]=Node{xx,yy,t,++qcnt,1,0};
            node[++cnt]=Node{x,yy,t,qcnt,-1,0};
            node[++cnt]=Node{xx,y,t,qcnt,-1,0};
            node[++cnt]=Node{x,y,t,qcnt,1,0};
        }
        else break;
    }
    sort(node+1,node+cnt+1,cmp);
    cdq(1,cnt);
    for(int i=1;i<=qcnt;i++)
     printf("%d\n",ans[i]);
    return 0;
}

后记：我是时候该去认真学Markdown了QAQ