NekoMio's Blog

美しいものが起こることを常に信じている

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  • Code
  • Description

    维护一个W*W的矩阵,初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.

    Input

    第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小

    接下来每行为一下三种输入之一(不包含引号):
    “1 x y a”
    “2 x1 y1 x2 y2”
    “3”
    输入1:你需要把(x,y)(第x行第y列)的格子权值增加a
    输入2:你需要求出以左下角为(x1,y1),右上角为(x2,y2)的矩阵内所有格子的权值和,并输出
    输入3:表示输入结束

    Output

    对于每个输入2,输出一行,即输入2的答案

    Sample Input

    0 4
    1 2 3 3
    2 1 1 3 3
    1 2 2 2
    2 2 2 3 4
    3

    Sample Output

    3
    5

    Code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int MAXN = 800005;
    struct Query
    {
    int x, y, op, val, id, pos;
    bool operator < (const Query &a) const
    {
    return x == a.x ? op < a.op : x < a.x;
    }
    } Ask[MAXN], tmp[MAXN];
    int n, m, Ans[MAXN];
    #define lowbit(_) ((_)&(-_))
    struct BIT
    {
    int Sum[2000005];
    void add(int x, int c)
    {
    for (int i = x; i <= n; i += lowbit(i))
    Sum[i] += c;
    }
    int Query(int x)
    {
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i))
    ans += Sum[i];
    return ans;
    }
    }bit;
    void add()
    {
    int x1, y1, x2, y2;
    scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);
    ++Ans[0];
    Ask[++m].pos = Ans[0], Ask[m].x = x1 - 1, Ask[m].y = y1 - 1, Ask[m].val = 1, Ask[m].op = 1;
    Ask[++m].pos = Ans[0], Ask[m].x = x2 , Ask[m].y = y2 , Ask[m].val = 1, Ask[m].op = 1;
    Ask[++m].pos = Ans[0], Ask[m].x = x1 - 1, Ask[m].y = y2 , Ask[m].val =-1, Ask[m].op = 1;
    Ask[++m].pos = Ans[0], Ask[m].x = x2 , Ask[m].y = y1 - 1, Ask[m].val =-1, Ask[m].op = 1;
    }
    void CDQ(int l, int r)
    {
    if (l == r)
    return;
    int mid = l + r >> 1, l1 = l, l2 = mid + 1;
    for (int i = l; i <= r; i++)
    {
    if (Ask[i].id <= mid && !Ask[i].op)
    bit.add(Ask[i].y, Ask[i].val);
    if (Ask[i].id > mid && Ask[i].op)
    Ans[Ask[i].pos] += Ask[i].val * bit.Query(Ask[i].y);
    }
    for (int i = l; i <= r; i++)
    if (Ask[i].id <= mid && !Ask[i].op)
    bit.add(Ask[i].y, -Ask[i].val);
    for (int i = l; i <= r; i++)
    {
    if (Ask[i].id <= mid)
    tmp[l1++] = Ask[i];
    else tmp[l2++] = Ask[i];
    }
    for (int i = l; i <= r; i++)
    Ask[i] = tmp[i];
    CDQ(l, mid);
    CDQ(mid + 1, r);
    return;
    }
    int main()
    {
    freopen("mokia.in", "r", stdin);
    freopen("mokia.out", "w", stdout);
    int op;
    scanf ("%d%d", &op, &n);
    while (1)
    {
    scanf ("%d", &op);
    if (op == 1)
    {
    m++;
    scanf ("%d%d%d", &Ask[m].x, &Ask[m].y, &Ask[m].val);
    }
    else if (op == 2)
    add();
    else break;
    }
    for (int i = 1; i <= m; i++)
    Ask[i].id = i;
    sort(Ask + 1, Ask + m + 1);
    CDQ(1 ,m);
    for (int i = 1; i <= Ans[0]; i++)
    printf ("%d\n", Ans[i]);
    }

    本文作者 : NekoMio
    知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
    本文链接 : https://www.nekomio.com/2017/10/21/115/

    本文最后更新于 天前,文中所描述的信息可能已发生改变