bzoj1176
题目描述
维护一个W*W的矩阵,初始值均为S(题目描述有误,这里的S没有任何作用!).每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.
输入
第一行两个整数,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:表示输入结束
输出
对于每个输入2,输出一行,即输入2的答案
样例输入
0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
样例输出
3
5
bzoj2683
题目描述
同上,只是少了一个烦人的S
题解
CDQ分治
先读入所有修改和询问操作,将每个修改拆成4个。
然后按照CDQ分治的套路,按x排序,按id比较,按y查询。
(好像这道题我写的和别的CDQ分治题不一样。。。)
代码是1176的,2683直接去掉%*d即可。
(就算S真的有用,可以直接改ans的初始值,也是一样的)
#include <cstdio>
#include <algorithm>
using namespace std;
struct data
{
int x , y , v , p , id , opt;
}a[800000] , tmp[800000];
int n , tot , cnt , f[2000010] , ans[200000];
bool cmp(data a , data b)
{
return a.x == b.x ? (a.y == b.y ? a.opt < b.opt : a.y < b.y) : a.x < b.x;
}
void add(int b , int c , int d , int t)
{
a[++tot].x = b , a[tot].y = c , a[tot].v = d , a[tot].id = tot , a[tot].opt = t;
if(t) a[tot].p = cnt;
}
void update(int x , int a)
{
int i;
for(i = x ; i <= n ; i += i & -i) f[i] += a;
}
int query(int x)
{
int i , ans = 0;
for(i = x ; i ; i -= i & -i) ans += f[i];
return ans;
}
void solve(int l , int r)
{
if(l == r) return;
int mid = (l + r) >> 1 , i , p1 = l , p2 = mid + 1;
for(i = l ; i <= r ; i ++ )
{
if(a[i].id <= mid && !a[i].opt) update(a[i].y , a[i].v);
if(a[i].id > mid && a[i].opt) ans[a[i].p] += a[i].v * query(a[i].y);
}
for(i = l ; i <= r ; i ++ ) if(a[i].id <= mid && !a[i].opt) update(a[i].y , -a[i].v);
for(i = l ; i <= r ; i ++ )
{
if(a[i].id <= mid) tmp[p1 ++ ] = a[i];
else tmp[p2 ++ ] = a[i];
}
for(i = l ; i <= r ; i ++ ) a[i] = tmp[i];
solve(l , mid) , solve(mid + 1 , r);
}
int main()
{
int i , k , b , c , d , e;
scanf("%*d%d" , &n);
while(scanf("%d" , &k) && k != 3)
{
if(k == 1) scanf("%d%d%d" , &b , &c , &d) , add(b , c , d , 0);
else scanf("%d%d%d%d" , &b , &c , &d , &e) , cnt ++ , add(d , e , 1 , 1) , add(b - 1 , e , -1 , 1) , add(d , c - 1 , -1 , 1) , add(b - 1 , c - 1 , 1 , 1);
}
sort(a + 1 , a + tot + 1 , cmp);
solve(1 , tot);
for(i = 1 ; i <= cnt ; i ++ ) printf("%d\n" , ans[i]);
return 0;
}