P4390 [BOI2007]Mokia 摩基亚

传送门

对于一个询问 $(xa,ya),(xb,yb)$，拆成 $4$ 个询问并容斥一下

具体就是把询问变成求小于等于 $xb,yb$ 的点数，减去小于等于 $xa-1,yb$ 和小于等于 $xb,ya-1$ 的点数，再加上小于等于 $xa-1,ya-1$ 的点数

就变成求二维前缀和的问题了

然后再加上时间维，发现其实就是对每个询问，求时间更早的，横纵坐标都小于询问点的点的数量

变成裸的三维偏序问题了， $CDQ$ 分治就行

注意 $long\ long$

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=1e6+,M=2e6+;

struct dat{

    int x,y,id,v;

}d[N],tmp[N];

int W,tot,m;

ll ans[N],t[M];

inline void add(int x,int v) { while(x<=W) t[x]+=v,x+=x&-x; }

inline ll ask(int x) { ll res=; while(x) res+=t[x],x-=x&-x; return res; }

inline bool fc(dat a,dat b) { if(a.x!=b.x) return a.x<b.x; return a.y!=b.y ? a.y<b.y : a.id<b.id; }

void CDQ(int l,int r)

{

    if(l==r) return; int mid=l+r>>;

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

    int i=l,j=mid+,p=l-;

    while(i<=mid&&j<=r)

    {

        if(fc(d[i],d[j]))

        {

            if(!d[i].id) add(d[i].y,d[i].v);

            tmp[++p]=d[i++];

            continue;

        }

        if(d[j].id) ans[d[j].id]+=d[j].v*ask(d[j].y);

        tmp[++p]=d[j++];

    }

    while(i<=mid) { if(!d[i].id) add(d[i].y,d[i].v); tmp[++p]=d[i++]; }

    while(j<=r) { if(d[j].id) ans[d[j].id]+=d[j].v*ask(d[j].y); tmp[++p]=d[j++]; }

    for(int k=l;k<=mid;k++) if(!d[k].id) add(d[k].y,-d[k].v);

    for(int k=l;k<=r;k++) d[k]=tmp[k];

}

int main()

{

    int opt,xa,xb,ya,yb;

    opt=read(),W=read();

    while()

    {

        opt=read();

        if(opt==) d[++tot].x=read(),d[tot].y=read(),d[tot].v=read();

        if(opt==)

        {

            m++;

            xa=read()-,ya=read()-,xb=read(),yb=read();

            d[++tot]=(dat){xa,ya,m,};

            d[++tot]=(dat){xa,yb,m,-};

            d[++tot]=(dat){xb,ya,m,-};

            d[++tot]=(dat){xb,yb,m,};

        }

        if(opt==) break;

    }

    CDQ(,tot);

    for(int i=;i<=m;i++) printf("%lld\n",ans[i]);

    return ;

}