The Preliminary Contest for ICPC Asia Nanjing 2019

2题

A The beautiful values of the palace

根据规律算出当前坐标对应的值,询问子矩阵内值的和可以搞个二维前缀和,可是$n$太大了,开不了这么大的矩阵,那什么可以查询$x$在$[x1,x2]$之间,$y$在$[y1,y2]$之间的所有$(x,y)$对应值之和呢? 主席树!

我这个利用规律找值写得比较丑陋hhh

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 1e6 + 10;
const int M = 1e5 + 10;
int n, m, p, tot;
ll s[N];
vector<P> g[M];
int count(ll x)
{
    int sum = 0;
    while (x)
    {
        sum += x % 10;
        x /= 10;
    }
    return sum;
}
struct node{
    int x, y, v;
}a[N];
struct tree{
    int  lc, rc;
    int cnt;
}T[M << 5];
int X[N], tot1;
int root[N];
void update(int &cur, int pre, int pos, int v, int l, int r)
{
    cur = ++tot;
    T[cur] = T[pre];
    T[cur].cnt += v;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) update(T[cur].lc, T[pre].lc, pos, v, l, mid);
    else update(T[cur].rc, T[pre].rc, pos, v, mid + 1, r);
}
int query(int r1, int r2, int l, int r, int x, int y)
{
    if (x <= l&&r <= y) return T[r2].cnt - T[r1].cnt;
    int mid = (l + r) >> 1;
    int ans1 = 0, ans2 = 0;
    if (x <= mid) ans1 = query(T[r1].lc, T[r2].lc, l, mid, x, y);
    if (y > mid) ans2 = query(T[r1].rc, T[r2].rc, mid + 1, r, x, y);
    return ans1 + ans2;
}
int main()
{
    int _, x, y;
    ll v;
    scanf("%d", &_);
    while (_--)
    {
        tot1 = tot = 0;
        scanf("%d%d%d", &n, &m, &p);
        int mid = (n + 1) / 2;
        for (int i = 1; i <= mid; i++){
            s[i] = s[i - 1] + max(1, 4 * (n - (2 * i - 1) + 1) - 4);
        }
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d", &a[i].x, &a[i].y);
            x = a[i].x, y = a[i].y;
            X[++tot1] = x;
            if (x == mid&&y == mid){
                v = 1LL * n*n;
            }
            else{
                int be = min(min(y, n - y + 1), min(x, (n - x + 1)));
                int bb = (n - be + 1);
                int cnt = 4 * (n - (2 * be - 1) + 1) - 4;
                if (x == bb&&y == bb){
                    v = 1;
                }
                else if (x == be || y == bb) {
                    v = cnt - (abs(x - bb) + abs(y - bb)) + 1;
                }
                else {
                    v = (abs(x - bb) + abs(y - bb)) + 1;
                }
                v += s[be - 1];
            }
            a[i].v = count(v);
        }
        sort(X + 1, X + tot1 + 1);
        tot1 = unique(X + 1, X + tot1 + 1) - X - 1;
        int pos, x1, y1, x2, y2, ans;
        for (int i = 1; i <= m; i++)
        {
            pos = lower_bound(X + 1, X + tot1 + 1, a[i].x) - X;
            g[pos].push_back(P(a[i].y, a[i].v));
        }
        for (int i = 1; i <= tot1; i++)
        {
            update(root[i], root[i - 1], g[i][0].first, g[i][0].second, 1, 1000000);
            for (int j = 1; j < g[i].size(); j++){
                update(root[i], root[i], g[i][j].first, g[i][j].second, 1, 1000000);
            }
            g[i].clear();
        }
        while (p--)
        {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            int p1 = lower_bound(X + 1, X + tot1 + 1, x1) - X, p2 = upper_bound(X + 1, X + tot1 + 1, x2) - X - 1;
            if (p1>p2){
                puts("0");
            }
            else{
                ans = query(root[p1 - 1], root[p2], 1, 1000000, y1, y2);
                printf("%d\n", ans);
            }
        }
    }
    return 0;
}
Last modification:September 1st, 2019 at 09:06 pm
如果觉得我的文章对你有用,请随意赞赏

2 comments

  1. gggg Firefox 69.0 Windows 10

    12312321

  2. 云中君 Google Chrome 76.0.3809.100 Windows 10

    写的不错!

Leave a Comment