权值线段树套区间线段树
把插入的值离散化一下开个线段树
蓝后每个节点开个线段树,维护一下每个数出现的区间和次数
为了防止MLE动态开点就好辣
重点是标记永久化,就是不下传标记,而是每次询问时算上路径上的标记
标记永久化后快了1倍
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rint register int
using namespace std;
typedef long long ll;
inline int Min(int a,int b){return a<b?a:b;}
inline int Max(int a,int b){return a>b?a:b;}
void gi(int &x){
static char c=getchar();x=;
while(c<''||c>'') c=getchar();
while(''<=c&&c<='') x=x*+(c^),c=getchar();
}
void gll(ll &x){
static char c=getchar();x=; bool f=;
while(c<''||c>'') f=f&&(c!='-'),c=getchar();
while(''<=c&&c<='') x=x*+(c^),c=getchar();
x=f?x:-x;
}
#define N 50005
#define W 20000005
int n,m,u,tn,opt[N],L[N],R[N],b[N],rt[],lc[W],rc[W],add[W];
ll k[N],sum[W];
#define mid (l+r)/2
void Add(int &o,int l,int r,int x1,int x2){
if(!o) o=++u;
sum[o]+=Max(Min(x2,r)-Max(x1,l)+,);//遍历过程中先处理掉sum
if(x1<=l&&r<=x2){++add[o]; return ;}//标记永久化
if(x1<=mid) Add(lc[o],l,mid,x1,x2);
if(x2>mid) Add(rc[o],mid+,r,x1,x2);
}
ll Ask(int o,int l,int r,int x1,int x2,ll t){
if(!o) return t*Max(Min(x2,r)-Max(x1,l)+,);//注意不返回0
if(x1<=l&&r<=x2) return sum[o]+t*(r-l+);
ll re=;
if(x1<=mid) re+=Ask(lc[o],l,mid,x1,x2,t+add[o]);//累加路径上的标记
if(x2>mid) re+=Ask(rc[o],mid+,r,x1,x2,t+add[o]);
return re;
}
void ins(int o,int l,int r,int x1,int x2,int v){
Add(rt[o],,n,x1,x2);
if(l==r) return ;
if(v<=mid) ins(o<<,l,mid,x1,x2,v);
else ins(o<<|,mid+,r,x1,x2,v);
}
int ask(int o,int l,int r,int x1,int x2,ll v){
if(l==r) return b[l];
ll tmp=Ask(rt[o<<|],,n,x1,x2,);
if(v<=tmp) return ask(o<<|,mid+,r,x1,x2,v);
else return ask(o<<,l,mid,x1,x2,v-tmp);
}
int main(){
gi(n);gi(m);
for(rint i=;i<=m;++i){
gi(opt[i]);gi(L[i]);gi(R[i]);gll(k[i]);
if(opt[i]==) b[++tn]=k[i];
}sort(b+,b+tn+);
tn=unique(b+,b+tn+)-b-;//离散化
for(rint i=;i<=m;++i)
if(opt[i]==) k[i]=lower_bound(b+,b+tn+,k[i])-b;
for(rint i=;i<=m;++i){
if(opt[i]==) ins(,,tn,L[i],R[i],k[i]);
else printf("%d\n",ask(,,tn,L[i],R[i],k[i]));
}return ;
}
P3332 [ZJOI2013]K大数查询(线段树套线段树+标记永久化)的更多相关文章
-
洛谷 P3332 [ZJOI2013]K大数查询 解题报告
P3332 [ZJOI2013]K大数查询 题目描述 有\(N\)个位置,\(M\)个操作.操作有两种,每次操作如果是\(\tt{1\ a\ b\ c}\)的形式表示在第\(a\)个位置到第\(b\) ...
-
洛谷 P3332 [ZJOI2013]K大数查询 (整体二分理解)
链接: P3332 题意: 维护 \(n(1\leq n\leq 5\times10^4)\) 个可重整数集,编号从 \(1\) 到 \(n\).有 \(m(1\leq m\leq5\times10^ ...
-
P3332 [ZJOI2013]K大数查询
传送门 注意操作 $1$ 是在区间的每个位置加入一个数,不是加上一个值 相当于每个位置维护的是一个集合 显然树套树 一开始想的是区间线段树套权值线段树 发现这样询问区间第 $K$ 大时就要先二分答案再 ...
-
[洛谷P3332][ZJOI2013]K大数查询
题目大意:有$n$个位置,$m$个操作.操作有两种: $1\;l\;r\;x:$在区间$[l,r]$每个位置加上一个数$x$ $2\;l\;r\;k:$询问$[l,r]$中第$k$大的数是多少. 题解 ...
-
洛谷 P3332 [ZJOI2013]K大数查询 || bzoj3110
用树套树就很麻烦,用整体二分就成了裸题.... 错误: 1.尝试线段树套平衡树,码农,而且n*log^3(n)慢慢卡反正我觉得卡不过去 2.线段树pushdown写错...加法tag对于区间和的更新应 ...
-
洛谷P3332 [ZJOI2013]K大数查询 权值线段树套区间线段树_标记永久化
Code: #include <cstdio> #include <algorithm> #include <string> #include <cstrin ...
-
P3332 [ZJOI2013]K大数查询 整体二分
终于入门整体二分了,勉勉强强算是搞懂了一个题目吧. 整体二分很多时候可以比较好的离线处理区间\(K\)大值的相关问题.考虑算法流程: 操作队列\(arr\),其中有询问和修改两类操作. 每次在答案的可 ...
-
bzoj 3110: [Zjoi2013]K大数查询 树状数组套线段树
3110: [Zjoi2013]K大数查询 Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 1384 Solved: 629[Submit][Stat ...
-
BZOJ 3110([Zjoi2013]K大数查询-区间第k大[段修改,在线]-树状数组套函数式线段树)
3110: [Zjoi2013]K大数查询 Time Limit: 20 Sec Memory Limit: 512 MB Submit: 418 Solved: 235 [ Submit][ ...
随机推荐
-
JS 实现可停顿的垂直滚动
var ScrollMiddle = { 'Odiv':document.getElementById('comment'), // 目标DOM 'Oli': document.getElementB ...
-
noi 2989 糖果
题目链接:http://noi.openjudge.cn/ch0206/2989/ 首先,数据很大,直接用背包会re. 这里增加的是对%k 的余数维度.f[i][j] 表示前 i 种糖果取到总颗数模 ...
-
HTML速查列表
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xht ...
-
IL查看泛型
查看泛型的IL 我们在开发中经常用到泛型,下面一起通过IL来查看泛型背后做了那些工作 示例代码 示例代码如下: using System; namespace MyCollection { pub ...
-
html页面元素加载顺序
一般来说,添加背景图片有三种办法: 直接写在标签的style里面,如: <div style="background-image:url('images/Css.JPG')" ...
-
java web工程的错误页面的简单配置
jsp页面,本身服务器也会将该页面翻译成一个servlet页面,所以请求该页面就会有可能出现错误的情况,就会出现下面类似的页面 这样给客户看到并不友好. 1.jsp页面<%@ page %> ...
-
HDU2186--水
悼念512汶川大地震遇难同胞--一定要记住我爱你 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java ...
-
Selenium-WebDriverApi接口详解
浏览器操作 # 刷新 driver.refresh() # 前进 driver.forward() # 后退 driver.back() 获取标签元素 # 通过ID定位目标元素 driver.find ...
-
Django基础与组件
第一章:Django系列之web应用与http协议 第二章:基于wsgiref模块DIY一个web框架 第三章:Django下载与简介 第四章:url控制系统 第五章:视图 第六章:Django模板语 ...
-
使用AutoMapper实现Dto和Model的*转换(上)
在实际的软件开发项目中,我们的“业务逻辑”常常需要我们对同样的数据进行各种变换.例如,一个Web应用通过前端收集用户的输入成为Dto,然后将Dto转换成领域模型并持久化到数据库中.另一方面,当用户请求 ...