2019南京网赛 The beautiful values of the palace（思维，树状数组

https://nanti.jisuanke.com/t/41298

题意：给一个n * n的螺旋矩阵，n保证是奇数，取一些点使其、获得价值，价值为数位和，然后再给q次查询，求矩阵中的价值总和

思路：首先这题由点的位置求权值是一个思维点，可以先求出点位于哪一层螺旋中，然后将该层螺旋的起点数值获取，推出所求点数值。离散化地将每个点加入数组，用0和1标记是价值点还是询问点，四个询问点属于一个询问，然后将点按y,x,flag地顺序排序，ans = map[x2][y2]− map[x2][y1−1]− map[x1−1][y2]+ map[x1−1][y1−1]，将询问点的权值设为-1或1，就能实现上式的加或减。

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<stack>

#include<cstdlib>

#include<queue>

#include<set>

#include<string.h>

#include<vector>

#include<deque>

#include<map>

using namespace std;

#define INF 0x3f3f3f3f3f3f3f3f

#define inf 0x3f3f3f3f

#define eps 1e-4

#define bug printf("*********\n")

#define debug(x) cout<<#x"=["<<x<<"]" <<endl;

typedef long long LL;

typedef long long ll;

const int maxn = 1e6 + 5;

const int mod = 998244353;

struct node{

    int flag;

    LL x,y,id;

    LL val;

    friend bool operator < (node a,node b) {

        if(a.y == b.y) {

            if(a.x == b.x) return a.flag < b.flag;

            return a.x < b.x;

        }

        return a.y < b.y;

    }

}p[maxn];

LL re_val(LL x) {

    LL sum = 0;

    while(x > 0) {

        sum += x % 10;

        x /= 10;

    }

    return sum;

}

LL index(LL y,LL x,LL n) {  //求的n * n的矩阵中(x,y)的值是多少

    LL mid = (n + 1) / 2;

    LL p = max(abs(x - mid), abs(y - mid));

    LL ans = n * n - (1 + p) * p * 4;

    LL sx = mid + p, sy = mid + p;

    if (x == sx && y == sy)

        return ans;

    else {

        if (y == sy || x == sx - 2 * p)

            return ans + abs(x - sx) + abs(y - sy);

        else

            return ans + 8 * p - abs(x - sx) - abs(y - sy);

    }

}

LL c[maxn],ans[maxn];

void init() {

    memset(c,0,sizeof c);

    memset(ans,0,sizeof ans);

}

LL lowbit(LL x) {

    return x & -x;

}

LL sum(LL i) {

    LL res = 0;

    while(i) {

        res += c[i];

        i -= lowbit(i);

    }

    return res;

}

LL n;

void add(LL i,LL t) {

    while(i <= maxn) {

        c[i] += t;

        i += lowbit(i);

    }

}

int main() {

    int t;

    scanf("%d",&t);

    while(t--) {

        init();

        LL m,q;

        scanf("%lld %lld %lld",&n,&m,&q);

        int cnt = 0;

        for(int i = 1;i <= m; i++) {

            LL x,y;

            scanf("%lld %lld",&x,&y);

            p[++cnt] = {0, x, y, -1, re_val(index(x,y,n))};

        }

        for(int i = 1; i <= q; i++) {

            LL x1,y1,x2,y2;

            scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);

            p[++cnt] = {1, x1 - 1, y1 - 1, i, 1};

            p[++cnt] = {1, x1 - 1, y2, i, -1};

            p[++cnt] = {1, x2, y1 - 1, i, -1};

            p[++cnt] = {1, x2, y2, i, 1};

        }

        sort(p + 1, p + 1 + cnt);

        for(int i = 1; i <= cnt; i++) {

            if(p[i].flag == 1) ans[p[i].id] += sum(p[i].x) * p[i].val;

            else add(p[i].x,p[i].val);

        }

        for(int i = 1; i <= q; i++)

            printf("%lld\n",ans[i]);

    }

}

巴特西

2019南京网赛 The beautiful values of the palace（思维，树状数组

最新文章

热门文章