【bzoj2683】簡單題 CDQ分治+樹狀數組

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2683

【題解】

話說這題好像可以用整體二分來做（蒟蒻不會啊），CDCQ大神的整體二分比我的CDQ分治高到不知道哪裡去了。

說一下做法吧：

首先把詢問的矩形分成4部分，算一下每部分的答案，然後容斥原理即可。

怎樣算每部分的答案呢？

我們按照時間分治，CDQ遞歸過程中按x排序，遇到修改則插入到樹狀數組中，遇到詢問就在bit中查詢即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
#define FILE "read"
#define MAXN 800010
#define up(i,j,n) for(int i=j;i<=n;++i)
#define dn(i,j,n) for(int i=j;i>=n;--i)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
struct node{
	ll x,y,v,id,opt;
	bool operator <(const node &b)const{return id<b.id;}
}a[MAXN],stack[MAXN];
int n,m,tr[500010];
namespace INIT{
	char buf[1<<15],*fs,*ft;
	inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,f=1;  char ch=getc();
		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
		return x*f;
	}
}using namespace INIT;
void add(int x,int v){while(x<=n)tr[x]+=v,x+=(x&-x);}
ll get(int x){int sum(0);while(x)sum+=tr[x],x-=(x&-x);return sum;}
void CDQ(int l,int r){
	if(l>=r)  return;
	int mid=(l+r)>>1,ta(l),tb(mid+1),top(0);
	CDQ(l,mid);  CDQ(mid+1,r);
	while(ta<=mid&&tb<=r){
		while(ta<=mid&&a[ta].x<=a[tb].x){
			if(a[ta].opt==1) add(a[ta].y,a[ta].v);
			stack[++top]=a[ta++];
		}
		while(tb<=r&&a[ta].x>a[tb].x){
			if(a[tb].opt==2) a[tb].v+=get(a[tb].y);
			stack[++top]=a[tb++];
		}
	}
	while(ta<=mid){
		if(a[ta].opt==1)  add(a[ta].y,a[ta].v);
		stack[++top]=a[ta++];
	}
	while(tb<=r){
		if(a[tb].opt==2)  a[tb].v+=get(a[tb].y);
		stack[++top]=a[tb++];
	}
	up(i,l,mid)  if(a[i].opt==1)  add(a[i].y,-a[i].v);
	up(i,l,r)  a[i]=stack[i-l+1];
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();
	while(1){
		int opt=read();  
		if(opt==1){
			int x=read(),y=read(),v=read();
			a[++m]=(node){x,y,v,m,opt};
		}
		else if(opt==2){
			int x1=read(),y1=read(),x2=read(),y2=read();
			int X1=min(x1,x2),Y1=min(y1,y2),X2=max(x1,x2),Y2=max(y1,y2);
			a[++m]=(node){X1-1,Y1-1,0,m,opt};
			a[++m]=(node){X1-1,Y2,0,m,opt};
			a[++m]=(node){X2,Y1-1,0,m,opt};
			a[++m]=(node){X2,Y2,0,m,opt};
		}
		else break;
	}
	CDQ(1,m);  sort(a+1,a+m+1);
	up(i,1,m)if(a[i].opt==2)printf("%lld\n",(ll)a[i+3].v-a[i+2].v-a[i+1].v+a[i].v),i+=3;
	return 0;
}