2683: 简单题

Time Limit: 50 Sec Memory Limit: 128 MB
Submit: 913 Solved: 379
[Submit][Status][Discuss]

Description

你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：

命令	参数限制	内容
1 x y A	1<=x,y<=N，A是正整数	将格子x,y里的数字加上A
2 x y x y	1<=x<= x<=N 1<=y<= y<=N	输出x y x y这个矩形内的数字和
3	无	终止程序

Input

输入文件第一行一个正整数N。

接下来每行一个操作。

Output

对于每个2操作，输出一个对应的答案。

Sample Input

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

Sample Output

3
5

HINT

1<=N<=500000,操作数不超过200000个，内存限制20M。

对于100%的数据，操作1中的A不超过2000。

Source

[Submit][Status][Discuss]

分析

离线CDQ分治，对于预处理后的所有操作（查询）按照X坐标排序，然后用树状数组维护Y坐标上的前缀和。

代码

 #include <bits/stdc++.h>

 using namespace std;

 const int N = ;

 const int M = ;

 template <class T>

 __inline void read(T &x)

 {

     x = ;

     bool f = false;

     char c = getchar();

     while (c < '')

     {

         if (c == '-')

             f ^= true;

         c = getchar();

     }

     while (c >= '')

     {

         x = x* + c - '';

         c = getchar();

     }

     if (f)x = -x;

 }

 struct operation

 {

     int id, op, to, x, y, d;

 }q[M << ], tmp[M << ];

 int cmp(const void *a, const void *b)

 {

     operation *A = (operation *)a;

     operation *B = (operation *)b;

     if (A->x != B->x)

         return A->x - B->x;

     if (A->y != B->y)

         return A->y - B->y;

     return A->op - B->op;

 }

 int n, m, t;

 void pushQuery(void)

 {

     int x1; read(x1);

     int y1; read(y1);

     int x2; read(x2);

     int y2; read(y2);

     ++t;

     {

         ++m;

         q[m].d = ;

         q[m].op = ;

         q[m].id = m;

         q[m].to = t;

         q[m].x = x1 - ;

         q[m].y = y1 - ;

     }

     {

         ++m;

         q[m].d = ;

         q[m].op = ;

         q[m].id = m;

         q[m].to = t;

         q[m].x = x2;

         q[m].y = y2;

     }

     {

         ++m;

         q[m].d = -;

         q[m].op = ;

         q[m].id = m;

         q[m].to = t;

         q[m].y = y2;

         q[m].x = x1 - ;

     }

     {

         ++m;

         q[m].d = -;

         q[m].op = ;

         q[m].id = m;

         q[m].to = t;

         q[m].x = x2;

         q[m].y = y1 - ;

     }

 }

 int answer[M];

 void printAnswer(void)

 {

     for (int i = ; i <= t; ++i)

         printf("%d\n", answer[i]);

 }

 namespace binaryInsertTree

 {

     int tree[N];

     void change(int p, int v)

     {

         for (int i = p; i <= n; i += i & -i)

             tree[i] += v;

     }

     int query(int p)

     {

         int ret = ;

         for (int i = p; i >= ; i -= i & -i)

             ret += tree[i];

         return ret;

     }

 }

 void divideAndConquer(int l, int r)

 {

     if (l != r)

     {

         int mid = (l + r) >> ;

         for (int i = l; i <= r; ++i)

         {

             if (q[i].op ==  && q[i].id <= mid)

                 binaryInsertTree::change(q[i].y, q[i].d);

             if (q[i].op ==  && q[i].id > mid)

                 answer[q[i].to] += binaryInsertTree::query(q[i].y) * q[i].d;

         }

         for (int i = l; i <= r; ++i)

             if (q[i].op ==  && q[i].id <= mid)

                 binaryInsertTree::change(q[i].y, -q[i].d);

         int t1 = l, t2 = mid + ;

         for (int i = l; i <= r; ++i)

         {

             if (q[i].id <= mid)

                 tmp[t1++] = q[i];

             else

                 tmp[t2++] = q[i];

         }

         for (int i = l; i <= r; ++i)

             q[i] = tmp[i];

         divideAndConquer(l, mid);

         divideAndConquer(mid + , r);

     }

 }

 signed main(void)

 {

     read(n);

     for (m = t = ; ; )

     {

         int opt; read(opt);

         if (opt == )break;

         switch (opt)

         {

             case  :

                 ++m;

                 q[m].op = ;

                 q[m].id = m;

                 read(q[m].x);

                 read(q[m].y);

                 read(q[m].d);

                 break;

             case  :

                 pushQuery();

         }

     }

     qsort(q + , m, sizeof(operation), cmp);

     divideAndConquer(, m);

     printAnswer();

 }

BZOJ_2683.cpp

@Author: YouSiki

简单题

BZOJ 2683: 简单题