icontofig | 发布于 2017-01-18 08:56:15 | 阅读量 208 | CDQ分治 树状数组

## Description

1 x y A 1<=x,y<=N，A是正整数 将格子x,y里的数字加上A
2 x1 y1 x2 y2 1<=x1<= x2<=N1<=y1<= y2<=N 输出x1 y1 x2 y2这个矩形内的数字和
3 无 终止程序

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

3
5

## HINT

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

## 题解

```#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}
const int maxn = 8e5+5;
struct point{
int opt,x,y,a,id,be;
}q[maxn],nq[maxn];
int n,fl,tot,t,ans[maxn],sum[maxn];
bool cmp(point a,point b){
return (a.x < b.x || (a.x == b.x && a.y < b.y) || (a.x == b.x && a.y == b.y && a.opt < b.opt));
}
int lowbit(int x){
return x & (-x);
}
void update(int p,int v){
for(int i = p;i < maxn;i += lowbit(i))
sum[i] += v;
}
int Sum(int p){
int ret = 0;
while(p > 0){
ret += sum[p];
p -= lowbit(p);
}
return ret;
}
void cdq(int l,int r){
if(l == r) return;
int mid = (l + r) >> 1;
for(int i = l;i <= r;++i){
if(q[i].id <= mid && q[i].opt == 1)update(q[i].y,q[i].a);
else if(q[i].id > mid && q[i].opt == 2){
if(q[i].a)ans[q[i].be] += Sum(q[i].y);
else ans[q[i].be] -= Sum(q[i].y);
}
}
for(int i = l;i <= r;++i)
if(q[i].id <= mid && q[i].opt == 1)
update(q[i].y,-q[i].a);
int l1,l2;
l1 = l;l2 = mid + 1;
for(int i = l;i <= r;++i){
if(q[i].id <= mid)
nq[l1++] = q[i];
else nq[l2++] = q[i];
}
for(int i = l;i <= r;++i)
q[i] = nq[i];
cdq(l,mid);
cdq(mid+1,r);
}
int main(){
n = get_num();
while(true){
fl = get_num();
if(fl == 3)break;
if(fl == 1){
int x,y,a;
x = get_num();y = get_num();a = get_num();
q[++tot].opt = 1;q[tot].x = x;q[tot].y = y;q[tot].a = a;q[tot].id = tot;
}
else{
int x1,y1,x2,y2;
x1 = get_num();y1 = get_num();
x2 = get_num();y2 = get_num();
q[++tot].opt = 2;q[tot].x = x1 - 1;q[tot].y = y1-1;q[tot].a = 1;q[tot].id = tot;q[tot].be = ++t;
q[++tot].opt = 2;q[tot].x = x1 - 1;q[tot].y = y2;q[tot].a = 0;q[tot].id = tot;q[tot].be = t;
q[++tot].opt = 2;q[tot].x = x2;q[tot].y = y1-1;q[tot].a = 0;q[tot].id = tot;q[tot].be = t;
q[++tot].opt = 2;q[tot].x = x2;q[tot].y = y2;q[tot].a = 1;q[tot].id = tot;q[tot].be = t;
}
}
sort(q+1,q+tot+1,cmp);
cdq(1,tot);
for(int i = 1;i <= t;++i){
printf("%d\n",ans[i]);
}
return 0;
}
﻿​```

208 人读过

0 条评论