银老板的游戏

C++11(clang++ 3.9) 解法, 执行用时: 1054ms, 内存消耗: 9188K, 提交时间: 2019-11-23 09:53:43

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define low(x) (x&-(x))
using namespace std;

struct type{
	int x1,y1,x2,y2,s,id;
} a[100001],b[100001];
struct Type{
	int s,id;
} c[200001];
struct type1{
	int x,s,id;
} d[100001];
struct type2{
	int x,y,s,id,Id;
} D[100001];
int tr[200001];
int ans[200001];
int n,i,j,k,l,tp,tot,Tot,sum,len;

bool Cmp(Type a,Type b) {return a.s<b.s;}
bool cmp(type2 a,type2 b) {return a.x<b.x || a.x==b.x && a.id>b.id;}

void change(int t,int s)
{
	while (t<=200000)
	{
		tr[t]+=s;
		t+=low(t);
	}
}

void clear(int t)
{
	while (t<=200000)
	{
		tr[t]=0;
		t+=low(t);
	}
}

int find(int t)
{
	int ans=0;
	
	while (t)
	{
		ans+=tr[t];
		t-=low(t);
	}
	
	return ans;
}

void work1()
{
	int i;
	
	fo(i,1,n)
	if (d[i].s)
	change(d[i].x,d[i].s);
	else
	ans[d[i].id]-=find(d[i].x-1);
	
	memset(tr,0,sizeof(tr));
}

void work2(int l,int r)
{
	int i,mid=(l+r)/2;
	
	if (l==r) return;
	
	work2(l,mid);
	work2(mid+1,r);
	
	sort(D+l,D+r+1,cmp);
	
	fo(i,l,r)
	if (D[i].Id<=mid && D[i].s)
	change(D[i].y,D[i].s);
	else
	if (D[i].Id>mid && !D[i].s)
	ans[D[i].id]+=find(D[i].y-1);
	
	fo(i,l,r)
	if (D[i].Id<=mid && D[i].s)
	clear(D[i].y);
}

int main()
{
//	freopen("e.in","r",stdin);
	
	scanf("%d",&n);
	fo(i,1,n)
	{
		scanf("%d",&tp);
		
		switch (tp)
		{
			case 1:{
				scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
				
				++sum;
				a[i].s=1;
				b[++tot]=a[i];
				break;
			}
			case 2:{
				scanf("%d",&j);
				
				--sum;
				a[i]=b[j];
				a[i].s=-1;
				break;
			}
			case 3:{
				scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
				
				a[i].id=++Tot;
				ans[Tot]=sum;
				break;
			}
		}
	}
	
//	---
	
	len=0;
	fo(i,1,n)
	{
		c[++len]={a[i].x1,i};
		c[++len]={a[i].x2,-i};
	}
	sort(c+1,c+len+1,Cmp);
	j=0;
	fo(i,1,len)
	{
		j+=i==1 || c[i].s!=c[i-1].s;
		
		if (c[i].id>0)
		a[c[i].id].x1=j;
		else
		a[-c[i].id].x2=j;
	}
	
	len=0;
	fo(i,1,n)
	{
		c[++len]={a[i].y1,i};
		c[++len]={a[i].y2,-i};
	}
	sort(c+1,c+len+1,Cmp);
	j=0;
	fo(i,1,len)
	{
		j+=i==1 || c[i].s!=c[i-1].s;
		
		if (c[i].id>0)
		a[c[i].id].y1=j;
		else
		a[-c[i].id].y2=j;
	}
	
//	---
	
	fo(i,1,n)
	if (a[i].s)
	d[i]={a[i].x2,a[i].s,0};
	else
	d[i]={a[i].x1,0,a[i].id};
	work1();
	
	fo(i,1,n)
	if (a[i].s)
	d[i]={200001-a[i].x1,a[i].s,0};
	else
	d[i]={200001-a[i].x2,0,a[i].id};
	work1();
	
	fo(i,1,n)
	if (a[i].s)
	d[i]={a[i].y2,a[i].s,0};
	else
	d[i]={a[i].y1,0,a[i].id};
	work1();
	
	fo(i,1,n)
	if (a[i].s)
	d[i]={200001-a[i].y1,a[i].s,0};
	else
	d[i]={200001-a[i].y2,0,a[i].id};
	work1();
	
//	---
	
	fo(i,1,n)
	if (a[i].s)
	D[i]={a[i].x2,a[i].y2,a[i].s,0};
	else
	D[i]={a[i].x1,a[i].y1,0,a[i].id};
	fo(i,1,n)
	D[i].Id=i;
	work2(1,n);
	
	fo(i,1,n)
	if (a[i].s)
	D[i]={200001-a[i].x1,200001-a[i].y1,a[i].s,0};
	else
	D[i]={200001-a[i].x2,200001-a[i].y2,0,a[i].id};
	fo(i,1,n)
	D[i].Id=i;
	work2(1,n);
	
	fo(i,1,n)
	if (a[i].s)
	D[i]={a[i].x2,200001-a[i].y1,a[i].s,0};
	else
	D[i]={a[i].x1,200001-a[i].y2,0,a[i].id};
	fo(i,1,n)
	D[i].Id=i;
	work2(1,n);
	
	fo(i,1,n)
	if (a[i].s)
	D[i]={200001-a[i].x1,a[i].y2,a[i].s,0};
	else
	D[i]={200001-a[i].x2,a[i].y1,0,a[i].id};
	fo(i,1,n)
	D[i].Id=i;
	work2(1,n);
	
//	---
	
	fo(i,1,Tot)
	printf("%d\n",ans[i]);
}

C++14(g++5.4) 解法, 执行用时: 472ms, 内存消耗: 9988K, 提交时间: 2020-01-07 14:36:53

#include<bits/stdc++.h>
#define N 200010
#define lb lower_bound
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
using namespace std;
int lx[N],ly[N],ans[N],op[N],nx,ny,n;
struct rd{
    int a,b,c,op;
}w[N],tmp[N];
struct rec{
    int a,b,x,y;
    void read(){scc(a,b);scc(x,y);lx[++nx]=a,lx[++nx]=x,ly[++ny]=b,ly[++ny]=y;}
}G[N],T[N];

struct bit{
    int d[N];
    void up(int x,int y){for(;x<N;x+=x&-x) d[x]+=y; }
    inline int get(int x){int r=0; for(;x;x-=x&-x) r+=d[x]; return r; }
    void cls(){memset(d,0,sizeof d); }
}U,D,L,R;

void CDQ(int l,int r){
    if (l==r) return;
    int t=l+r>>1,x=l,y=t+1,k=l;
    CDQ(l,t);
    CDQ(t+1,r);
    while(x<=t && y<=r){
        if (w[x].b<=w[y].b){
            U.up(w[x].c,w[x].op);
            tmp[k++]=w[x++];
        } else {
            ans[w[y].a]+=U.get(w[y].c);
            tmp[k++]=w[y++];
        }
    }
    while(y<=r){
        ans[w[y].a]+=U.get(w[y].c);
        tmp[k++]=w[y++];
    }
    for (int i=l;i<x;i++) U.up(w[i].c,-w[i].op);
    while(x<=t) tmp[k++]=w[x++];
    for (int i=l;i<=r;i++) w[i]=tmp[i];
}

void solve(int f1,int f2){
    for(int i=1;i<=n;i++)
        if (op[i]!=3) w[i]=rd{i,f1?N-G[i].a:G[i].x,f2?N-G[i].b:G[i].y,op[i]==1?1:-1}; else
                      w[i]=rd{i,f1?N-G[i].x-1:G[i].a-1,f2?N-G[i].y-1:G[i].b-1,0};
    CDQ(1,n);
}

int main(){
    sc(n); int tt=0;
    for(int num=0,x,i=1;i<=n;i++){
        sc(op[i]);
        if (op[i]==1) num++;else
        if (op[i]==2) num--;else
        if (op[i]==3) ans[i]=num;
        if (op[i]!=2) G[i].read();
        else{
            sc(x);
            G[i]=T[x];
        }
        if (op[i]==1) T[++tt]=G[i];
    }

    sort(lx+1,lx+nx+1); sort(ly+1,ly+ny+1);
    nx=unique(lx+1,lx+nx+1)-lx-1, ny=unique(ly+1,ly+ny+1)-ly-1;
    for(int i=1;i<=n;i++)
        G[i].a=lb(lx+1,lx+nx+1,G[i].a)-lx+1,
        G[i].x=lb(lx+1,lx+nx+1,G[i].x)-lx+1,
        G[i].b=lb(ly+1,ly+ny+1,G[i].b)-ly+1,
        G[i].y=lb(ly+1,ly+ny+1,G[i].y)-ly+1;

    for(int i=1;i<=n;i++){
        int tg;
        if (op[i]==1) tg=1;else
        if (op[i]==2) tg=-1;
        if (op[i]!=3){
            L.up(G[i].x,tg);
            R.up(N-G[i].a,tg);
            U.up(N-G[i].b,tg);
            D.up(G[i].y,tg);
        }else{
            ans[i]-=L.get(G[i].a-1);
            ans[i]-=R.get(N-G[i].x-1);
            ans[i]-=U.get(N-G[i].y-1);
            ans[i]-=D.get(G[i].b-1);
        }
    }

    U.cls();
    solve(0,0);     // L D
    solve(0,1);     // L U
    solve(1,0);     // R D
    solve(1,1);     // R U
    for(int i=1;i<=n;i++) if (op[i]==3) printf("%d\n",ans[i]);
}

详情