icontofig | 发布于 2019-09-02 23:23:58 | 阅读量 654 | 思维题 扫描线 树状数组
发布于 2019-09-02 23:23:58 | 思维题 扫描线 树状数组

题目大意

每个点的数值是通过一个从中心最大值开始的蛇形矩阵确定的。其中有m个点上的权值可用,对于q个询问,输出左下角为(x1,y1),右上角为(x2,y2)的矩阵区域内所有可用点的权值经过处理后的和。

处理的方法是,将原权值所有数位上的数相加。

题解

此题估计是模仿NOIP2014普及组T3的蛇形矩阵出的规律题目。

首先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));

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cal(int x, int y, int n){
    int layer = min(min(x, y), n - max(x, y) + 1);
    if ((layer << 1) > n){
        return 1LL * n * n;
    }
    long long st = 1LL * n * n - 1LL * (n - (layer << 1) + 2) * (n - (layer << 1) + 2) + 1;
    if (x >= y){
        return st + ((n - layer) << 1) + 2 - x - y;
    }
    return st + ((n - (layer << 1) + 1) << 1) + x + y - (layer << 1);
}
const int maxn = 1e6+5;
const int maxm = 1e5 + 5;
struct quest{
    int x,y;
    int flag;
    int id;
}e[maxm<<3];
int ans[maxm];
int res[maxn];
int lowbit(int x){
    return (x & -x);
}
void update(int pos,int d){
    while(pos < maxn){
        res[pos] += d;
        pos += lowbit(pos);
    }
    return;
}
int query(int pos){
    int ret = 0;
    while(pos){
        ret += res[pos];
        pos -= lowbit(pos);
    }
    return ret;
}
struct point{
    int x,y;
    int ans;
}p[maxm];
bool cmp(quest a,quest b){
    return (a.x < b.x) || (a.x == b.x && a.y < b.y) || (a.x == b.x && a.y == b.y && a.flag > b.flag);
}
int t;
int n,m,q;
int work(ll x){
    int ret = 0;
    while(x){
        ret += x % 10;
        x /= 10;
    }
    return ret;
}
int x,y,xx,yy;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--){
        memset(res,0,sizeof(res));
        cin >> n >> m >> q;
        for(int i = 1;i <= m;++i){
            cin >> p[i].x >> p[i].y;
            ll pk = cal(p[i].x,p[i].y,n);
            p[i].ans = work(pk);
            e[4*q + i].x = p[i].x;
            e[4*q + i].y = p[i].y;
            e[4*q+i].id = q+i;
            e[4*q+i].flag = 2;
        }
        int cnt = 4*q + m;
        for(int i = 1;i <= q;++i){
            cin >> x >> y >> xx >> yy;
            e[4*(i-1) + 1].x = x-1;e[4*(i-1)+1].y = y-1;e[4*(i-1)+1].id = i;e[4*(i-1)+1].flag = 1;
            e[4*(i-1) + 2].x = xx;e[4*(i-1)+2].y = yy;e[4*(i-1)+2].id = i;e[4*(i-1)+2].flag = 1;
            e[4*(i-1) + 3].x = x-1;e[4*(i-1)+3].y = yy;e[4*(i-1)+3].id = i;e[4*(i-1)+3].flag = -1;
            e[4*(i-1) + 4].x = xx;e[4*(i-1)+4].y = y-1;e[4*(i-1)+4].id = i;e[4*(i-1)+4].flag = -1;
        }
        sort(e+1,e+cnt+1,cmp);
        for(int i = 1;i <= q;++i)
            ans[i] = 0;
        for(int i = 1;i <= cnt;++i){
            if(e[i].flag == 2){
                int now = e[i].id - q;
                update(e[i].y,p[now].ans);
            }
            else{
                ans[e[i].id] += e[i].flag * query(e[i].y);
            }
        }
        for(int i = 1;i <= q;++i){
            cout << ans[i] << "\n";
        }
    }
    return 0;
}



内容更新于: 2019-09-02 23:24:01
链接地址: http://blog.leanote.com/post/icontofig/2019

上一篇: 2018 ACM/ICPC Xuzhou Regional G.Rikka with Intersections of Paths 树上差分+LCA

下一篇: 2018 ICPC 徐州赛站网络赛 B.BE,GE or NE 博弈论+记忆化搜索

654 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航