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

Description

你有一个N*N的棋盘,每个格子内有一个整数,初始时的时候全部为0,现在需要维护两种操作:
命令 参数限制 内容
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 无 终止程序

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。

题解

首先对于这道题,看了范围之后,二维的数据结构是显然不能过的,于是我们可能会考虑把一维排序之后另一位上数据结构什么的,然而cdq分治却能够很好的体现它的作用。

首先,对于每一个询问求和,显然是x在它左边的并且出现时间在它之前的所有的change对他可能会有影响。

我们按照x第一关键字,y第二关键字,操作第三关键字来排序所有的询问,然后在cdq的时候,每次递归处理左半区间,按照x动态的将y这一列的值加到树状数组里,来更新右半边的所有询问,注意这里的树状数组是需要清的,也就是每次cdq都是采用不同的树状数组。

另:这题神坑,数组开小不是RE而是WA

数组范围是要开到200000*4的,因为对于每个1操作,是一个操作,而2操作根据容斥原理,是4个操作。所以复杂度大概是多少呢O(nlog2(n))cdq+树状数组。n<=800000

#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;
}
​

内容更新于: 2017-01-18 08:56:12
链接地址: http://blog.leanote.com/post/icontofig/0ebb734a6377

上一篇: NOI2007 货币兑换 Cash 【CDQ分治 斜率优化DP】

下一篇: [Zjoi2013]K大数查询

208 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航