【cdq分治】【模板】

Problem

三维偏序的模板题。

Solution：

经典做法是，先排序控制一维，再用cdq分治控制一维，最后用数据结构（通常是树状数组）维护一维。

cdq分治还可以嵌套，每嵌套一次，复杂度乘一个log，可以拓展到n维偏序（但超过3维，效率就很低了，通常会使用kd-tree），因此，这题也可以用两个cdq分治嵌套解决（但我不会）

复杂度O(n log^2 n),cdq分治和树状数组各提供一个log

需要注意的问题：

在cdq分治的外层排序中，必须要满足在cdq内部划分时，右半区间不能对左半区间造成影响，因此，当两个元素完全相同时，需要把他们合成一个元素，最后再累计相同元素的贡献，而且要按照三关键字排序

Code

#include
using namespace std;

inline int read()
{
	register int x=0,w=1;
	register char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') {ch=getchar();w=-1;}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*w;
}
inline void write(int x)
{
	if(x<0) {putchar('-');x=~(x-1);}
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const int N=1e5+100;
int n,k;
struct node{
	int a,b,c,s,ans;
	bool operator<(const node&x)const{
	     if(a!=x.a) return a>1;
	cdq(l,mid);cdq(mid+1,r);
	sort(a+l,a+mid+1,cmp);sort(a+mid+1,a+r+1,cmp);
	int pos=l;
	for(int i=mid+1;i<=r;++i)
	{
		while(pos<=mid&&a[pos].b<=a[i].b) {
			add(a[pos].c,a[pos].s);pos++;
		}
		a[i].ans+=ask(a[i].c);
	}
	for(int i=l;i

#include
using namespace std;

inline int read()
{
	register int x=0,w=1;
	register char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-') {ch=getchar();w=-1;}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*w;
}
inline void write(int x)
{
	if(x<0) {putchar('-');x=~(x-1);}
	if(x>9) write(x/10);
	putchar('0'+x%10);
}
const int N=1e5+100;
int n,k;
struct node{
	int a,b,c,s,ans;
	bool operator<(const node&x)const{
	     if(a!=x.a) return a>1;
	cdq(l,mid);cdq(mid+1,r);
//	sort(a+l,a+mid+1,cmp);sort(a+mid+1,a+r+1,cmp);
	int pos=l;
	for(int i=mid+1;i<=r;++i)
	{
		while(pos<=mid&&a[pos].b<=a[i].b) {
			add(a[pos].c,a[pos].s);pos++;
		}
		a[i].ans+=ask(a[i].c);
	}
	for(int i=l;imid)
		tmp[++pos]=a[q++];
		else if(q>r) tmp[++pos]=a[p++];
		else tmp[++pos]=a[a[p].b