【BZOJ2683】简单题 [分治][树状数组]

简单题

Time Limit: 50 Sec Memory Limit: 128 MB
[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。

Solution

　　首先把询问拆成4个，那么我们就只要维护一个点左下角权值和了。

　　然后对所有操作按照 x 升序排序。

　　对 y 用个树状数组求前缀和，（由于 x 升序，所以此时询问已经相当于对y求前缀和了）

　　以mid为分界线，考虑左区间对右区间的影响。

　　显然，我们可以把左区间的修改执行，然后执行右区间的询问。

　　这样我们就做完了这道题。

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 typedef long long s64;

 const int ONE = ;

 const int INF = ;

 int get()

 {

         int res = , Q = ; char c;

         while( (c = getchar()) <  || c > )

             if(c == '-') Q = -;

         if(Q) res = c - ;

         while( (c = getchar()) >=  && c <= )

             res = res *  + c - ;

         return res * Q;

 }

 int n;

 namespace BIT

 {

         int C[ONE];

         int lowbit(int i) {return i & -i;}

         void Add(int R, int x)

         {

             for(int i = R; i <= n; i += lowbit(i))

                 C[i] += x;

         }

         int Query(int R)

         {

             int res = ;

             for(int i = R; i >= ; i -= lowbit(i))

                 res += C[i];

             return res;

         }

 }

 int id, query_num, Ans[ONE];

 struct power

 {

         int id, opt, from;

         int x, y, val;

 }oper[ONE], q[ONE];

 bool cmp(const power &a, const power &b)

 {

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

         return a.opt < b.opt;

 }

 void Deal(int x_1, int y_1, int x_2, int y_2)

 {

         query_num++;

         oper[++id] = (power){id, , query_num, x_2, y_2, };

         oper[++id] = (power){id, , query_num, x_1 - , y_1 - , };

         oper[++id] = (power){id, , query_num, x_1 - , y_2, -};

         oper[++id] = (power){id, , query_num, x_2, y_1 - , -};

 }

 void Solve(int l, int r)

 {

         if(l >= r) return;

         int mid = l + r >> ;

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

         {

             if(oper[i].opt ==  && oper[i].id <= mid)

                 BIT::Add(oper[i].y, oper[i].val);

             if(oper[i].opt ==  && oper[i].id > mid)

                 Ans[oper[i].from] += BIT::Query(oper[i].y) * oper[i].val;

         }

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

             if(oper[i].opt ==  && oper[i].id <= mid)

                 BIT::Add(oper[i].y, -oper[i].val);

         int tl = l, tr = mid + ;

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

             if(oper[i].id <= mid) q[tl++] = oper[i];

             else q[tr++] = oper[i];

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

             oper[i] = q[i];

         Solve(l, mid), Solve(mid + , r);

 }

 int opt, x_1, y_1, x_2, y_2;

 int main()

 {

         n = get();

         for(;;)

         {

             opt = get();

             if(opt == ) break;

             if(opt == )

                 oper[++id].id = id, oper[id].opt = ,

                 oper[id].x = get(), oper[id].y = get(), oper[id].val = get();

             if(opt == )

                 x_1 = get(), y_1 = get(),

                 x_2 = get(), y_2 = get(),

                 Deal(x_1, y_1, x_2, y_2);

         }

         sort(oper + , oper + id + , cmp);

         Solve(, id);

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

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

 }

巴特西