【题解】【老C的任务】

题目内容

Solution

对于每个询问可以拆分成4个前缀矩形的求和，容易发现，前缀矩形的求和相当于是求一个二维偏序，可以用树状数组或cdq分治在nlogn的复杂度内完成。

Code

#include
using namespace std;
#define int long long
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);
}//Make sure that the left won't make a difference to the right
//If it is true,there is no need to unique 
const int N=1e5+100;
int n,m,ans[N];
struct node{
	int x,y,z,p,sum,id,tag;
	bool operator<(const node& g)const
	{
		if(x^g.x) return x>1;
	cdq(l,mid);
	cdq(mid+1,r);
	int sum=0,pos=l;
	for(int i=mid+1;i<=r;++i)
	{
		while(pos<=mid&&a[pos].y<=a[i].y) sum+=a[pos].p,pos++;
		a[i].sum+=sum;
	}
	int p=l,q=mid+1;
	for(int i=l;i<=r;++i)
	  if(p>mid) tmp[i]=a[q++];
	  else if(q>r) tmp[i]=a[p++];
	  else tmp[i]=a[a[p].y