BZOJ2683: 简单题-程序员宅基地

技术标签: CDQ分治  

BZOJ2683传送门
BZOJ1176几乎一样啊
戳这里–>BZOJ1176

然后这个题 应 该? 要开long long 吧。
(日常打错变量名QAQ。。)

【代码】

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#define N 200005
#define M 800005
#define INF 1<<29
using namespace std;
typedef long long ll;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){
   if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}

int n,tot,numa;
ll ans[N],szsz[500005];

class Query{
    public:
        int type,x,y,w,id;
    Query(){}
    Query(int tt,int xx,int yy,int ww,int ii){
        type=tt,x=xx,y=yy,w=ww,id=ii;
    }
}Q[M],tmp[M];

bool operator <(Query a,Query b){
    return a.x<b.x||(a.x==b.x&&a.type<b.type);
}

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

void Sum_Up(int x,int y){
    for(int i=x;i<=n;i+=lowbit(i)) szsz[i]+=y;
}

ll query(int x){
    ll rtn=0;
    for(int i=x;i;i-=lowbit(i)) rtn+=szsz[i];
    return rtn;
}

void Clear(int x){
    for(int i=x;i<=n&&szsz[i];i+=lowbit(i)) szsz[i]=0;
}

void CDQ(int l,int r)
{
    if(l==r) return;
    int mid=l+r>>1;CDQ(l,mid);CDQ(mid+1,r);
    int p=l,q=mid+1,o=0;
    while(p<=mid&&q<=r){
        if(Q[p]<Q[q]) {
            if(Q[p].type&1) Sum_Up(Q[p].y,Q[p].w);
            tmp[o++]=Q[p++];
        }
        else {
            if(Q[q].type==2) ans[Q[q].id]+=query(Q[q].y)*Q[q].w;
            tmp[o++]=Q[q++];
        }
    }
    while(p<=mid) tmp[o++]=Q[p++];
    while(q<=r) {
        if(Q[q].type==2) ans[Q[q].id]+=query(Q[q].y)*Q[q].w;
        tmp[o++]=Q[q++];
    }
    for(int i=0;i<o;i++) Clear(tmp[i].y),Q[i+l]=tmp[i];
}

int main()
{
    n=read();
    while(1)
    {
        static int tp,x,y,xx,yy;
        tp=read();if(tp==3) break;
        x=read(),y=read(),xx=read();
        if(tp&1) Q[++tot]=Query(tp,x,y,xx,0);
        else {
            yy=read();numa++;
            Q[++tot]=Query(tp,x-1,y-1,1,numa);Q[++tot]=Query(tp,x-1,yy,-1,numa);
            Q[++tot]=Query(tp,xx,y-1,-1,numa);Q[++tot]=Query(tp,xx,yy,1,numa);
        }
    }
    CDQ(1,tot);
    for(int i=1;i<=numa;i++) printf("%lld\n",ans[i]);
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Ep1C_HeReT1c/article/details/72657556

智能推荐

11、ThinkInJava(java编程思想)第九章 接口(策略设计模式) 笔记_根据参数,调用不同的service接口方法设计模式-程序员宅基地

文章浏览阅读82次。创建一个能够根据所传递参数对象不同而具有不同的行为的方法,称为策略设计模式。这类方法宝行索要执行的算法中固定不变的部分,而“策略”包含变化部分。策略就是传递进去的参数对象,他包含要执行的代码。这里processor对象就是一个策略,在main()方法中科院看到三种不同类型的策略应用到string类型的s对象上------------摘自java编程思想“接口”篇//: interfaces/cl..._根据参数,调用不同的service接口方法设计模式

mp3与aac音频格式的比较_5m左右的aac 和mp3-程序员宅基地

文章浏览阅读1.1w次。1. 常见的使用比较好的音频格式:mp3 aac2. 利用ffmpeg转换的命令:D:\srcVideo\testAudio>ffmpeg -i song.mp3 -strict -2 -ab96k -acodec aac song_aac.aac3. 转换后的文件比较:下面是从名为“music.mp4”文件通过ffmpeg抽取出音频的结_5m左右的aac 和mp3

Pytorch报urllib.error.URLError: <urlopen error [SSL: CERTIFICATE_VERIFY_FAILED]错误_raise urlerror(err) urllib.error.urlerror: <urlope-程序员宅基地

文章浏览阅读5.5k次,点赞21次,收藏14次。问题描述在调用torchvision.datasets.CIFAR10下载数据集的过程中,trainset = torchvision.datasets.CIFAR10(root='./data', train=True, download=True, transform=transform)报如下错误:Traceback (most recent call last): File "D:/pythonCode/pytorch/Learn_Torchvision/Leran_datasets_raise urlerror(err) urllib.error.urlerror:

form表单中input输入框的用法总结-程序员宅基地

文章浏览阅读1k次。1.  <input type="text"> type类型为text,定义一个可以输入内容文本输入框  2.  <input type="submit" value="提交"> type类型为text,定义一个按钮,点击会提交到form表单地址中    另外:<button>提交</button> 按钮的标签button..._form表单左右两侧都有输入框怎么写

使用Hugo和Github Pages服务从零开始搭建个人博客_hugo中文文档-程序员宅基地

文章浏览阅读616次,点赞2次,收藏6次。前几天查资料的时候,意外注意到了别人的博客地址是github.io结尾的,出于好奇就查了一下,原来是利用github的免费Pages服务来托管静态网站。因此本篇文章还是采用学习笔记的方式来记录,不断更新,共同进步。Github提供静态网站托管服务,也就是Github Pages服务;而Hugo是一个静态网站生成器,可从一系列源文件生成静态网站。_hugo中文文档

LR函数web_concurrent_start和web_concurrent_end_web_concurrent_start web_sync-程序员宅基地

文章浏览阅读842次。web_url("www.news.baidu.com", "URL=http://www.news.baidu.com/", "Resource=0", "RecContentType=text/html", "Referer=", "Snapshot=t2.inf", "Mode=HTTP", LAST);web_concurrent_start(N_web_concurrent_start web_sync

随便推点

FastJson中实体类、Json字符串和JSONObject之间的转换_fastjson实现object和实体类的转化-程序员宅基地

文章浏览阅读692次。1. 实体类或集合转JSON串String jsonString = JSONObject.toJSONString(实体类);2.JSON串转JSONObjectJSONObject jsonObject = JSONObject.parseObject(jsonString);3.JSON串转实体类实体类 javaBean = JSON.parseObject(json, ..._fastjson实现object和实体类的转化

CentOS6安装PLEX-程序员宅基地

文章浏览阅读355次。为什么80%的码农都做不了架构师?>>> ..._centosibm plex

(原创)Cassandra数据库的优化总结_cassandra 保存大数据连接超时-程序员宅基地

文章浏览阅读4.5k次。(原创)Cassandra数据库的优化总结[TOC] 实验室的源代码分析系统的Cassandra数据库优化过程从十一放假开学起cassandra一直出现的超时,崩溃等一系列问题就一直得不到解决。现在已经解决,把解决过程记录与此。0x01:分析原因起初分析原因,认为是一些基础设置不够到位,例如cassandra.yaml等配置不够好。因为cassandra不只是查询速度慢,其他操作例如插入之类的也会_cassandra 保存大数据连接超时

从零开始搭建自己的VueJS2.0+ElementUI单页面网站(一、环境搭建)-程序员宅基地

文章浏览阅读48次。原网址:https://blog.csdn.net/u012907049/article/details/72764151前言VueJS可以说是近些年来最火的前端框架之一,越来越多的网站开始使用vuejs作为前端框架,vuejs轻量、简单的特性使得前端开发变得更加简易,而基于vuejs的前端组件库也越来越多。我们今天使用的ElementUI,是饿了么团队开发的一款基于vuejs的前端..._idea 跑vue element 跑自己创建的页面

QT 中一些数学计算函数-程序员宅基地

文章浏览阅读3.3k次,点赞2次,收藏8次。QT的一些範例中有出現 qmax, qmin 等 math函式的身影,但我在官方文件中卻找不到與 math函式相關的說明,所以我就把函式的source裡面提供的方法整理條列,並且看看還有哪些 math相關的函式可用。在 qglobal.h 裡,可以找到幾種 math函式,條列於下,但一般常用的 math如:qfloor(無條件捨去)、qceil(無條件進位)、qsin,qcos,qta..._qt中数学函数常量比变量计算快

罗马仕充电宝php30pro拆解,罗马仕Sense 4移动电源拆解-程序员宅基地

文章浏览阅读4.7k次。◆ 罗马仕Sense 4移动电源拆解罗马仕的Sense 4移动电源外壳以白色和灰色相间,白色的外壳为细磨砂处理,和灰色中壳之间采用超声波密封,做工还是相当不错的。不过这也是我们评测以来最难拆的一款产品。罗马仕Sense 4把两边外壳拆开之后,接下来看到的东西和我之前猜测的完全不一样。我在拆解之前认为这应该是4节电量为2600mAh的18650电芯,累计10400mAh就和标称的相符,不过拆开之后发..._罗马仕sense4拆解