The beautiful values of the palace（思维+离散化+二维树状数组维护）

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

Here is a square matrix of

The grid in the lower left corner is (1,1) and the grid in the upper right corner is (n , n)

Now I can choose

Next, we ask $grid(x_1,y_1x1,y1), the upper right square (x_2,y_2x2,y2).$

Input

The first line has only one number

The next line is three number:

The

The $(x_1,y_1)(x1,y1) the upper right square (x_2,y_2)(x2,y2)$

Output

Next, $p_1+p_2...+p_Tp1+p2...+pT lines: Represent the answer in turn(n le 10^6)(m , p le 10^5)(n≤106)(m,p≤105)$

样例输入

样例输出

5
18
23
17
思路：首先得求出每个位置对应的值出来，O(1）的复杂度，这是做这道题的前提，然后点的个数太多了，有1e6，所以开不了那么大的数组，比赛的时候用了map，疯狂超时
猜想超时的原因应该就是用了map，map复杂度是log(N) ，正确做法是：扫描线的思想，按x从小到大排序，当x相等时，优先插入点，而不是插入矩形。
题解是这么说的：

首先n为奇数，n*n为奇数，地图大小为一定为奇数，所以

x = x − n/2 − 1
y = y - n /2 - 1；
t = max(abs(x),abs(y))； //确定该点在第几圈螺旋
if(x >= y)ans = n ∗ n −4∗ t ∗ t −2∗ t − x − y;//在向右与向上的路线上

else ans = n ∗ n −4∗ t ∗ t +2∗ t + x + y;//在向左与向下的路线上

这样我们就可以O(m)的预处理所有的可用点的权值了。

对于每一次询问，都是一个矩形区域。

我们考虑二维前缀和，其答案相当于ans(x2,y2) - ans(x2,y1-1) - ans(x1-1,y2) + ans(x-1,y-1)，其中ans(x,y)代表1——x，1——y矩形区域中所有值的和。

但是二维显然会爆空间，所以我们考虑如何降维。

我们可以将一个询问拆解成4个，用flag为1或-1标记此次询问的前缀和是要加还是减。

之后我们可以运用扫描线的方法，先按照x排序，然后对y进行映射，用树状数组维护映射后y上的值。用一条竖直的扫描线不断向右扫，遇到一个询问点就查询一次。

但是这样我们使用扫描线是要将所有的点当作修改操作的，而不能提前加入树状数组，否则答案会出问题。

所以我们将所有的m个点和4*q个询问加入操作合集，查询flag为-1或1，修改flag为2，按照先x、次先y、再次先修改的顺序排序，用一条平行于y轴的线从左向右扫过整个横坐标区间，用树状数组维护当前投影到y轴上的值。每当遇到修改操作，直接update树状数组中的值进行维护，遇到查询操作直接从树状数组中查询。

理论时间复杂度为O((m+4*q)log(m+4*q))；

看代码：

/**
x=x-n/2-1
y=y-n/2-1
t=max(abs(x),abs(y));
if(x>=y) ans=n*n-4*t*t-2*t-x-y;
else ans=n*n-4*t*t+2*t+x+y
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=5e6+5;
typedef long long LL;
int ly[maxn];
int c[maxn];
int Ans[maxn];
int len;
struct Node
{
    int x,y,v,flag,id;
}node[maxn<<2];
bool cmp(const Node a,const Node b)
{
    if(a.x==b.x)
    {
        return a.flag>b.flag;
    }
    return a.x<b.x;
}
LL cal(int x,int y,LL n)
{
    LL ans;
    LL sum=0;
    x=x-n/2-1;
    y=y-n/2-1;
    LL t=max(abs(x),abs(y));
    if(x>=y) ans=n*n-4*t*t-2*t-x-y;
    else ans=n*n-4*t*t+2*t+x+y;
    while(ans)
    {
        sum+=ans%10;
        ans/=10;
    }
    return sum;
}
int getid(int x)
{
    return lower_bound(ly+1,ly+1+len,x)-(ly);
}
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int v)
{
    while(x<=len)
    {
        c[x]+=v;
        x+=lowbit(x);
    }
}
LL Query(LL x)
{
    LL sum=0;
    while(x)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        memset(c,0,sizeof(c));memset(Ans,0,sizeof(Ans));
        LL N,M,Q;scanf("%lld%lld%lld",&N,&M,&Q);
        int p=0,p1=0;
        for(int i=1;i<=M;i++)
        {
            int x,y;scanf("%d%d",&x,&y);
            ly[++p1]=y;//存所有的y
            node[++p].x=x;node[p].y=y;node[p].v=cal(x,y,N);node[p].flag=2;//flag代表是点 而不是矩形
        }
        for(int i=1;i<=Q;i++)
        {
            int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            ly[++p1]=y1-1;ly[++p1]=y2;
            node[++p].x=x1-1;node[p].y=y1-1;node[p].flag=1;node[p].id=i;  //代表要加的
            node[++p].x=x1-1;node[p].y=y2;node[p].flag=-1;node[p].id=i;//代表要减的
            node[++p].x=x2;node[p].y=y2;node[p].flag=1;node[p].id=i;  //代表要加的
            node[++p].x=x2;node[p].y=y1-1;node[p].flag=-1;node[p].id=i;//代表要减的
        }
        sort(node+1,node+p+1,cmp);
        sort(ly+1,ly+1+p1);
        len=unique(ly+1,ly+1+p1)-(ly+1);
        for(int i=1;i<=p;i++)//遍历所有的点
        {
            int x=getid(node[i].y);
            if(node[i].flag==2)//代表是个点 直接更新就行
            {
                add(x,node[i].v);
            }
            else Ans[node[i].id]+=node[i].flag*Query(x);
        }
        for(int i=1;i<=Q;i++)
        {
            printf("%d
",Ans[i]);
        }
    }
    return 0;
}

当初的梦想实现了吗，事到如今只好放弃吗~