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

本文链接：https://blog.csdn.net/Ep1C_HeReT1c/article/details/72657556

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

瑞芯微RK3288、RK3399、RK3568、RK3368芯片性能介绍与对比分析_rk3288和rk3568对比-程序员宅基地

文章浏览阅读2.1k次，点赞7次，收藏8次。是瑞芯微推出的一款低功耗、高性能的应用处理器芯片，该芯片基于Big.Little架构,即具有独立的NEON协同处理器的双核Cortex-A72及四核Cortex-A53组合架构，主要应用于计算机、个人互联网移动设备、VR、广告机等智能终端设备。RK3399内置多个高性能硬件处理引擎，能够支持多重格式的视频解码，如：4K*2K@60fps 的H.264/H.265/VP9，也支持1080P@30fps的H.264/MVC/VP8 以及高质量的JPEG编解码和图像的前后处理器。_rk3288和rk3568对比

使用esp 8266物联网开发板 + Mqtt制作远程控制LED小灯_esp8266 mqtt 控制灯亮灭-程序员宅基地

文章浏览阅读1.5k次。如何30快钱以内制作一个手机控制的led小灯_esp8266 mqtt 控制灯亮灭

Ansys Zemax | 如何模拟光学相干层析成像系统_nsdd操作数-程序员宅基地

文章浏览阅读291次，点赞2次，收藏4次。聚焦透镜的坐标(0，20，40)，使聚焦透镜与扫描镜保持水平，并保持20mm的距离(该距离在两者的水平位置距离中是任意的)，聚焦透镜的材料为N-BK7。_nsdd操作数

流式处理中的文本聚类：探索Apache Beam在文本数据处理中的应用-程序员宅基地

文章浏览阅读5.7k次。作者：禅与计算机程序设计艺术流式处理中的文本聚类：探索Apache Beam在文本数据处理中的应用引言1.1. 背景介绍随着互联网与物联网的发展，大量的文本数据在各个领

基于微服务架构的分布式系统：如何设计和实现高效的微服务系统_基于微服务的系统-程序员宅基地

文章浏览阅读4.7k次。随着互联网的发展，分布式系统在大型企业应用中越来越普遍。微服务架构作为一种新兴的分布式系统架构，以其灵活性和可扩展性吸引了越来越多的开发者。在微服务架构中，每个服务都是独立的，具有完整的功能和数据职责。本文旨在探讨如何设计和实现高效的微服务系统，以应对现代应用中日益增长的需求。服务注册和发现：服务注册表和反向代理服务。服务路由：服务发现和路由器。服务安全：访问控制、加密和认证。分布式事务：分布式事务工具，如乐观锁。消息队列：异步处理和消息传递。_基于微服务的系统

全网最有效解决centos7 安装MySQL报错No package mysql-server available_no package mod_auth_mysql available.-程序员宅基地

文章浏览阅读856次。今天想在centos7上面装一个mysql，但是无论我yum就还是wget都装不上，提示No package mysql-server…,然后又度娘又各种查资料，试了好多种方法都没有用，最后了解Centos7系统后发现，Centos7带有MariaDB而不是MySQL，MariaDB和MySQL一样也是开元的数据库，同样可以使用yum命令安装，只不过安装使用的并不是老方式的MySQL，而是默认的MariaDB，并且还需要安装的是mariadb-server，如果想继续使用老方式的MySQL，那么需要清_no package mod_auth_mysql available.