2019 icpc南京赛区网络赛A题题解

题目链接：https://nanti.jisuanke.com/t/41298

思路：好困，先睡了，AC代码先贴上。思路明天补辽QAQ。
差点忘了，俺来补思路辽。
思路:一开始看到这个题目想的是想办法快速求一下每个坐标对应的值，然后离散化+二维树状数组之类的求二维前缀和，后来发现这个题目即使离散化了，也要开1e5*1e5的数组来存储，显然这个大小内存是开不下的。所以我们就只能试着用一维的方式来解决，二维降维到一维很容易让人想到cdq分治这样的方法，但是因为只是二维，我就想着试着给他们的x排序一下然后来试着再y那一维解决可不可以，推容斥式子时发现恰好是加上两个值减去两个值，这样就相当于把之前x的所有和加上两次再减去两次，所以最终答案是正确不变的，总体来说就是这样的思路。
这题找每个坐标对应的数值我想了好久QAQ，太菜了我。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+50;
typedef long long ll;

struct node
{
	int x,y,rec,id;
	//rec是标记，id是值或者答案标号 
}po[maxn];
bool comp(node a,node b)
{
	if(a.x!=b.x) return a.x<b.x;
	if(a.y!=b.y) return a.y<b.y;
	if(a.rec!=b.rec) return a.rec>b.rec;
}

int N;
int lowbit(int x)
{
	return x&(-x);
}
ll tre[maxn];
void add(int pos,int val)
{
	while(pos<=N)
	{
		tre[pos]+=val;
		pos+=lowbit(pos);
	}
	return ;
}

ll ask(int pos)
{
	ll ans=0;
	while(pos>0)
	{
//		cout<<pos<<"--"<<endl;
		ans+=tre[pos];
		pos-=lowbit(pos);
	}
//	cout<<ans<<"....."<<endl;
	return ans;
}

int value(int x, int y, int n) 
{
    int w=min(min(x-1,y-1),min(n-x,n-y));
    ll v=2LL*(n-1+n-1-2*(w-1))*w;
    n-=w*2;
    x-=w;
    y-=w;
    if(x==n&&y>1) v+=1LL*(n-y+1);
    else if(y==1&&x>1) v+=1LL*(n-1+n-x+1);
    else if(x==1&&y<n) v+=1LL*(2*(n-1)+y);
    else v+=1LL*(3*(n-1)+x);
    int tot=0;
    while(v)
    {
    	tot+=v%10;
    	v=v/10;
	}
    return tot;
}


int t;
int n,m,q;
ll fin[maxn];
int num;
void init()
{
	for(int i=0;i<=n;i++) tre[i]=0;
	N=n;
	num=0;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&n,&m,&q);
		init();
		for(int i=1;i<=m;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			po[++num].x=a;po[num].y=b;
			po[num].rec=233;po[num].id=value(a,b,n);
		}
//		cout<<"=="<<endl;
		//num的最终值就是城堡的个数
	//	sort(po+1,po+1+num,comp); 
		for(int i=1;i<=q;i++)
		{
			int a,b,c,d;
			scanf("%d%d%d%d",&a,&b,&c,&d);
			po[++num].x=c;po[num].y=d;po[num].rec=1;po[num].id=i;
			po[++num].x=a-1;po[num].y=b-1;po[num].rec=1;po[num].id=i;
			po[++num].x=a-1;po[num].y=d;po[num].rec=-1;po[num].id=i;
			po[++num].x=c;po[num].y=b-1;po[num].rec=-1;po[num].id=i; 
			fin[i]=0;	
		}
	//	cout<<"=="<<endl;
		sort(po+1,po+1+num,comp);
	//	cout<<"=="<<endl;
		for(int i=1;i<=num;i++)
		{
			if(po[i].rec==233) add(po[i].y,po[i].id);
			else
			{
				fin[po[i].id]+=1LL*ask(po[i].y)*po[i].rec;
			}
		}
		for(int i=1;i<=q;i++)
		{
			printf("%lld\n",fin[i]);
		}
	}
	return 0;
}