【BOI2007】【BZOJ1176】Mokia

简介:

1176: [Balkan2007]Mokia 
Time Limit: 30 Sec Memory Limit: 162 MB 
Submit: 1059 Solved: 432 
[Submit][Status][Discuss] 
Description

维护一个W*W的矩阵,初始值均为S.每次操作能够添加某格子的权值,或询问某子矩阵的总权值.改动操作数M<=160000,询问数Q<=10000,W<=2000000. 
Input

第一行两个整数,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:表示输入结束 
Output

对于每一个输入2,输出一行,即输入2的答案 
Sample Input 
0 4

1 2 3 3

2 1 1 3 3

1 2 2 2

2 2 2 3 4


Sample Output 
3


HINT

保证答案不会超过int范围

Source

cdq分治的模板题然而我如今才做这个题。

。。 
差分一下询问操作。对全部操作按y排序。 
树状数组维护一下。

然后就能够了。


自从看过了Tsinsen上的姿势分 
我写代码都開始丧心病狂了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 200000
#define SIZE 2000010
#define lowbit(x) (x&(-x))
using namespace std;
int w;
int top,opt,L,R,l,r,delta,Top;
struct Query
{
    int op;
    int x,y,A;
    int t,id;
    bool operator <(const Query& a)const
    {
        if (x == a.x && y == a.y) return op < a.op;
        if (x == a.x) return y < a.y;
        return x < a.x;
    }
}que[MAXN],newq[MAXN];
int ans[MAXN],c[SIZE];
inline void in(int &x)
{
    x=0;char ch = getchar();
    while (!(ch >= '0' && ch <= '9'))   ch = getchar();
    while (ch >= '0' && ch <= '9')  x = x * 10 + ch - '0',ch = getchar();
}
inline void add(int i,int x)
{
    while (i && i <= w) c[i] += x,i += lowbit(i);
}
inline int query(int i)
{
    int ret = 0;
    while (i) ret += c[i],i -= lowbit(i);
    return ret;
}
inline void Solve(int l,int r)
{
    int mid = (l + r) >> 1,tp1 = l,tp2 = mid + 1;
    if (l == r) return;
    for (int i = l;i <= r;i++)
    {
        if (que[i].t <= mid && que[i].op == 1)  add(que[i].y,que[i].A);
        if (que[i].t > mid && que[i].op == 2)   ans[que[i].id] += query(que[i].y) * que[i].A;
    }
    for (int i = l;i <= r;i++)
        if (que[i].t <= mid && que[i].op == 1) add(que[i].y,-que[i].A);
    for (int i = l;i <= r;i++)
        if (que[i].t <= mid) newq[tp1++] = que[i];
        else newq[tp2++] = que[i];
    memcpy(que+l,newq+l,sizeof(Query)*(r - l + 1));
    Solve(l,mid);Solve(mid+1,r); 
}
int main()
{
    freopen("mokia.in","r",stdin);
    freopen("mokia.out","w",stdout);
    in(opt);in(w);
    while (1)
    {
        in(opt);
        if (opt == 3) break;
        switch (opt)
        {
            case 1:
                in(L);in(R);in(delta);
                que[++top].op = opt;que[top].x = L;que[top].y = R;que[top].A = delta;que[top].t = top;
                break;
            case 2:
                in(L);in(R);in(l);in(r);
                que[++top].op = opt;que[top].x = L - 1;que[top].y = R - 1;que[top].t = top;que[top].A = 1;que[top].id = ++Top;
                que[++top].op = opt;que[top].x = L - 1;que[top].y = r;que[top].t = top;que[top].A = -1;que[top].id = Top;
                que[++top].op = opt;que[top].x = l;que[top].y = R - 1;que[top].t = top;que[top].A = -1;que[top].id = Top;
                que[++top].op = opt;que[top].x = l;que[top].y = r;que[top].t = top;que[top].A = 1;que[top].id = Top;
                break;
        }
    }
    sort(que + 1,que + top + 1);
    Solve(1,top);
    for (int i = 1;i <= Top;i++)    printf("%d\n",ans[i]);
}


本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5153369.html,如需转载请自行联系原作者
相关文章
|
人工智能 IDE 开发工具
任意输入的日期转成星期几
任意输入的日期转成星期几
108 2
|
传感器 关系型数据库 ice
Google Earth Engine ——LANDSAT8——TOA系列数据
Google Earth Engine ——LANDSAT8——TOA系列数据
519 0
Google Earth Engine ——LANDSAT8——TOA系列数据
阿里云企业邮箱哪个代理商好
  阿里云企业邮箱哪个代理商好,阿里云企业邮箱开通,阿里企业邮箱怎么注册,阿里云邮箱企业版试用询“阿里邮箱华南400服务066中心2020”(汇华科技),2015年5月,钉钉正式推出了合作协同功能,同时也推出了与阿里邮箱合作的邮箱产品——钉邮。
|
Windows API 自然语言处理
背水一战 Windows 10 (80) - 本地化
原文:背水一战 Windows 10 (80) - 本地化 [源码下载] 背水一战 Windows 10 (80) - 本地化 作者:webabcd介绍背水一战 Windows 10 之 本地化 Demo 改变语言 示例1、演示本地化的基本应用Localization/LocalizationDemo.
1010 0
|
搜索推荐 程序员
程序员从初级到中级10个秘诀
ustin James曾发表过一篇博文《10 tips for advancing from a beginner to an intermediate developer》,为我们分享如何才能完成程序员从初级到中级的蜕变,现将中文译文转载于此,供大家借鉴。
1279 0
|
算法 C++
2013级C++第14周项目——一维数组、字符数组
课程首页在:http://blog.csdn.net/sxhelijian/article/details/11890759 【项目1 - 数组大折腾】  将所有元素值加倍后保存在数组中,最后由前往后输出数组中所有元素的值,再由后往前输出数组中所有元素的值,再输出数组中的所有大于100的数,以及下标为3的倍数的元素值。  (1)创建一个长度为20的整型数组,通过初始化,为数组中的前10个元素
1345 0
|
5天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
16天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1315 5